ch图的基本概念.pptx

n如何找到物流运输的最优路径？n如何找到最优的网络通信线路？n如果你想周游全国所有城市，如何设计旅游线路？n化学化合物分析：结构是否相同？n程序结构度量：程序是否结构相似？n如何为考试分配教室，使得资源利用率最优？n如何安排工作流程而达到最高效率？n如何设计为众多的电视台频道分配最优方案？n如何设计通信编码以提高信息传输效率？n操作系统中,如何调度进程而使得系统效率最优？n如何设计集成电路线路布局而达到最优效率？n如何设计计算机鼓轮？n七枚同重量硬币与一枚较轻的伪币，使用天平秤多少次就能找出伪币？n如何设计下棋程序？nn-皇后问题n最少用几种颜色就能将世界地图都着色？n如何使箱子尽可能装满物体？n一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢？研究主题研究主题n旅行商问题：TSP问题n中国邮路问题n地图着色问题：四色定理n最短路径问题n网络流n匹配n组合计数主要内容主要内容 1)1)图的基本术语；图的基本术语；2)2)结点的度，子图，完全图；结点的度，子图，完全图；3)3)图的连通性；图的连通性；4)4)图的运算，图的矩阵表示及其性质；图的运算，图的矩阵表示及其性质；5)5)图的同构；图的同构；6)6)欧拉图与哈密尔顿图的性质及其应用。欧拉图与哈密尔顿图的性质及其应用。10.1 10.1 图论概述图论概述 图是人们日常生活中常见的一种信息载图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。图由一些点和连接这些点的线组成的结构。图论是有许多应用的古老学科，也一直以来都论是有许多应用的古老学科，也一直以来都是一个热门学科，它已经被广泛应用于计算是一个热门学科，它已经被广泛应用于计算机科学、化学、运筹学、心理学等很多领域。机科学、化学、运筹学、心理学等很多领域。10.2 10.2 图与图模型图与图模型 例例10.210.2 时时间间安安排排问问题题。某某大大学学计计算算机机学学院院的的某某教教研研组组共共有有1010名名教教师师，他他们们分分别别参参加加7 7个个班班级级的的讨讨论论课课，每每个个班班级级可可能能同同时时需需要要多多位位教教师师参参加加，有有的的教教师师可可能能需需要要参参加加多多个个班班级级的的讨讨论论，每每个个班班级级必必须须单单独独开开展展讨讨论论课课，则则如如何何安安排排才才使使得得所所有有班班级级在在最最短短时时间间段段内内完完成成讨讨论论课课？参参加加各各个个班班级级讨讨论论课课的的教教师师情情况况如下（如下（c ci i为班级编号，数字为班级编号，数字1-101-10为教师编号）：为教师编号）：c c1=1=1，2 2，33，c c2=1=1，3 3，4 4，55，c c3=2=2，5 5，6 6，77，c c4=2=2，6 6，77，c c5=4=4，7 7，8 8，99，c c6=8=8，9 9，1010，c c7=1=1，3 3，9 9，1010。10.2 10.2 图与图模型图与图模型 这样，一位教师如果给多个班级都授课，则在这样，一位教师如果给多个班级都授课，则在讨论课时间安排方面则不能冲突，如教师讨论课时间安排方面则不能冲突，如教师1 1不能同不能同时参加班级时参加班级c c1 1与班级与班级c c2 2的讨论课。这种情况可以用的讨论课。这种情况可以用下下图直观地表示。图直观地表示。在在上上图中，共用了图中，共用了7 7个小圆圈来表示班级，圆圈个小圆圈来表示班级，圆圈之间的线段表示存在同一个教师参加该二班级的讨之间的线段表示存在同一个教师参加该二班级的讨论课，这样就不能安排该二班级同时开展讨论课。论课，这样就不能安排该二班级同时开展讨论课。显然，这就给上述问题构建了一个直观的图的模型。显然，这就给上述问题构建了一个直观的图的模型。c c6c c5c c4c c2c c3c c7c c110.2 10.2 图与图模型图与图模型 定义定义10.110.1 图图G G包括一个非空的对象的集合包括一个非空的对象的集合V V与与有限的两个对象构成的有限的两个对象构成的V V的无序对构成的集合的无序对构成的集合E E，前者称为的，前者称为的结点集结点集，后者称为，后者称为边集边集。令令V=vV=v1 1,v,v2 2,v,vn n 是包含是包含n n个结点的集合，个结点的集合，其其m m条边的集合条边的集合E=eE=e1 1,e,e2 2,e,em m，其中，每一，其中，每一条边都是集合条边都是集合V V的二元子集，如边的二元子集，如边e ei i=u=u，vv，常常简记为，常常简记为uvuv或或vuvu，其中，其中u u、v v称为边称为边uvuv的的端点端点。这样，一个图事实上就是。这样，一个图事实上就是V V与与E E构成的构成的序偶，常常被记作序偶，常常被记作G=(V,E)G=(V,E)。于是，也常常用。于是，也常常用V(G)V(G)和和E(G)E(G)来表示某一个图来表示某一个图G G的结点集与边集。的结点集与边集。当然，也可以使用其它符号来表示图，如用当然，也可以使用其它符号来表示图，如用F F或或H H，甚至，甚至G G1 1等等。等等。10.2 10.2 图与图模型图与图模型 集合集合V(G)V(G)的基数的基数n n表示表示图图G G的阶的阶（OrderOrder），集合），集合E(G)E(G)的基数的基数m m表示表示图图G G的规模的规模（SizeSize），有时也将图），有时也将图G G记作记作(n,m)(n,m)。在图。在图G G中，若边集中，若边集E(G)=,E(G)=,则称则称G G为为零图零图（Null GraphNull Graph），此时，又若），此时，又若G G为为n n阶图，则称阶图，则称G G为为n n阶零图阶零图，记作，记作N Nn n，特别地，称，特别地，称N N1 1为为平凡图平凡图（Trivial Trivial graphgraph）。在图的定义中规定结点集）。在图的定义中规定结点集V V为非空集，但为非空集，但在图的运算中可能产生结点集为空集的运算结果，在图的运算中可能产生结点集为空集的运算结果，为此规定结点集为空集的图为为此规定结点集为空集的图为空图空图（Empty GraphEmpty Graph），），并将空图记为并将空图记为。阶为有限的图称为。阶为有限的图称为有限图有限图(Finite(Finite Graph)Graph)，否则称为，否则称为无限图无限图(Infinite Graph)(Infinite Graph)。结点结点没有标号的图称为没有标号的图称为非标号图非标号图（Unlabeled GraphUnlabeled Graph），），否则为否则为标号图标号图（Labeled GraphLabeled Graph）。）。10.2 10.2 图与图模型图与图模型 如果图中存在某两条边的端点都相如果图中存在某两条边的端点都相同，则称该图为同，则称该图为多重图多重图(Multigraph)(Multigraph)，该两条边称为该两条边称为平行边平行边。如果一条边关联。如果一条边关联的两个结点是相同的结点，则称该边为的两个结点是相同的结点，则称该边为圈圈或或自环自环(Loop)(Loop)。不存在平行边与圈的。不存在平行边与圈的图即称为图即称为简单图简单图(Simple Graph)(Simple Graph)。10.2 10.2 图与图模型图与图模型 定义定义10.210.2 如果如果uvuv是图是图G G的边，记为的边，记为e e，即，即uvuv E(G),E(G),则则称结点称结点u u和和v v邻接邻接(Adjacent),(Adjacent),否则称结点否则称结点u u与与v v非邻接非邻接。这里，也称结点这里，也称结点u u或或v v与边与边e e是是关联关联（IncidentIncident）关系。）关系。与同一个结点关联的两条边称为与同一个结点关联的两条边称为邻接边邻接边。与结点。与结点v v关关联的边数称为联的边数称为结点结点v v的度的度，记作，记作deg(v)deg(v)。与结点。与结点v v关联关联的环对的环对v v的度数的贡献要计算两次。如果结点的度数的贡献要计算两次。如果结点v v的度为的度为0 0，则称之为，则称之为孤立点孤立点(Isolated Vertex)(Isolated Vertex)。一度的结点。一度的结点称为称为悬挂点悬挂点（Pendant VertexPendant Vertex）。图）。图G G的所有结点度的所有结点度数的最小度数称为数的最小度数称为G G的最小度的最小度，记作，记作(G)(G)，而所有结，而所有结点度数的最大者称为点度数的最大者称为G G的最大度的最大度，记作，记作(G)(G)。各结点。各结点的度均相同的图称为的度均相同的图称为正则图正则图（Regular GraphRegular Graph）。各）。各结点度均为结点度均为k k的正则图称为的正则图称为k-k-正则图正则图。10.2 10.2 图与图模型图与图模型 定义定义10.310.3 如果图的每条边是二结点构成的有序对，如果图的每条边是二结点构成的有序对，则该图称为则该图称为有向图有向图(Directed Graph)(Directed Graph)，上文所定义，上文所定义的图都是的图都是无向图无向图(Undirected Graph)(Undirected Graph)。有向图中边。有向图中边uvuv与与vuvu是两条不同的边，对于边是两条不同的边，对于边uvuv，称，称u u为为始点始点，v v为为终点终点。有向图中，结点有向图中，结点v v的度分为的度分为入度入度，即与该结点相，即与该结点相关联并以该结点为终点的边的数目，以及关联并以该结点为终点的边的数目，以及出度出度,即与即与该结点相关联并以该结点为始点的边的数目该结点相关联并以该结点为始点的边的数目,分别记分别记作作degdeg+(v)(v)，degdeg-(v)(v)。10.2 10.2 图与图模型图与图模型v v1 1v v2 2e e1 1e e2 2v v1 1v v2 2e e1 1e e2 2无向图无向图有向图有向图10.2 10.2 图与图模型图与图模型环环looploop-(-(伪图伪图:非简单图非简单图simple graph)simple graph)边边e e2 2(有向边有向边directed edgedirected edge有向图有向图)关联关联incidentincident结点结点v v1 1、v v2 2结点结点vertex/vertices(vertex/vertices(顶点顶点)平行边平行边/重边重边multiedgemultiedge多多重图重图multigraphmultigraph多重图多重图且伪图且伪图拟图拟图(pseudograph)(pseudograph)孤立点孤立点(isolated vertex)(isolated vertex)悬挂边悬挂边(pendant edge)(pendant edge)悬挂点悬挂点(pendant vertex)(pendant vertex)分离边分离边v v3 3结点度结点度degreedegree为为3,3,与与3 3结点结点邻接邻接adjacent,2adjacent,2出度出度1 1入度入度v v3 3v v1 1v v2 2e e1 1e e2 210.2 10.2 图与图模型图与图模型 练习练习1 1 设设G=(V,E)G=(V,E)是一无向图，是一无向图，V=vV=v1 1,v,v2 2,v,v8 8，E=E=(v(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v3 3,v,v1 1),(v),(v1 1,v,v5 5),(v),(v5 5,v,v4 4),(v),(v4 4,v,v3 3),),(v(v7 7,v,v8 8)（1 1）画出）画出G G的图解；的图解；（2 2）指出与）指出与V V3 3邻接的结点，以及和邻接的结点，以及和V V3 3关联的边；关联的边；（3 3）指出与）指出与(v(v2 2,v,v3 3)邻接的边和与邻接的边和与(v(v2 2,v,v3 3)关联的结点；关联的结点；（4 4）该图是否有孤立结点和孤立边？）该图是否有孤立结点和孤立边？（5 5）求求出出各各结结点点的的度度数数，并并判判断断是是否否是是完完全全图图和和正正则图？则图？（6 6）该）该(n,m)(n,m)图中，图中，n=n=？，？，m=m=？10.2 10.2 图与图模型图与图模型 图图的的边边数数与与结结点点数数的的关关系系是是图图最最为为重重要要的的属属性性，结结点点的的度度数数满满足足一一个个非非常常简简单单的的关关系系，即即图图的的每每条条边边都都关关联联于于两两个个结结点点，则则每每条条边边对对图图结结点点度度数数之之和和的贡献为的贡献为2 2，从而有下面的定理：，从而有下面的定理：定定理理10.110.1（欧欧拉拉定定理理）在在任任何何图图中中，结结点点度度的的总总和和等于边数的两倍。等于边数的两倍。该该定定理理也也被被称称为为握握手手定定理理，被被认认为为图图论论第第一一定定理，可以用于证明图的相关性质。理，可以用于证明图的相关性质。推论推论10.110.1 在任意图中，奇数度的结点个数为偶数。在任意图中，奇数度的结点个数为偶数。10.2 10.2 图与图模型图与图模型 例例10.310.3 设设G=G=，|V|=n,|E|=m|V|=n,|E|=m，证明：，证明：(G)2m/n(G)2m/n(G)(G)。证明证明 由欧拉定理，由欧拉定理，deg(v)deg(v)=2m=2m。对对任任意意的的v v V V，有有(G)deg(v)(G)deg(v)(G)(G)，于于是是 n n(G)(G)deg(v)deg(v)nn(G)(G)n n(G)2mn(G)2mn(G)(G)即即 (G)2m/n(G)2m/n(G)(G)。10.2 10.2 图与图模型图与图模型 例例10.410.4 请证明：有向图中，所有结点出度之请证明：有向图中，所有结点出度之和等于所有结点入度之和。和等于所有结点入度之和。证明证明 在有向图中，任意一条边都有一个始点在有向图中，任意一条边都有一个始点和一个终点，因而结论成立。和一个终点，因而结论成立。10.2 10.2 图与图模型图与图模型 练习练习2 2 设设G=(V,E)G=(V,E)有有1212条边，有条边，有6 6个度为个度为3 3的结的结点，其余结点的度数均小于点，其余结点的度数均小于3 3，问，问G G中至少有中至少有多少个结点？多少个结点？10.2 10.2 图与图模型图与图模型 例例10.510.5 十字路口交通管理问题。下图十字路口交通管理问题。下图(a)(a)是某繁忙的城市十字是某繁忙的城市十字路口交通管理示意图，其中路口交通管理示意图，其中c c1 1 c c9 9表示可能的行车路线，为安全表示可能的行车路线，为安全考虑，显然考虑，显然c c1 1、c c5 5可以同时进入十字路口，但可以同时进入十字路口，但c c1 1与与c c8 8却不能同时却不能同时进入十字路口，等等。本问题可以用图来建模，如下图（进入十字路口，等等。本问题可以用图来建模，如下图（b b）所示。其中，结点集为所有行车路线的构成的集合，结点之间所示。其中，结点集为所有行车路线的构成的集合，结点之间的边表示相应的二行车道不能同时开通。显然此图可以用于十的边表示相应的二行车道不能同时开通。显然此图可以用于十字路口交通信号灯的设计。字路口交通信号灯的设计。c4 c5c1 c2c3c8c7c6c3c4c9c1c5c2c7 c6c9 c8(a)(b)10.2 10.2 图与图模型图与图模型 例例10.610.6 旅行售货员问题。现有旅行售货员问题。现有一个笔记本计算机代理商要从一个笔记本计算机代理商要从其所在的城市北京出发，乘飞其所在的城市北京出发，乘飞机去机去5 5个城市，然后回到出发点。个城市，然后回到出发点。如右图所示。图中结点代表城如右图所示。图中结点代表城市，边代表城市间的直达航线。市，边代表城市间的直达航线。他怎样才能出差到每个城市恰他怎样才能出差到每个城市恰巧一次，最后回到北京呢？巧一次，最后回到北京呢？海口海口成都成都北京北京武汉武汉广州广州上海上海这个问题的解答本身比较简单，如可以选择线路为北京这个问题的解答本身比较简单，如可以选择线路为北京-成都成都-武汉武汉-海口海口-广州广州-上海上海-北京。但对于更为复杂的北京。但对于更为复杂的情况就很难直接找到好的解答。本问题与后文将研究的情况就很难直接找到好的解答。本问题与后文将研究的HamiltonHamilton图有关，将在那里做详细讨论。图有关，将在那里做详细讨论。10.2 10.2 图与图模型图与图模型 例例10.710.7 优先图。通过并发地执行某些语句，计算机程序可以执优先图。通过并发地执行某些语句，计算机程序可以执行得更快。如何确定哪些语句可以并发执行是非常重要的，这需行得更快。如何确定哪些语句可以并发执行是非常重要的，这需要分析清楚程序中语句之间的优先关系。这种优先关系可以用有要分析清楚程序中语句之间的优先关系。这种优先关系可以用有向图来表示。如用结点表示语句，若在执行完第一个结点表示的向图来表示。如用结点表示语句，若在执行完第一个结点表示的语句之前不能执行第二个结点表示的语句所表示的语句，则在第语句之前不能执行第二个结点表示的语句所表示的语句，则在第一个结点到第二个结点之间添加一条边。最后得到的图称为优先一个结点到第二个结点之间添加一条边。最后得到的图称为优先图。下图就是一个优先图的例子。该图表明在执行语句图。下图就是一个优先图的例子。该图表明在执行语句S S1 1 1 1、S S2 2 2 2与与S S4 4 4 4之前不能执行语句之前不能执行语句S S5 5 5 5。S S S S1 1 1 1 a=0 a=0 a=0 a=0S S S S2 2 2 2 b=1 b=1 b=1 b=1S S S S3 3 3 3 c=a+1 c=a+1 c=a+1 c=a+1S S S S4 4 4 4 d=b+a d=b+a d=b+a d=b+aS S S S5 5 5 5 e=d+1 e=d+1 e=d+1 e=d+1S S S S6 6 6 6 e=c+d e=c+d e=c+d e=c+dS S S S4 4 4 4S S S S5 5 5 5S S S S6 6 6 6S S S S3 3 3 3S S S S2 2 2 2S S S S1 1 1 110.2 10.2 图与图模型图与图模型 练习练习3 3 在在晚会上有晚会上有n n个人，他们各自与自己相识的人个人，他们各自与自己相识的人握一次手。已知每人与别人握手的次数都是奇数，握一次手。已知每人与别人握手的次数都是奇数，问问n n是奇数还是偶数。为什么？是奇数还是偶数。为什么？解解 n n是偶数。用是偶数。用n n个顶点表示个顶点表示n n个人，顶点间的一条个人，顶点间的一条边表示一次握手，可构成边表示一次握手，可构成 一个无向图。若一个无向图。若n n是奇数，是奇数，那么该图的顶点度数之和为奇数个奇数的和那么该图的顶点度数之和为奇数个奇数的和,即为奇即为奇数，与图性质矛盾，因此，数，与图性质矛盾，因此，n n是偶数。是偶数。10.2 10.2 图与图模型图与图模型 与集合论中研究子集，抽象代数中研究与集合论中研究子集，抽象代数中研究子代数类似，图论中也研究一个图的子图。子代数类似，图论中也研究一个图的子图。一个图一个图G G的子图的子图GG可以通过选取可以通过选取G G中的部分结中的部分结点与边构成，但要求如果选择了点与边构成，但要求如果选择了G G中的边，则中的边，则必须选择与该边向关联的结点。这样就保证必须选择与该边向关联的结点。这样就保证了了GG能够构成一个图。能够构成一个图。10.2 10.2 图与图模型图与图模型定定义义10.410.4 令令图图G=G=（V V，E E），称称(V,E)(V,E)为为G G的的子子图图（SubgraphSubgraph），当），当 (1)V(1)VV V且且E EE E；(2)(2)对任意对任意e eE E，则与，则与e e 相关联的结点相关联的结点u u,v,vV V。若若G G 是是 G G的子图的子图,则称则称G G是是G G 的的超图超图，记作，记作G GG G。若。若G GG G且且G G G(G(即即V VV V或或E EE)E)，则，则称称G G 是是G G的的真子图真子图。若。若G GG G且且V V V V，则称，则称G G 是是G G的的生成子图生成子图（Spanning SubgraphSpanning Subgraph）。设）。设V V1 1 V,V,且且V V1 1，以，以V V1 1 1 1为结点集，以两端点均在为结点集，以两端点均在V V1 1中的全体边为中的全体边为边集的边集的G G的子图，称为的子图，称为结点集结点集V V1 1导出的导出子图导出的导出子图（Derived SubgraphDerived Subgraph）。设）。设E E1 1 E,E,且且E E1 1，以，以E E1 1 1 1为边为边集，以集，以E E1 1中边关联的结点的全体为结点集中边关联的结点的全体为结点集G G的子图，称的子图，称为为边集边集E E1 1导出的导出子图导出的导出子图。10.2 10.2 图与图模型图与图模型 显然，子图或导出子图可以通过删除一显然，子图或导出子图可以通过删除一些结点或一些边得到。些结点或一些边得到。例例10.910.9 下下图所示的图中，图所示的图中，G G1 1 1 1是是G G的由结点导的由结点导出的导出子图，出的导出子图，G G2 2 2 2为为G G的由边集导出的导出子的由边集导出的导出子图。图。10.2 10.2 图与图模型图与图模型 定义定义10.510.5 设设G=G=是是n n阶图阶图,若若G G中任何结中任何结点都与其余的点都与其余的n n 1 1个结点相邻，则称个结点相邻，则称G G为为n n阶阶完全图完全图(Complete Graph)(Complete Graph)。记作。记作K Kn n。设。设D=D=为为n n阶有向图阶有向图,若对于任意的结点若对于任意的结点,u,v,u,v V(uv),V(uv),既有有向边既有有向边,又有又有，则称，则称D D为为有向完全图有向完全图。容易得到如下重要结论：容易得到如下重要结论：K Kn n的边数的边数|E(K|E(Kn n)|=n(n-1)/2)|=n(n-1)/2，且对于一般，且对于一般的的n n个结点的图个结点的图G G其边数其边数|E(G)|E(G)|n(n-1)/2n(n-1)/2。10.2 10.2 图与图模型图与图模型 下下图中图图中图(a)(a)为四个结点的完全图，为四个结点的完全图，(b)(b)不是完全图，不是完全图，(c)(c)是有向完全图。是有向完全图。(a)(b)(c)10.2 10.2 图与图模型图与图模型 定义定义10.610.6 若图若图G G的结点可以分为两个非空集合的结点可以分为两个非空集合V V1 1，V V2 2，G G中的边的端点分别属于中的边的端点分别属于V V1 1，V V2 2，则称，则称G G为为二分图二分图（Bipartite GraphBipartite Graph），可简记为），可简记为G(VG(V1 1，V V2 2)。若。若V V1 1中中结点与结点与V V2 2中结点均邻接且中结点均邻接且V V2 2中结点与中结点与V V1 1中结点也均邻中结点也均邻接，则称接，则称G G为为完全二分图完全二分图（Complete Bipartite Complete Bipartite GraphGraph），记为），记为K Km,nm,n，m,nm,n分别是分别是V V1 1，V V2 2的基数。的基数。二分图常常被应用于工作分配问题中，通过对二分图常常被应用于工作分配问题中，通过对二分图的分析，找出满足最多条件的工作分配方案。二分图的分析，找出满足最多条件的工作分配方案。完全二分图完全二分图K K1 1，n n常常被用来对计算机网络建模，度为常常被用来对计算机网络建模，度为n n的结点代表网络服务器，其余结点代表网络中的的结点代表网络服务器，其余结点代表网络中的n n个计算机。个计算机。10.2 10.2 图与图模型图与图模型例例10.1010.10 下图所示的图下图所示的图(a)(a)是二分图是二分图,图图（b b）是其的另一种表示。）是其的另一种表示。v v1 1 1 1v v v v6 6 6 6v v v v2 2 2 2v v v v3 3 3 3v v v v5 5 5 5v v1 1 1 1v v v v3 3 3 3v v v v2 2 2 2v v v v4 4 4 4v v v v6 6 6 6v v v v4 4 4 4v v v v5 5 5 510.3 10.3 路径与图连通性路径与图连通性 图图论论中中的的许许多多概概念念和和应应用用都都与与对对图图的的遍遍历历有有关关，即即是是从从一一个个结结点点u u出出发发，到到达达与与之之相相邻邻接接的的结结点点，在在从从该该邻邻接接结结点点出出发发到到达达其其邻邻接接的的结结点点，依依次次类类推推，最最后后可可以以到到达达图图中中的的某某结结点点v v，从从而而就就得得到到一一条条从从u u到到v v的的通通路路。从从u u到到v v的通路的通路W W可用如下的结点的序列来表示：可用如下的结点的序列来表示：W:u=v W:u=v0 0,v,v1 1,v,v2 2,v,vk k=v=v，k k 0 0。通路通路W W常表示为常表示为u-vu-v通路。这些结点序列通路。这些结点序列中任意相邻的结点在图中是邻接的关系，称中任意相邻的结点在图中是邻接的关系，称结点结点v vi i（i=0i=0，1,1,k,k）以及边）以及边(v(vi i,v,vi+1i+1)(i=0,1,(i=0,1,k-1),k-1)为通路为通路W W上的上的结点结点与与边边。10.3 10.3 路径与图连通性路径与图连通性 如果通路上首尾结点相同，则称该通路如果通路上首尾结点相同，则称该通路是是闭的闭的(Closed)(Closed)，否则称该通路是，否则称该通路是开的开的(Opened)(Opened)。如果通路上没有相同的边，则称。如果通路上没有相同的边，则称该通路为该通路为迹迹(Trail)(Trail)，如果迹上的开始结点与，如果迹上的开始结点与结束结点相同，则称之为结束结点相同，则称之为回路回路(Circuit)(Circuit)，如，如果回路上除了开始结点与结束结点没有相同果回路上除了开始结点与结束结点没有相同的结点，则称之为的结点，则称之为环环(Cycle)(Cycle)。如果通路上没。如果通路上没有相同的结点，则称该通路为有相同的结点，则称该通路为路路或或路径路径(Path)(Path)，有，有n n个结点的路常记作个结点的路常记作P Pn n。10.3 10.3 路径与图连通性路径与图连通性 通路遍历过的边的数目为通路的长度，如果通通路遍历过的边的数目为通路的长度，如果通路长度为路长度为0 0，则称之为，则称之为平凡通路平凡通路（Trivial WalkTrivial Walk）。）。两结点两结点u u，v v间的路可能不只一条，将其中的最短的间的路可能不只一条，将其中的最短的路称为路称为u u，v v间的间的距离距离。如果一条通路如果一条通路W W上有上有k+1k+1个结点，即个结点，即W:W:u=vu=v0 0,v,v1 1,v,v2 2,v,vk k=v=v，k k0 0。则由于。则由于W W上的边是由上的边是由W W上相上相邻结点邻结点(v(vi i,v,vi+1i+1)(i=0,1,k-1)(i=0,1,k-1)构成，因此构成，因此W W上有上有k k条边，即条边，即W W的长度为的长度为k k。如果一条环。如果一条环C C上有上有k+1k+1个结点，个结点，即即C:vC:v0 0,v,v1 1,v,v2 2,v,vk kv v0 0，k k0.0.则由于则由于C C上的边是由上的边是由C C上相邻结点上相邻结点(v(vi i,v,vi+1i+1)(i=0,1,k-1)(i=0,1,k-1)以及（以及（v vk k,v,v0 0）构成，因此构成，因此C C上有上有k+1k+1条边，即条边，即C C的长度为的长度为k+1k+1。10.3 10.3 路径与图连通性路径与图连通性 定理定理10.210.2 如果图如果图G G上存在一条上存在一条u-vu-v通路，则必通路，则必然存在一条然存在一条u-vu-v路；如果路；如果G G上存在一条闭通路，上存在一条闭通路，则必然存在一条回路则必然存在一条回路(环环)。这是因为，如果通路上存在相同的结点这是因为，如果通路上存在相同的结点v vi i,v,vj j，则可将则可将v vi i,v,vj j之间的一段通路删除，并合并之间的一段通路删除，并合并v vi i，v vj j为一为一个结点，从而得到一条更短的个结点，从而得到一条更短的u-vu-v通路。如果所得到通路。如果所得到的的u-vu-v通路上还存在相同的结点，则可以依此继续执通路上还存在相同的结点，则可以依此继续执行删除操作，最终一定可以得到一条没有相同结点行删除操作，最终一定可以得到一条没有相同结点的的u-vu-v通路，也就是一条通路，也就是一条u-vu-v路。类似地，如果路。类似地，如果G G上存上存在一条闭通路，则必然存在一条回路（环）。在一条闭通路，则必然存在一条回路（环）。10.3 10.3 路径与图连通性路径与图连通性例例10.1110.11在右图中，在右图中，1)1)找出一条包含图所有结点的通道；找出一条包含图所有结点的通道；2)2)找出一条包含图所有结点的迹；找出一条包含图所有结点的迹；3)3)找出所有找出所有a-da-d路，并求出其长度；路，并求出其长度；4)4)找出图中所有的环。找出图中所有的环。解解 1)1)包包含含图图所所有有结结点点的的不不是是迹迹的的通通道道：aebcaebdaebcaebd。2)2)包含所有结点的迹：包含所有结点的迹：beacbdbeacbd。3)a-d3)a-d路：路：aebd,acbd,aebd,acbd,长度均为长度均为3 3。4)4)环：环：acbeaacbea，长度为，长度为4 4。a a a ab b b be e e ed d d dc c c c10.3 10.3 路径与图连通性路径与图连通性 例例10.1210.12 每每个个结结点点的的度度数数至至少少为为2 2的的图图必必包包含含一一个个回回路。路。证证明明 设设P P是是图图G G中中最最长长路路经经中中的的一一条条，并并设设其其长长度度为为m,m,P P的的一一个个端端点点为为u u。考考察察G G中中与与u u关关联联的的边边，由由于于G G中中每每个个结结点点的的度度至至少少为为2 2，故故u u必必关关联联一一条条不不在在P P上上的的边边e e，从从而而e e的的另另一一个个端端点点v v必必然然在在P P上上，否否则则，将将这这个个结结点点加加入入P P上上，则则可可以以得得到到更更长长的的路路。于于是是，P P上上u u到到v v的的路与边的的路与边e e构成回路。构成回路。u u u uv v v vP P P P10.3 10.3 路径与图连通性路径与图连通性DijkstraDijkstra最短路径算法最短路径算法输输入入：一一个个带带权权图图G G，G G的的任任意意两两个个结结点点间间有有路路径径存存在在，G G中任意边中任意边(v,x)(v,x)的权值的权值w(v,x)0w(v,x)0；结点；结点a a与与z z输出：输出：L(z)L(z)，从结点，从结点a a到到z z的最短路径长度的最短路径长度1 Procedure Dijkstra(G)1 Procedure Dijkstra(G)2 2 For For 所有结点所有结点xa xa 3 3 L(x)=;L(x)L(x)=;L(x)表示表示a a到到x x的最短路径长度的最短路径长度4 4 End for;End for;5 5 L(a)=0;L(a)=0;6 T=V(G);6 T=V(G);7 7 S=S=;10.3 10.3 路径与图连通性路径与图连通性8 While(zT)8 While(zT)9 9 从从T T中找出具有最小中找出具有最小L(v)L(v)的结点的结点v;v;10 10 For For 所有与所有与v v相邻的结点相邻的结点xTxT11 11 L(x)=minL(x),L(v)+w(v,x)L(x)=minL(x),L(v)+w(v,x)1212End ForEnd For13 13 T=T-v;T=T-v;1414S=Sv;S=Sv;15 15 End WhileEnd While16 End Procedure16 End Procedure 10.3 10.3 路径与图连通性路径与图连通性 例例10.1310.13 下图所示的带权图中，根据上述算下图所示的带权图中，根据上述算法可以得到结点法可以得到结点a a到到z z的最短路径为图中加粗的最短路径为图中加粗的边所示，长度为的边所示，长度为1313。4 5 6 4 5 6 1 8 2 1 8 2 a z a z 2 10 3 2 10 310.3 10.3 路径与图连通性路径与图连通性 定定义义10.510.5 如如果果图图G G中中结结点点u u到到v v有有一一条条路路径径，则则称称结结点点 u u到到 v v是是 可可 达达 的的（AccesibleAccesible）或或 连连 通通 的的（ConnectedConnected）。结点）。结点u u到其自身也定义为连通的。到其自身也定义为连通的。定义定义10.610.6 如果图如果图G G的任何两个结点都是相互可达的，的任何两个结点都是相互可达的，称称G G是是连通的连通的（ConnectedConnected）,并称并称G G为为连通图连通图(Connected Graph)(Connected Graph)。对于有向图。对于有向图G G，如果，如果G G的任何两的任何两个结点都是相互可达的，则称有向图个结点都是相互可达的，则称有向图G G是是强连通强连通的；的；如果如果G G的任何两个结点中，至少从一个结点到另一个的任何两个结点中，至少从一个结点到另一个结点是可达的，称有向图结点是可达的，称有向图G G是是单向连通单向连通的；如果的；如果G G的的有向边被看作无向边时是连通的，称有向图有向边被看作无向边时是连通的，称有向图G G是是弱连弱连通通的。的。10.3 10.3 路径与图连通性路径与图连通性 容易判断，强连通图必定是单向连通图，容易判断，强连通图必定是单向连通图，单向连通图必定是弱连通图。单向连通图必定是弱连通图。例例10.1410.14 下图中，下图中，(a)(a)为连通图，为连通图，(b)(b)为由两为由两个连通分支的非连通图，个连通分支的非连通图，c c为强连通图，为强连通图，d d为为单向连通图，单向连通图，e e为弱连通图。为弱连通图。a b c d ea b c d e10.3 10.3 路径与图连通性路径与图连通性 练习练习