离散数学图论部分.ppt

第四部分第四部分第四部分第四部分 图论图论图论图论1图论问题的起源图论问题的起源 1818世纪东普鲁士哥尼斯堡被普列戈世纪东普鲁士哥尼斯堡被普列戈尔河分为四块尔河分为四块,它们通过七座桥相互连接它们通过七座桥相互连接,如下图如下图.当时该城的市民热衷于这样一个当时该城的市民热衷于这样一个游戏游戏:“:“一个散步者怎样才能从某块陆地一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发出发，经每座桥一次且仅一次回到出发点？点？”SNAB2 陆地陆地 岛屿岛屿 岛屿岛屿 陆地陆地哥尼斯堡七桥问题哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？如何不重复地走完七桥后回到起点？。A AB BCD D3当当时时人人们们热热衷衷于于这这样样的的游游戏戏：设设想想从从任任一一个个地地方方出出发发通通过过每每座座桥桥一一次次且且仅仅一一次次后后回回到到原原地地,这是否可能这是否可能?但多次实践都发现不行。但多次实践都发现不行。1727 年年欧欧拉拉的的朋朋友友向向欧欧拉拉提提出出了了这这个个问问题题是是否否有解？有解？1736 年年欧欧拉拉用用图图论论的的方方法法解解决决了了这这个个问问题题,写写了第一篇图论的论文了第一篇图论的论文,成为图论的成为图论的创始人创始人。后来称此问题为后来称此问题为哥尼斯堡七桥问题哥尼斯堡七桥问题。4但在此之后但在此之后100年间，没有大的进展。年间，没有大的进展。直到直到Kirchhoff(克希霍夫克希霍夫)用树的理论解决了电用树的理论解决了电网络问题。这些结果引起了人们的重视网络问题。这些结果引起了人们的重视,图论图论的研究进入了一个发展时期。的研究进入了一个发展时期。直到直到1920年年,科尼格科尼格(Konig)撰写了许多图论方撰写了许多图论方面的论文。在面的论文。在1936年科尼格年科尼格(Konig)发表了第发表了第一本图论书籍有限图与无限图理论一本图论书籍有限图与无限图理论,总结总结了了200年来图论研究的主要成果。年来图论研究的主要成果。此后的此后的50年年,图论经历了一场爆炸性的发展图论经历了一场爆炸性的发展,成为数学科学中一门独立的学科。成为数学科学中一门独立的学科。5几十年来图论在理论上和应用上都得到很几十年来图论在理论上和应用上都得到很大大 的发展的发展,特别是在近特别是在近30多年来由于计算多年来由于计算机的广泛应用而又得到飞跃的发展。机的广泛应用而又得到飞跃的发展。在在计算机科学、运筹学、化学、物理和社计算机科学、运筹学、化学、物理和社会科学会科学等方面都取得了不少成果，对计算等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应工智能和计算机网络等方面都有广泛的应用。用。这里主要讨论这里主要讨论图的基本概念和算法图的基本概念和算法,为今后为今后的学习和研究打下基础。的学习和研究打下基础。6 本本章章首首先先给给出出图图、简简单单图图、完完全全图图、子子图图、路路和和图图的的同同构构等等概概念念，接接着着研研究究了了连连通通图图性性质质和和规规律律，给给出出了了邻邻接接矩矩阵阵、可可达达性性矩矩阵阵、连连通通矩矩阵阵和和完完全全关关联联矩矩阵阵的的定定义义。最最后后介介绍绍了了欧欧拉图与哈密尔顿图。拉图与哈密尔顿图。7图的定义图的定义89例例 画出下列图形。画出下列图形。(1)G=,其中其中V=v1,v2,v3,v4,v5,(2)E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(3)(v1,v5),(v2,v5),(v4,v5)。v v1 1v v2 2v v3 3v v4 4v v5 5e e1 1e e2 2e e3 3e e4 4e e5 5e e6 610例：例：画出下列图形。画出下列图形。(2)D=,(2)D=,其中其中V=vV=v1 1,v,v2 2,v,v3 3,v,v4 4,E=v E=,v ,。v v1 1v v2 2v v3 3v v4 4e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e7 711图相关的概念和规定图相关的概念和规定设设 G=为一有向图或无向图。为一有向图或无向图。(1)V、E分别表示分别表示G的的顶点集顶点集、边集边集，|V|、(2)|E|分别表示分别表示G的顶点数、边数。若的顶点数、边数。若|V|=n,(3)则称则称G为为n阶图阶图。(2)若若|V|、|E|均为有限数，则称均为有限数，则称G为为有限图有限图 这是本书讨论的重点。这是本书讨论的重点。(3)在图在图G中，若中，若E=,则称则称G为为零图零图。此时。此时 若若|V|=n，则称则称 G 为为n阶零图阶零图，记作，记作 Nn。若若|V|=1，则称则称 G 为为平凡图平凡图。12(a)图图(b)零图零图(c)完全图完全图l 没有任何边的图称为没有任何边的图称为零图零图；l 只有一个点，没有边的图称为只有一个点，没有边的图称为平凡图平凡图；l 任意两点之间都有边的图称为任意两点之间都有边的图称为完全图完全图。13v1v2v3v4v5e1e2e3e4e5e6在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为条，则称这些边为平行边平行边，平行边的条数称，平行边的条数称为为重数重数。例：例：下图中下图中 e4 与与 e5 是平行边。是平行边。14v1v2v3v4v5e2e3e4e5e6e7e8 在有向图中，关联一对顶点的有向边如果多在有向图中，关联一对顶点的有向边如果多于于1 1条，并且这些边的始点与终点相同条，并且这些边的始点与终点相同(即方向相即方向相同同)，则称这些边为，则称这些边为平行边平行边。例例：下图中：下图中e e3 3与与e e4 4是平行边是平行边,e,e7 7与与e e8 8不是平行边不是平行边（因为因为e e7 7与与e e8 8方向不同方向不同）15含平行边的图称为含平行边的图称为多重图多重图；既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图。本书主要讨论本书主要讨论简单图简单图的相关结论。的相关结论。16设设G=为无向图，为无向图，ek=E,则称则称vi,vj为为ek的端点，的端点，ek与与vi或或ek与与vj是是彼此关联彼此关联的。的。无边关联的顶点称为无边关联的顶点称为孤立点孤立点。若一条边所关。若一条边所关联的两个顶点重合，则称此边为联的两个顶点重合，则称此边为环环。vivj，则称则称ek与与vi或或ek与与vj的的关联次数关联次数为为1，若若vi=vj，则称则称ek与与vi的关联次数为的关联次数为2；若；若vi不是不是ek的端点，则称的端点，则称ek与与vi的关联次数的关联次数0。17设设G=为无向图，为无向图，vi,vjV,ek,elE,(1)若存在一条边若存在一条边e以以vi,vj端点，即端点，即e=(vi,vj)则称则称vi与与vj是是彼此相邻彼此相邻的。简称的。简称相邻的。相邻的。(2)(2)若若ek与与el至少有一个公共端点，则称至少有一个公共端点，则称ek与与el 是是彼此相邻的。彼此相邻的。简称简称相邻相邻的。的。设设D=为有向图为有向图,vi,vjV,ek,elE,若若ek=,除称除称vi,vj是是ek的端点外，还称的端点外，还称vi为为ek的的起点起点，vj为为ek的的终点终点，并称，并称vi邻接到邻接到vj,vj 邻邻接于接于vi。18顶点的度顶点的度 设设G=为一无向图，为一无向图，viV,称称vi作为作为边的端点的次数之和为边的端点的次数之和为vi的的度数度数，简称为，简称为度度，记作记作deg(vi)（或（或d(vi)）。）。设设D=为一有向图，为一有向图，vjV,称称vj作为作为边的始点的次数之和边的始点的次数之和,为为vj的的出度出度，记作，记作d+(vj);称称vj作为边的终点的次数之和作为边的终点的次数之和,为为vj的的入度入度，记，记作作d-(vj);称称d+(vj)+d-(vj)为为vj的的度数度数，记作，记作d(vj)。称度数为称度数为1的顶点为的顶点为悬挂顶点悬挂顶点,它所对应的它所对应的边为边为悬挂边悬挂边。19例例：在上图在上图(1)中中,d(v1)=4,d(v2)=4,d(v5)=0,在图在图(2)中中,d+(v1)=2,d-(v1)=1,d(v1)=3 d+(v2)=1,d-(v2)=3,d(v2)=4,v1v2v3v4v5e1e2e3e4e5e6(1)(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)(2)20在无向图在无向图G中中,令令 (G)=maxd(v)|vV(G);(G)=mind(v)|vV(G)称称(G)和和 (G)分别为分别为G的的最大度最大度和和最小度最小度。在有向图在有向图D中中,可类似定义可类似定义(D)、(G)。另外。另外,令令 +(G)=maxd+(v)|vV(D)+(G)=mind+(v)|vV(D)-(G)=maxd-(v)|vV(D)-(G)=mind-(v)|vV(D)分别为分别为D的的最大出度、最小出度、最大入度、最最大出度、最小出度、最大入度、最小入度小入度。简记作。简记作、+、+、-、-。21v1v2v3v4v5e1e2e3e4e5e6(1)(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)(2)例例 在上图在上图(1)中中,最大度最大度=6,最小度最小度=0,在图在图(2)中中,最大度最大度=4,最小度最小度=2,最大出度最大出度+=4,最大入度最大入度-=3 最小出度最小出度+=1,最小入度最小入度-=0。22握手定理握手定理 设设G=为无向图或有向图，为无向图或有向图，V=v1,v2,vn,|E|=m(m为边数为边数)则则证明证明：G G中每条边（包括环）均提供中每条边（包括环）均提供2 2个端点，故在个端点，故在计算各顶点度数的和时，每条边均提供计算各顶点度数的和时，每条边均提供2 2度，度，m m条边条边共提供共提供2m2m度。度。=2m。即每个顶点度数之和等于即每个顶点度数之和等于边数的边数的2 2倍。倍。推论推论 在任何图在任何图G=V,E 中，度数为奇数的结中，度数为奇数的结点必为偶数个。点必为偶数个。23 设设G=V,E 是是有有向向图图，v V，射射入入(出出)结结点点v的的边边数数称称为为结结点点v的的入入(出出)度度。记记为为deg(v)(deg(v)。显显然然，任任何何结结点点的的入入度度与与出出度度的的和和等等于于该该结结点点的的度度数数，即即deg(v)=deg(v)+deg(v)。定定理理：在在有有向向图图中中，所所有有结结点点入入度度的的和和等等于于所所有结点出度的和。有结点出度的和。证证明明：在在有有向向图图中中每每一一条条边边对对应应一一个个入入度度和和一一个个出出度度，为为图图的的入入度度和和出出度度各各增增加加1。所所以以，所所有有结结点点入入度度的的和和等等于于边边数数，所所有有结结点点出出度的和也等于边数。度的和也等于边数。24 设设V=v1,v2,vn为图的顶点集，称为图的顶点集，称(d(v1),d(v2),d(vn)为为G的的度数序列。度数序列。例：例：在下图中的度数序列为（在下图中的度数序列为（4,4,3,1,0)。v1v2v3v4v5e1e2e3e4e5e625例例 (3,3,2,3),(5,2,3,1,4)(3,3,2,3),(5,2,3,1,4)能成为图的能成为图的 度数序列吗？为什么？度数序列吗？为什么？已知图已知图G G中有中有1010条边条边,4,4个个3 3度顶点度顶点,其其 余顶点的度数均不大于余顶点的度数均不大于2,2,问问G G中至少中至少 有多少个顶点有多少个顶点?为什么为什么？解解:由于这两个序列中由于这两个序列中,奇数个数均为奇数奇数个数均为奇数,它们都不能成为图的度数序列。它们都不能成为图的度数序列。图中边数图中边数m=10,m=10,由握手定理可知由握手定理可知,G,G中各顶中各顶 点度数之和为点度数之和为2020，4 4个个3 3度顶点占去度顶点占去1212度，度，还剩还剩8 8度若其余全是度若其余全是2 2度顶点度顶点,还需要还需要4 4个顶个顶 点来占用这点来占用这8 8度，所以度，所以G G至少有至少有8 8个顶点。个顶点。26如：如：K3K6Kn的边数为的边数为的边数为的边数为m=Cm=Cn n2 2=n(n-1)/2=n(n-1)/2完全图完全图 设设G为为n阶无向简单图，若阶无向简单图，若G中每个顶点均与其余中每个顶点均与其余的的n-1个顶点相邻，则称个顶点相邻，则称G为为n阶阶无向完全图无向完全图，简称，简称n阶阶完全图，记作完全图，记作Kn(n1)。27如：如：如：如：3 3阶有向完全图阶有向完全图n阶有向完全图的边数阶有向完全图的边数m=n(n-1）。有向完全图有向完全图 设设D D为为n n阶有向简单图，若阶有向简单图，若D D中每个顶点都邻接到其中每个顶点都邻接到其余的余的n-1n-1个顶点，又邻接于其余的个顶点，又邻接于其余的n-1n-1个顶点，则称个顶点，则称D D为为n n阶有向完全图阶有向完全图 。28正则图正则图 在一个无向简单图中，如果每个结点的在一个无向简单图中，如果每个结点的度数均为度数均为k k，则该图称为，则该图称为k-k-正则图正则图。下图所示的图称为彼得森（下图所示的图称为彼得森（PetersenPetersen）图，是）图，是3-3-正则图正则图。完全图是。完全图是n-1-n-1-正则图正则图。29如：如：(1)(1)(3)(3)补图补图 设设G=为为n阶无向简单图阶无向简单图,以以V为顶点集，为顶点集，以所有使以所有使G成为完全图成为完全图 Kn 的添加边组成的集合的添加边组成的集合为边集的图，称为为边集的图，称为G的的补图补图，记作，记作 G。(2)(2)30(1)(2)例：例：在下图中在下图中,(1)是是(2)的补图的补图,当然当然(2)也是也是(1)的补图的补图,就是说就是说,(1),(2)互为补图互为补图 同样同样,(3),(4)互为补图。互为补图。(3)(4)31子图与生成子图子图与生成子图 设设G=,G=为两个图为两个图(同时为无同时为无向图或有向图向图或有向图)，若，若V V且且E E，则称，则称G为为G的的子图子图，G为为G的的母图母图，记作，记作G G。若若G是是 G的子图，且的子图，且V V或或E E，则则称称G为为G的的真子图真子图。若若G是是G的子图，且的子图，且V=V，则称，则称G为为G的的生成子图生成子图。生成子图非常重要。生成子图非常重要。32导出子图导出子图 n V1 V且且V1,以以V1为顶点集为顶点集,以两端点均在以两端点均在V1中的全体边为边集的中的全体边为边集的G的子图的子图,称为称为V1导出的导出的导出子图导出子图，记为记为GV1。n E1 E且且E1,以以E1为边集为边集,以以E1中边关联的顶中边关联的顶点的全体为顶点集的点的全体为顶点集的G的子图的子图,称为称为E1导出的导出的导出导出子图子图,记为记为GE1。33例：例：在上图中，在上图中，G是母图，是母图，G1是是G的子图，且是的子图，且是真子图；真子图；G2是是G的生成子图；的生成子图；G3是由边子集是由边子集e4,e5的导出子图，记为的导出子图，记为G e4,e5;G3也是由结也是由结点子集点子集a,d,e的导出子图，记为的导出子图，记为G a,d,e;34(1)(1)abd dc ce1e2e3e4e5e6b bd dc ce3e e4 4e e5 5(2)(2)(3)(3)母图同时也是母图同时也是(1)(1)的生成子图。的生成子图。(2）是）是(1)子图、子图、真子图。真子图。（3）是（）是（1）的）的子图、真子图、子图、真子图、生成子图。生成子图。c ca ab bd de e3 3e e4 4e e5 5e e2 2例：例：判断下列各图的母子关系。判断下列各图的母子关系。35图的同构图的同构 设设G1=,G2=为两个无为两个无(有有)向图，若存在双射函数向图，若存在双射函数f:V1V2,于于 vi,vj V1,(vi,vj)E1(E1)(f(vi),f(vj)E2(E2)，并且，并且(vi,vj)()与与(f(vi),f(vj)()重数相同，则称重数相同，则称G1与是与是G2同构同构的，的，记作记作G1 G2。36换言之：换言之：两个图两个图G1=,G2=,如如果它们的节点间存在一一对应关系（双果它们的节点间存在一一对应关系（双射），而且这种对应关系也反映在表示射），而且这种对应关系也反映在表示边的结点对中边的结点对中(如果是有向边则对应的结如果是有向边则对应的结点对还保持相同的顺序点对还保持相同的顺序),则称此两图是则称此两图是同构同构的。的。两个图同构的判断非常困难，需要两个图同构的判断非常困难，需要仔细考察图的结点和边的关联关系。仔细考察图的结点和边的关联关系。37如何判断两个图是否同构呢？如何判断两个图是否同构呢？答案答案：迄今为止还没有有效的算法。：迄今为止还没有有效的算法。根据定义，根据定义，则我们得到两个图同构的必要条件：则我们得到两个图同构的必要条件：(1)结点数目相等；结点数目相等；(2)边数相等；边数相等；(3)度数相同的结点数目相同（度数序列相同）。度数相同的结点数目相同（度数序列相同）。注意：注意：但这仅仅是但这仅仅是G1 G2的必要条件的必要条件。两个图就。两个图就算这三点同时满足也不一定同构。算这三点同时满足也不一定同构。38(1)G(2)G例：例：在下图中在下图中,(1)和和(2)结点集的元素一一对结点集的元素一一对应应v1b,v2d,v3e,v4c,v5a;边集边集 (v1,v2)(b,d),(v2,v3)(d,e),(v3,v4)(e,c),(v4,v5)(c,a),(v5,v1)(a,b);度数相同的结点数目相同度数相同的结点数目相同 是同构的。是同构的。(3)-Gav3v1v2v4v5edcbv239abcdd1a1b1c1abcdd1a1b1c1abcdd1a1b1c1判断下列三个图是否同构？判断下列三个图是否同构？40上图中上图中G1和和G2同构，同构，G3和和G4同构。同构。41 。例例：试证下列两个有向图：试证下列两个有向图G1=和和 G2=同构？同构？abcd。v1G G1 1v2v3v4G G2 2证明证明:由图可知由图可知,V1=a,b,c,d 和和V2=v1,v2,v3,v4 令映令映射射 g:V1V2 即结点和边的对应关系分别为即结点和边的对应关系分别为:g(a)V1,g(b)V2,g(c)V3,g(d)V4,。显然。显然,映射映射g是双射是双射,G1和和 G2同构。同构。42 下图中（下图中（a)a)与（与（b b），（），（c c）与（）与（d d）分别顶点数相）分别顶点数相同、边数相同、度数序列都相同；但它们不同构。同、边数相同、度数序列都相同；但它们不同构。(c)(d)43图的简单操作图的简单操作设设G=为无向图为无向图(1)设设eE,用用G-e表示表示从从G中去掉边中去掉边e,称为称为删除边删除边e.又设又设E E,用用G-E 表示表示从从G中删除中删除E 中所有边，中所有边，称为删除称为删除E；(2)设设vV,用用G-v表示表示从从G中去掉中去掉v及所关联的一切边及所关联的一切边,称为称为删除顶点删除顶点v.又设又设V V,用用G-V 表示表示 从从G中删除中删除V 中所有顶点，中所有顶点，称为删除称为删除V 。44(3)设边设边e=(u,v)E,用用Ge表示从表示从G中去掉中去掉e后，后，将将e的两个端点的两个端点u,v 用一个新的顶点用一个新的顶点w(或用或用u或或v充当充当w)代替，代替，使使w关联关联e以外以外u,v关联的所有边，关联的所有边，称为称为边边e收缩收缩(4)设设u,vV,(u,v可能相邻也可能不相邻可能相邻也可能不相邻)，用用G(u,v)(或或G+(u,v)表示在表示在u,v之间加一条边之间加一条边(u,v),称为称为加新边加新边45图图GG-e5G-e1,e4例：例：46G-v5G-v4,v5,Ge547 通路与回路通路与回路设设G为无向标定图，为无向标定图，G中顶点与边的交替序列中顶点与边的交替序列=v0e1v1e2elvl称为称为v0到到vl的的通路（路）通路（路），其中其中vr-1,vr为为er的端点。的端点。r=1,2,l,v0,vl分别称为分别称为的起点与终点，的起点与终点，中边的条数中边的条数 l 称为它的称为它的长度长度。若若v0=vl，则称通路为则称通路为回路回路。若若的所有边各异，的所有边各异，则称则称为为简单通路简单通路，则称则称为为简单回路简单回路。又若又若v0=vl，48若若的所有顶点的所有顶点各异，各异，所有边也各异，所有边也各异，则称则称为为初级通路初级通路 或或路径路径，则称则称为为初级回路或圈。初级回路或圈。将长度为奇数的圈称为将长度为奇数的圈称为奇圈奇圈，长度为偶数的圈称为长度为偶数的圈称为 偶圈偶圈此时又若此时又若v0=vl，(除除v0与与vl可能相同外可能相同外)在初级通路与初级回路的定义中，在初级通路与初级回路的定义中，仍将初级回路看成初级通路仍将初级回路看成初级通路(路径路径)的特殊情况，的特殊情况，只是在应用中初级通路只是在应用中初级通路(路径路径)都是始点与终点不相同，都是始点与终点不相同，长为长为1的圈只能由环生成，的圈只能由环生成，长为长为2的圈只能由平行边生成，的圈只能由平行边生成，因而在简单无向图中，因而在简单无向图中，圈的长度至少为圈的长度至少为3若若中有边重复出现，中有边重复出现，则称则称为为复杂通路复杂通路，则称则称为为复杂回路。复杂回路。又若又若v0=vl，49在有向图中，在有向图中，通路、回路及分类的定义与无向图中非常类似，通路、回路及分类的定义与无向图中非常类似，只要注意有向边方向的一致性只要注意有向边方向的一致性在上述定义中，在上述定义中，将回路定义成通路的特殊情况，将回路定义成通路的特殊情况，即回路也是通路，即回路也是通路，又初级通路又初级通路(回路回路)是简单通路是简单通路(回路回路)，但反之不真但反之不真在简单图中也可以只用顶点序列表示通路在简单图中也可以只用顶点序列表示通路(回路回路)。可以先将非标定图标成标定图，可以先将非标定图标成标定图，为了写出非标定图中的通路为了写出非标定图中的通路(回路回路)，再写出通路与回路。再写出通路与回路。=v0v1vlv250定理定理在在n阶图阶图G中，中，若从顶点若从顶点v0到到vl(v0vl )存在通路，存在通路，则则v0到到vl 存在长度小于或等于存在长度小于或等于(n-1)的通路。的通路。证：证：设设为为G中一条长度为中一条长度为l 的通路，的通路，=v0e1v1e2elvl若若ln-1,则则 满足要求，满足要求，否则必有否则必有l+1n,即即上的顶点数大于上的顶点数大于G中的顶点数中的顶点数,必存在必存在k,s,0ksl,使得使得 vs=vk,即在即在上存在上存在 vs到自身的回路到自身的回路 Csk在在上删除上删除 Csk上的一切边上的一切边得得 =v0e1v1e2 vkes+1,elvl,仍为仍为v0到到vl的通路的通路,且长度至少比且长度至少比减少减少1.若若 还不满足要求还不满足要求,则则 重复上述过程，重复上述过程，由于由于G是有限图是有限图,经过有限步后经过有限步后,及除及除 vs外的一切顶点外的一切顶点,必得必得v0到到 vl存在长度小于或等于存在长度小于或等于(n-1)的通路。的通路。51推论推论：在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj(vivj)存在存在通路，则通路，则vi到到vj存在长度小于或等于存在长度小于或等于(n-1)的初的初级通路级通路(路径路径)。定理：定理：在在n阶图阶图G中，若存在从中，若存在从vi到自身的回路，到自身的回路，则一定存在则一定存在vi到自身度小于或等于到自身度小于或等于n的回路的回路推论推论：在在n阶图阶图G中，若存在从中，若存在从vi到自身的简单到自身的简单回路，回路，则一定存在则一定存在vi到自身度小于或等于到自身度小于或等于n的的初级回路。初级回路。52图的连通性图的连通性 一个无向图一个无向图(有向图忽略其方向有向图忽略其方向)G=,)G=,如果它的任何两点均是可达的如果它的任何两点均是可达的,则称图则称图G G为为连通连通图图，否则称为，否则称为非连通图非连通图。v1v2v3v5v4v1v2v3v4v5v6v1v2v3v4v5v6左图和中图均是连通图，但右图则是非左图和中图均是连通图，但右图则是非连通图，因为结点连通图，因为结点v v1 1,v,v2 2,v,v3 3与结点与结点v v4 4,v v5 5,v,v6 6间是不可达的。间是不可达的。53 在一个无向图在一个无向图G中，若从顶点中，若从顶点vi到到vj存在通存在通路路(当然从当然从vj到到vi也存在通路也存在通路),则称则称vi与与vj是是连通连通的的。规定。规定vi到自身总是到自身总是连通的连通的。在一个有向图在一个有向图D中，若从顶点中，若从顶点vi到到vj存在通路，存在通路，则称则称vi可达可达vj。规定。规定vi到自身总是到自身总是可达的。可达的。设设vj,vi为无向图为无向图G中任意两点中任意两点,若若vj与与vi是连是连通的通的,则称则称vj与与vi之间长度最短的通路为之间长度最短的通路为vj与与vi之之间的间的短程线短程线,并称为并称为vj与与vi之间的之间的距离距离,记作记作d,当当vj不可达不可达vi时，规定时，规定d=。54距离有以下距离有以下性质性质：1.d0，vj=vi时，等号成立。时，等号成立。2.在无向图中还有对称性在无向图中还有对称性:d(vj,vi)=d(vj,vi)3.满足三角不等式：满足三角不等式：d+dd55v3 。v1e4v2v4v5e1e3e5e6e7v3 。v1v2v4v5e1e3e5e6连连通通图图分分离离图图 若无向图若无向图G G是平凡图或是平凡图或G G中任何两个顶点都中任何两个顶点都是连通的，则称是连通的，则称G G为为连通图连通图，否则称，否则称G G为为非连通非连通图图或或分离图分离图。显然，一个图。显然，一个图G G是连通的，当且是连通的，当且仅当仅当G G中任意两点都是相连的。中任意两点都是相连的。56v3 。v1e4v2v4v5e1e3e5e6e7v3 。v1v2v4v5e1e3v3 。V1 v2133 无向图中无向图中,顶点之间的连通关系是顶点之间的连通关系是等价关系等价关系,设设G是一个无向图是一个无向图,R是是G中顶点之间的连通关系，中顶点之间的连通关系，按着按着R可将可将V(G)划分成划分成k(k1)个等价类，记成个等价类，记成V1,V2,Vk,由它们导出的导出子图由它们导出的导出子图GVi(i=1,2,k)称为称为G的的连通分支连通分支，连通分支数个数记为，连通分支数个数记为 。例例:下列图的连通分支数分别为下列图的连通分支数分别为:57设设D=D=为一个有向图。为一个有向图。若略去若略去D D中各有向边的方向后所得无向图中各有向边的方向后所得无向图G G是连通图是连通图,则称则称D D是是连通图连通图，或称，或称D D是是弱连通图弱连通图，简称为连通图。，简称为连通图。若若D D中任意两点至少一个可达另一个中任意两点至少一个可达另一个,则称则称D D是是单向连通图单向连通图。若若D D中任何一对顶点都是相互可达的中任何一对顶点都是相互可达的,则称则称D D是是强连通图强连通图。(1(1)(2(2)(3(3)(1)(1)为为强连通图强连通图,(2),(2)为为单向连通图单向连通图,(3),(3)为为弱连通图弱连通图58 一个有向图如果其任何两点间均是互相可一个有向图如果其任何两点间均是互相可达的则称图达的则称图G G是是强连通的强连通的；如果其任何两点间至；如果其任何两点间至少存在一向是可达的则称图少存在一向是可达的则称图G G是是单向连通的单向连通的；如；如果忽略边的方向后其无向边连通的则称图果忽略边的方向后其无向边连通的则称图G G是是弱弱连通的连通的。(1)(2)(3)(1)(1)为强连通图为强连通图 (2)(2)为单向连通图为单向连通图(3)(3)为弱连通图为弱连通图 (4)(4)为非连通图为非连通图(4)v1v2v3v1v2v3v1v2v3v1v2v359定定理理：一一个个有有向向图图G是是强强连连通通的的充充分分必必要要条条件件是是G中中有有一一个回路至少包含个回路至少包含G的每个结点一次。的每个结点一次。证证明明：设设G中中有有一一个个回回路路至至少少包包含含G的的每每个个结结点点一一次次，下证下证G是强连通的。是强连通的。G中中有有一一个个回回路路至至少少包包含含每每个个结结点点一一次次，则则G中中的的任任意两个结点通过回路互相可达。所以意两个结点通过回路互相可达。所以G是强连通的。是强连通的。设设G是是强强连连通通的的，下下证证G中中有有一一个个回回路路至至少少包包含含G的的每个结点一次。每个结点一次。若若不不然然，存存在在结结点点v不不在在G的的任任何何回回路路上上，则则v与与其其它它任任何何结结点点不不能能互互相相可可达达，这这与与G是是强强连连通通的的矛矛盾盾。故故G中中有一个回路至少包含有一个回路至少包含G的每个结点一次。的每个结点一次。定理：定理：一个有向图一个有向图G是单向连通的充分必要条是单向连通的充分必要条件是件是G中有一个路至少包含每个结点一次。中有一个路至少包含每个结点一次。证明略。证明略。60 设无向图设无向图 G=,若存在若存在V V,且且V,使得使得 ,而对于而对于V的的任意真子任意真子集集V，即，即V V,均有均有 ，则，则称称V是是 G 的的点割集点割集，若点割集中只有一个顶点，若点割集中只有一个顶点v，则称，则称v为为割点割点。v3v2v1v4v5v6v7e2e1e3e4e5e6e7e8e9 在右图中在右图中v3,v5,v2,v6,为点割集。为点割集。v4,v2不是不是点割集点割集,因为它的真子集因为它的真子集v2 已经是点割集了，类似已经是点割集了，类似地地,v1,v6也不是点割集。也不是点割集。61 设无向图设无向图G=,若存在若存在E E,且且E，使得使得 ，而对于，而对于E的任意的真的任意的真子集子集E,即即E E,均有均有 ,则称则称E是是G的的边割集边割集，或简称为，或简称为割集割集。若边割集中只。若边割集中只有一条边有一条边e,则称则称e为为割边割边或或桥桥。v3v2v1v4v5v6v7e2e1e3e4e5e6e7e8e9 在左图中在左图中e3,e4,e1,e2,e3,e1,e2,e4,e9等都是边割集等都是边割集,其中其中e9是是割边割边。e6,e7,e9不不是边割集是边割集,因为它的真子集因为它的真子集e9 已是割边集，类似地已是割边集，类似地,e6,e8,e1,e2,e5也不是割边集。也不是割边集。62 设设G=G=V,EV,E 是是无无向向连连通通图图，如如果果G G不不是是完完全全图图，k(G)=mink(G)=min|V|V1 1|V V1 1是是G G的的点点割割集集 称称为为图图G G的的点点连连通通度度。如如果果G G是是完完全全图图，规规定定n n阶阶无无向向完完全全图图K Kn n的的点点连连通通度度为为n1n1，即即k(Kk(Kn n)=n1)=n1。规定不连通图规定不连通图G G的点连通度为的点连通度为0 0。即。即k(G)=0k(G)=0。无向连通图的点连通度的物理意义是：要无向连通图的点连通度的物理意义是：要使使G G成为不连通的最少要删除的结点数。如果成为不连通的最少要删除的结点数。如果一个图的点连通度是一个图的点连通度是1 1，最少删除一个结点，最少删除一个结点，图变为不连通的。图变为不连通的。63 设设G=G=V,EV,E 是是无无向向连连通通图图，如如果果G G是是非非平平凡凡图图，(G)=min(G)=min|E|E1 1|E E1 1是是G G的的边边割割集集 称称为为G G的的边边连通度连通度。如如果果G G是是平平凡凡图图，规规定定G G的的边边连连通通度度为为0 0。规规定定不不连连通通图图G G的的边边连连通通度度为为0 0，即即(G)=0(G)=0。有有割割边边的图的边连通度是的图的边连通度是1 1。无无向向连连通通图图的的边边连连通通度度的的物物理理意意义义是是：要要使使G G成为不连通的最少要删除的边数。成为不连通的最少要删除的边数。64无无向向图图G的的点点连连通通度度k(G)、边边连连通通度度(G)和和最最小小度度 (G)有下列的关系：有下列的关系：定理：定理：设设G=V,E 为任意无向图，则为任意无向图，则k(G)(G)(G)证证明明：如如果果G是是不不连连通通的的，由由点点连连通通度度和和边边连连通通度的定义有度的定义有k(G)=(G)=0，所以，所以 k(G)(G)(G)如果如果G是连通图。是连通图。先证明先证明(G)(G)如果如果G是平凡图，是平凡图，(G)=0(G)，即，即(G)(G)如如果果G是是非非平平凡凡图图，设设n=(G)=min deg(v)|v V，则则存存在在G的的一一个个结结点点v，它它关关联联了了n条条边边，而而其其它它结结点点关关联联的的边边数数大大于于等等于于n，将将v关关联联的的这这n条条边边删删除除，G成成为为不不连连通通的的。从从而而这这n条条边边或或这这n条条边边中中的的几几条条边边组组成成一一个个边割集，即存在一个边割集的基数小于等于边割集，即存在一个边割集的基数小于等于n，所以，所以65 min|E 1|E 1是是G的的边边割割集集 n=min deg(v)|v V ，即即 (G)(G)再证再证k(G)(G)设设(G)=1，G有有一一条条割割边边，此此边边的的任任一一端端点点是是割割点点，k(G)=1。所以。所以k(G)(G)成立。成立。设设(G)2，则则可可删删除除某某(G)条条边边，使使G成成为为不不连连通通的的，而而删删除除其其中中的的(G)1条条边边，它它仍仍然然是是连连通通的的且且有有一一个个桥桥，设设该该桥桥为为e=(u,v)。对对这这(G)1条条边边选选取取一一个个不不同同于于u，也也不不同同于于v的的端端点点，把把这这些些端端点点删删除除，则则必必至至少少删删除除了了这这(G)1条条 边边。若若 这这 样样 产产 生生 的的 图图 是是 不不 连连 通通 的的，则则k(G)(G)1(G)。若若这这样样产产生生的的图图是是连连通通的的，则则e=(u,v)仍仍是是桥桥。此此时时再再删删除除u或或v，就就必必产产生生了了一一个个不不连连通通图，故图，故k(G)(G)。由由和和得得k(G)(G)(G)。66 下下图图是是无无向向连连通通图图，点点连连通通度度k(G)=1，边边连连通通度度(G)=2，最小度，最小度(G)=3，此图满足，此图满足k(G)(G)(G)。67例例：在在无无向向连连通通图图G中中，结结点点v是是割割点点的的充充分分必必要要条条件件是是存存在在两两个个结结点点u和和w，使使结结点点u和和w之之间间的的每每一一条条路路都通过都通过v。证证明明：设设v是是割割点点，证证明明存存在在两两个个结结点点u和和w，使使结结点点u和和w之间的每一条路都通过之间的每一条路都通过v。v是是割割点点，删删除除v得得G，G至至少少包包含含两两个个连连通通分分支支，设设其其中中的的两两个个为为G1=V1,E1 和和G2=V2,E2，u V1，w V2，因因为为G连连通通，在在G中中u和和w之之间间必必有有路路，设设L是是它它们们之之间间任任意意一一条条路路。在在G中中，由由于于u和和w属属于于两两个个不不同同连连通通分分支支，所所以以，u和和w之之间间必必没没有路。故有路。故L必通过必通过v。设设存存在在