图的基本概念ppt课件.ppt

第五章第五章 图的基本概念图的基本概念 图论起源于图论起源于1736年欧拉年欧拉(Enler)的第一篇的第一篇图论图论 论文论文, 解决了解决了“哥尼斯堡的七桥问哥尼斯堡的七桥问题题”。在哥尼斯堡的匹格河上有七座桥。在哥尼斯堡的匹格河上有七座桥,如图所示。如图所示。 当时人们热衷于这样的游戏：设想从任一当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回个地方出发通过每座桥一次且仅一次后回到原地到原地, 这是否可能这是否可能?但多次实践都发现不但多次实践都发现不行行 1727 年欧拉的朋友向欧拉提出了这个问题年欧拉的朋友向欧拉提出了这个问题是否有解？是否有解？ 1736 年欧拉用图论的方法解决了这个问题年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文写了第一篇图论的论文,成为图论的创始人。成为图论的创始人。 后来称此问题为哥尼斯堡七桥问题。后来称此问题为哥尼斯堡七桥问题。 在图在图a中中,用边表示桥用边表示桥,顶点表示岛屿和河的顶点表示岛屿和河的两岸两岸,便得到一个图便得到一个图,如图如图b所示。所示。很显然很显然,通过哥尼斯堡通过哥尼斯堡七座桥中每一座一次七座桥中每一座一次且仅一次的问题等价且仅一次的问题等价于在图于在图5.13 (b)中找一中找一条闭链条闭链,使得它的每一边出现使得它的每一边出现一次且仅一次一次且仅一次, 也就是也就是如何一笔画的问题。如何一笔画的问题。 但在此之后但在此之后100年间，没有大的进展。年间，没有大的进展。 直到直到Kirchhoff(克希霍夫克希霍夫)用树的理论解决了电网络问题，用树的理论解决了电网络问题， 1857年年Cayler(凯莱凯莱)用统计不同构树的方法来计算用统计不同构树的方法来计算CnH2n+1同分异构体数目同分异构体数目, 这些结果引起了人们的重视这些结果引起了人们的重视,图论的研究进入了一个发展图论的研究进入了一个发展时期时期, 在此期间在此期间,出现了两个著名的问题出现了两个著名的问题:四色问题和四色问题和Hamilton回路问题回路问题,成为不少数学家的研究目标。成为不少数学家的研究目标。 但在但在19世纪后期和二十世纪初，图论的研究再次处于停世纪后期和二十世纪初，图论的研究再次处于停顿状态。顿状态。 直到直到1920年年, 科尼格科尼格(Konig)攥写了许多图论方面的论文攥写了许多图论方面的论文, 在在1936 年科尼格年科尼格(Konig)发表了第一本图论书籍有限图发表了第一本图论书籍有限图与无限图理论，总结了与无限图理论，总结了200年来图论研究的主要成果。年来图论研究的主要成果。 此后的此后的50年，图论经历了一场爆炸性的发展，年，图论经历了一场爆炸性的发展，成为数学科学中一门独立的学科。成为数学科学中一门独立的学科。 主要分支有图论、超图理论、极值图论、算法主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。图论、网络图论和随机图论等。 几十年来图论在理论上和应用上都得到很大的几十年来图论在理论上和应用上都得到很大的发展发展,特别是在近特别是在近30多年来由于计算机的广泛应多年来由于计算机的广泛应用而又得到飞跃的发展。用而又得到飞跃的发展。 在计算机科学、运筹学、化学、物理和社会科在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。机网络等方面都有广泛的应用。 这里主要讨论图的基本概念和算法，为今后的这里主要讨论图的基本概念和算法，为今后的学习和研究打下基础。学习和研究打下基础。5.1 引言引言 一、图的定义：一、图的定义： 在集合论中离散对象之间的关系可以用关在集合论中离散对象之间的关系可以用关系图来描述系图来描述,这种图就是图论中所述的有向这种图就是图论中所述的有向图。图。 定义定义5.1：设：设V是一个非空集是一个非空集,E是是V上的二元上的二元关系关系,称有序对称有序对(V, E)为为有向图有向图,记为记为G=(V,E) 或或G(V,E)。V中的元素称为中的元素称为顶点顶点(或点或点),V称称顶点集顶点集。E是是VV的子集的子集,E中的元素是有中的元素是有序对序对,称为称为弧弧,E称为称为弧集弧集。 例如有向图例如有向图G=(V,E),V=a,b,c,d,e,f,g, E=(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e), (f,f), 弧弧(a,b)表示从顶点表示从顶点a到顶点到顶点b的一条带箭头的线。的一条带箭头的线。对于弧对于弧(a,b)来讲来讲,在关系中在关系中a称称为有序对中的第一个元素为有序对中的第一个元素,b称称为第二个元素。为第二个元素。在图论中，称在图论中，称a为起点，为起点，b为终为终点。点。称称a与弧与弧(a,b)关联，关联，b与弧与弧(a,b)关联。关联。弧弧(c,c),(f,f)这种起点与终点相这种起点与终点相同的弧就称为自环。同的弧就称为自环。在图中，在图中，g与与E中任何元素中任何元素(弧弧)都不关联，称为孤立点。都不关联，称为孤立点。 定义定义5.2：顶点：顶点a和和b称为弧称为弧(a,b)的的端点端点,a为为起点起点,b为为终点终点。称。称a和和b与弧与弧(a,b)关联关联。若顶点若顶点a和和b相同相同,则对应的弧则对应的弧(a,b)称为称为自自环环。若。若V中某顶点与中某顶点与E中任何弧都不关联中任何弧都不关联, 则该顶点称为则该顶点称为孤立点孤立点。与一条弧相关联。与一条弧相关联的两个顶点称为的两个顶点称为邻接邻接的或的或相邻相邻的。一顶的。一顶点关联于几条弧点关联于几条弧,称这些弧是称这些弧是弧邻接弧邻接或或弧弧相邻相邻。例如上图中例如上图中a与与b相邻相邻;c与与d相邻相邻;(a,b)与与(b,c)弧相邻。弧相邻。 在研究有向图时在研究有向图时,只考察它的顶点与弧的连接关只考察它的顶点与弧的连接关系以及整个图形所具有的性质。至于各顶点之系以及整个图形所具有的性质。至于各顶点之间的相对位置及弧的长短曲直都是无关紧要的。间的相对位置及弧的长短曲直都是无关紧要的。 对于有向图，弧集中的元素都是有序对，若改对于有向图，弧集中的元素都是有序对，若改成无序对，则就是下面介绍的无向图。成无序对，则就是下面介绍的无向图。 定义定义5.3：设：设V是一个非空集是一个非空集,E是以是以V中两中两个元素组成的多重集为元素的集合个元素组成的多重集为元素的集合, 称有称有序对序对(V,E)为为无向图无向图,也记为也记为G=(V,E)或或G(V,E)。V中的元素称为中的元素称为顶点顶点或或点点,V称为称为顶点集顶点集, E中的元素称为中的元素称为边边,E称为称为边集边集。 E中元素现在也是集合，由于可能出现中元素现在也是集合，由于可能出现a,a这种情况，所以说这种情况，所以说E中元素是中元素是V中两个元中两个元素组成的多重集。素组成的多重集。该图的该图的V=v1,v2,v3,v4,v5,v6，E=v1,v2,v1,v5,，v2,v2, v2,v3,v2,v4,v2,v5,v2,v5,v3,v4,v4,v5，边边v1,v2关联于顶点关联于顶点a,b，而而v2,v2这种关联的两个顶点是相同的称为自环。这种关联的两个顶点是相同的称为自环。而而v6不关联任何边，也称为孤立点。不关联任何边，也称为孤立点。顶点顶点v4同时关联边同时关联边v2,v4,v3,v4,v4,v5，称这些边为边邻接另外称这些边为边邻接另外在上图中，边在上图中，边v2,v5出现了两次，象这种两个顶点之间出现不止出现了两次，象这种两个顶点之间出现不止一条的边称为多重边。一条的边称为多重边。 定义定义5.7：若图：若图G=(V,E)中中, 连结两个顶点连结两个顶点之间的边可以不止一条这些边称为之间的边可以不止一条这些边称为多重多重边边,则图则图G称为称为多重图多重图。无自环的非多重。无自环的非多重图称为图称为简单图简单图。边集为空集的图称为。边集为空集的图称为零零图图。只有一个顶点的图称为。只有一个顶点的图称为平凡图平凡图。若。若G中每两个顶点之间恰有一条边中每两个顶点之间恰有一条边, 则称则称G为为完全图完全图。n个顶点的完全图记为个顶点的完全图记为Kn。 在定义在定义5.7 中中,零图是指没有边的图零图是指没有边的图,其每其每个顶点为孤立点个顶点为孤立点,但顶点集但顶点集V不能是空集。不能是空集。 同样在有向图中，也可定义多重弧，多同样在有向图中，也可定义多重弧，多重有向图和简单有向图。重有向图和简单有向图。 为了叙述方便起见为了叙述方便起见,简称无向图为简称无向图为图图,如果如果在图在图(有向图有向图)中顶点标以名称中顶点标以名称,如上图中顶如上图中顶点标点标a,b,c,d,e,f,g,这样的图这样的图(有向图有向图)称为称为标标定图定图(有向图有向图),否则称为非标定图否则称为非标定图(有向图有向图)。下面主要考虑标定图。下面主要考虑标定图。 如果一个图的顶点集和边集是有限的如果一个图的顶点集和边集是有限的,则称则称该图为该图为有限图有限图, 类似地定义类似地定义有限有向图有限有向图。我们这里讨论的图和有向图是指有限图和我们这里讨论的图和有向图是指有限图和有限有向图。有限有向图。 图图(有向图有向图)的最本质的内容就是顶点与边的最本质的内容就是顶点与边(弧弧)的关联关系。为了描述这一关系的关联关系。为了描述这一关系,现在现在引进一个重要的概念引进一个重要的概念, 即顶点的度数。即顶点的度数。 二、顶点度数二、顶点度数 定义定义5.4：设：设G=(V,E)是一个图是一个图,顶点顶点v所关所关联的边数联的边数(有自环情况要计算两次有自环情况要计算两次), 称为称为顶点顶点v的的度数度数,记为记为d(v)。度数为度数为1的顶点的顶点称为称为悬挂点悬挂点。度数为奇。度数为奇(偶偶)数的顶点称为数的顶点称为奇奇(偶偶)顶点顶点。图。图G中顶点的最小度数记为中顶点的最小度数记为 (G), (G)=minv Vd(v),简记为简记为 。 在这里要注意：在这里要注意： 对于边对于边a,b,在计算顶点在计算顶点a的度数和的度数和b的度的度数时分别都被用了一次，因此对于自环，数时分别都被用了一次，因此对于自环，此时此时b=a,a,a,同样要统计两次。同样要统计两次。 证明：对每条边来讲，有两个端点，证明：对每条边来讲，有两个端点， 在计算顶点度数时，每条边被计算了两在计算顶点度数时，每条边被计算了两次次(极端情况，自环，同一端点同样算了极端情况，自环，同一端点同样算了两次两次)， 所以图中所有顶点度数之和为边数的两所以图中所有顶点度数之和为边数的两倍。倍。定理5.1:evdnii2)(1 定理定理5.2:奇顶点有偶数个。奇顶点有偶数个。 定义定义5.5：设：设G是一个有向图是一个有向图, 以顶点以顶点v为起为起点的弧数称为点的弧数称为v的的出度出度,记为记为d+(v);以顶点以顶点v为终点的弧数称为为终点的弧数称为v的的入度入度,记为记为d-(v)。 对于有向图对于有向图G中任一顶点中任一顶点v,d+(v)+d-(v)称为称为顶点顶点v的度数的度数,也记为也记为d(v)。 作为弧，有进必有出，有出必有进，两作为弧，有进必有出，有出必有进，两者平衡者平衡 定理定理5.3:在有向图中在有向图中,所有顶点的入度之和等于所有顶点的入度之和等于所有顶点的出度之和。所有顶点的出度之和。 证明略。证明略。 三、同构三、同构 一个有向图的弧以及弧所关联的顶点位置变动一个有向图的弧以及弧所关联的顶点位置变动后后,可以画出许多不同的图形和形状。可以画出许多不同的图形和形状。例如图的例如图的(a)和和(b) 这两个有向图这两个有向图,粗看起来是不同的粗看起来是不同的, 但但仔细观察以后仔细观察以后,发现顶点之间一一对应发现顶点之间一一对应,即即aD, bB,cA,dE; 弧之间也一一对应弧之间也一一对应,即即(a,b)(D,B), (a,c)(D,A),，即这两个有向图除顶点所标名称不同即这两个有向图除顶点所标名称不同外外,其结构相同其结构相同,顶点数相同顶点数相同,弧数相同弧数相同,并且顶点与弧的并且顶点与弧的关联关系保持不变关联关系保持不变,通常说这两个有向图是同构的。通常说这两个有向图是同构的。 定义定义5.6：设：设G=(V,E)和和G=(V,E)是两个有向图是两个有向图,若若存在双射存在双射 :VV以及双射以及双射 :EE,使得对任何使得对任何u,v V,(u,v) E, 有有 (u,v)=( (u), (v),称称G和和G是是同构同构的的,记为记为G G。 类似可以定义两个无向图的同构概念。类似可以定义两个无向图的同构概念。 图图5.4中两个图同构中两个图同构, 即著名的彼得森即著名的彼得森(Petersen)图。图。该图的每个顶点度数均为该图的每个顶点度数均为3, 称为称为3-正则图。正则图。一般一般, 若图的每个顶点度数均为若图的每个顶点度数均为r, 则称为则称为r-正则图正则图。 研究同构的好处是，对于几个同构的图只要研究同构的好处是，对于几个同构的图只要研究其中一个图的性质，其他几个图的性质研究其中一个图的性质，其他几个图的性质也就知道了。事实上同构关系是一个等价关也就知道了。事实上同构关系是一个等价关系。系。 定义定义5.8：设：设V是顶点集是顶点集,E是边集是边集,f是是V到实到实数的函数数的函数,g是是E到实数集的函数到实数集的函数,称有序三元称有序三元组组G=(V,E,f)或或 G=(V,E,g)，以及有序四元组以及有序四元组G=(V,E,f,g)为为带权图带权图。 例 如 下 图 就 是 边 上 带 权 为例 如 下 图 就 是 边 上 带 权 为 g 的 带 权 图的 带 权 图G=(V,E,g),以后主要讨论边上带权的带权图以后主要讨论边上带权的带权图 在有向图中类似可以定义带权有向图。在有向图中类似可以定义带权有向图。 四、子图四、子图 在讨论图的性质时研究图的局部结构是相当重在讨论图的性质时研究图的局部结构是相当重要的要的,现介绍子图的概念。现介绍子图的概念。 定义定义5.9：设有图：设有图G=(V,E),若在图若在图G=(V,E)中中,V V,E E且且E中边所关联的顶点在中边所关联的顶点在V中中,则称则称G为为G的的子图子图。若。若V=V, E E,则子图则子图G=(V,E)称为图称为图G的一个的一个生成子图生成子图。 定义定义5.10：设有图：设有图G=(V,E),设设E E ,以以E为边集为边集,E中边的端点全体为顶点集中边的端点全体为顶点集, 构成构成的子图称为的子图称为由由E导出的导出的G的子图的子图, 记为记为G(E),又称为又称为G的的边导出子图边导出子图。设。设V V,以以V为顶点集为顶点集, 端点均在端点均在V中所有边的全中所有边的全体为边集体为边集,构成的子图称为构成的子图称为由由V导出的导出的G的子图的子图,记为记为G(V),又称为又称为G的的导出子图导出子图 例如图例如图(d)是由是由G的边的边v1,v2,v2,v4,v4,v5导出的子图导出的子图J, (e)是由是由G的顶点的顶点v1,v2,v4,v5导出的子图导出的子图H。定义 5.11:设 G=(V,E)是 n 个顶点的任意简单图, 从完全图 Kn中删去G的所有边,但保留顶点集V所得到的图称为G的 补图,记为G,简称为 G 的补。 简单图简单图G=(V,E)的补图是一个以的补图是一个以V为顶点为顶点集的简单图集的简单图, 中两个顶点相邻当且仅当这中两个顶点相邻当且仅当这两个顶点在两个顶点在G中不相邻。中不相邻。 从图从图 G 中删去一个顶点中删去一个顶点v及其关联的边得及其关联的边得到的子图到的子图, 记为记为G-v, 或或G-v。从图从图G中删中删去一边去一边e得到的子图记为得到的子图记为G-e,如图所示。如图所示。5.2路与回路路与回路 一、路径一、路径,链链,路路 定义定义5.12：图：图G的一个有限点边交替序列的一个有限点边交替序列(v0,e1,v1,e2, em,vm)，使得对使得对1im,ei的端的端点是点是vi - 1和和vi,称该序列为一条称该序列为一条路径路径。边。边e1,e2,em互不相同的路径称为互不相同的路径称为链链。m称为称为该链的长度。顶点都不相同的该链的长度。顶点都不相同的链链称为称为路路,m称为该路的长度。称为该路的长度。v0=vm的路径的路径(或链或链)称为称为闭路径闭路径(或或闭链闭链)。除首尾两点外其余顶点都。除首尾两点外其余顶点都不相同的不相同的闭链闭链称为称为回路回路。长度为偶。长度为偶(奇奇)数的数的路或回路称为路或回路称为偶偶(奇奇)路路或或偶偶(奇奇)回路回路。 例如图中例如图中 (v2,e6,v5,e7,v2,e8,v4,e4,v5,e7,v2,e1,v1)是一条是一条v2到到v1的路径的路径; (v2,e6,v5,e7,v2,e1,v1)是一条是一条v2到到v1的路径，由于边不重复，的路径，由于边不重复，所以是链所以是链; (v2,e8,v4,e4,v5,e5,v1)是一条是一条v2到到v1的路径，边不重复，所的路径，边不重复，所以是链，又因为点也不重复，所以是一条路。以是链，又因为点也不重复，所以是一条路。有时点边交替序列可用边序列或有时点边交替序列可用边序列或点序列代替。点序列代替。在图中在图中(v2,e6,v5,e7,v2,e8,v4, e4,v5,e7,v2)是一条闭路径是一条闭路径;(v1,e1,v2,e6,v5,e7,v2,e8,v4,e4,v5,e5,v1)是一条闭路径，由于边不重复，是一条闭路径，由于边不重复，是一条闭链是一条闭链;(v1,e1,v2,e8,v4,e4,v5,e5,v1)是一条闭是一条闭路径，由于边不重复，是一条闭路径，由于边不重复，是一条闭链，除首尾两点外，点不重复，链，除首尾两点外，点不重复，是回路。是回路。(v2,e6,v5,e7,v2)也是回路。也是回路。 一条路也是一条链一条路也是一条链,一条回路也是一条闭链一条回路也是一条闭链,并且自环和两条多重边都自成一条回路并且自环和两条多重边都自成一条回路 一条回路上每个顶点的度数为一条回路上每个顶点的度数为2 ,一条路除一条路除起点和终点外起点和终点外, 每个顶点的度数也为每个顶点的度数也为2。 定理定理5.4：若图：若图G中每个顶点度数至少为中每个顶点度数至少为2,则则G包含一条回路。包含一条回路。 证明：若图证明：若图G包含自环或多重边包含自环或多重边,则定理结论显则定理结论显然成立然成立(a,e,a),或或(a,e,b,e,a)。 下面假设图下面假设图G是简单图是简单图 二、连通与连通图二、连通与连通图 定义定义5.14：设：设u和和v是图是图G的两个不同的顶的两个不同的顶点点,若若u和和v之间存在一条路之间存在一条路,则称则称顶点顶点u和和v是连通的是连通的。若图。若图G中任何两个不同顶点中任何两个不同顶点之间存在一条路之间存在一条路,则称则称G为为连通图连通图,否则称否则称G为为 不连通图不连通图。上面图是连通图，上面图是连通图，而下面图因为而下面图因为v1到到v8之间没有路，之间没有路，即即v1与与v8不连通，所以不是连通图不连通，所以不是连通图把把V划分为非空子集划分为非空子集V1,V2,V,使使得得u和和v属于同一子集属于同一子集Vi当且仅当当且仅当u和和v是连通的。是连通的。每个顶点子集每个顶点子集Vi的导出子图的导出子图Gi称为称为G的一个的一个连通分支连通分支,简称简称分支分支。G有有个分支个分支:G1,G2,G。当。当=1时时,G为为连通图。连通图。例如下图中例如下图中G有三个分支。有三个分支。 例：若图例：若图G中恰有两个顶点度数为奇数中恰有两个顶点度数为奇数,则这两则这两个顶点之间必有一条路。个顶点之间必有一条路。 说明：恰有表示有且仅有。说明：恰有表示有且仅有。 证明证明:(1)若若G为连通图为连通图, 结论显然成立。因为连结论显然成立。因为连通图中任何两点都连通。通图中任何两点都连通。 (2)若若G不连通不连通,则有若干个连通分支，则有若干个连通分支， 分两个奇顶点在不同连通分支分两个奇顶点在不同连通分支Gi,Gj和在同一个和在同一个连通分支进行讨论连通分支进行讨论作业：作业：P1121,4,5,6(1),7,8,9,10,12,13,14,15,17