离散数学-图论ppt课件.ppt

《离散数学-图论ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-图论ppt课件.ppt（237页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1010章章 图论图论(Graph Theory ) )第十章第十章 图论图论(Graph Theory) 10.1 图的基本概念图的基本概念(Graph) 10.2 路与图的连通性路与图的连通性(Walks & Connectivity of Graphs) 10.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)10.4 最短链与关键路最短链与关键路（Minimal path ） 10.5 欧拉图与哈密尔顿图欧拉图与哈密尔顿图(Eulerian Graph & Hamilton-ian Graph ) 10.6 平面图平面图(Planar Graph)10

2、.7树树与生成树与生成树(Trees and Spanning Trees) 10.8 二部图（二部图（bipartite graph） 第第1010章章 图论图论(Graph Theory ) )10.1 图的基本概念图的基本概念 10.1.1 图的基本概念图的基本概念 10.1.2 图的结点的度数及其计算图的结点的度数及其计算 10.1.3 子图和图的同构子图和图的同构第第1010章章 图论图论(Graph Theory ) ) 图图 10.1.1哥尼斯堡七桥问题 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )10.1.1 图图 现实世界中

3、许多现象能用某种图形表示现实世界中许多现象能用某种图形表示,这种图形这种图形是由一些点和一些连接两点间的连线所组成。是由一些点和一些连接两点间的连线所组成。 【例【例10.1.1】a， b， c， d 4个篮球队进行友谊比赛。个篮球队进行友谊比赛。 为为了表示个队之间比赛的情况，了表示个队之间比赛的情况， 我们作出图我们作出图10.1.1的图形。的图形。 在图中个小圆圈分别表示这个篮球队，在图中个小圆圈分别表示这个篮球队， 称之为结点。称之为结点。如果两队进行过比赛，则在表示该队的两个结点之间用一如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，称之为边。这样利用一个图形条线连接

4、起来，称之为边。这样利用一个图形使各队之间使各队之间的比赛情况一目了然。的比赛情况一目了然。1.图的定义图的定义 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) ) 图图 10.1.1如果图如果图 10.1.1中的个中的个结点结点a， b， c， d分别分别表示个人，当某两表示个人，当某两个人互相认识时，个人互相认识时， 则则将其对应点之间用边将其对应点之间用边连接起来。连接起来。 这时的图这时的图又反映了这个人之又反映了这个人之间的认识关系。间的认识关系。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory

5、) ) 定义定义10.1.1一个图一个图G是一个序偶是一个序偶V(G), E(G)， 记记为为GV(G), E(G)。 其中其中V(G)是非空结点集合，是非空结点集合， E(G)是边集合，是边集合， 对对E(G)中的每条边，中的每条边， 有有V(G)中的中的结点的有序偶或无序偶与之对应。结点的有序偶或无序偶与之对应。 若边若边e所对应的结点对是有序偶所对应的结点对是有序偶a,b,则称则称e是有向边。是有向边。a叫边叫边e的始点的始点,b叫边叫边e的终点的终点,统称为统称为e的的端点。若边端点。若边e所对应的结点对是无序偶所对应的结点对是无序偶(a,b) ,则称则称e是是无向边。这时统称无向边。

6、这时统称e与两个结点与两个结点a和和b互相关联。互相关联。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )【例【例10.1.2】 设设G=V(G),E(G),其中其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。则图则图G可用图可用图10.1.2(a)或或(b)表示。表示。我们将结点我们将结点a、b的无序结点对记为的无序结点对记为(a，b），）， 有序有序结点对记为结点对记为a，b。

7、一个图一个图G可用一个图形来表示且表示是不唯一的。可用一个图形来表示且表示是不唯一的。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )图图 10.1.2 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )图 10.1.2 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )2. 图图G的结点与边之间的关系的结点与边之间的关系邻接点邻接点: 同一条边的两个端点。同一条边的两个端点。孤立点孤立点: 没有边与之关联的结点。没有边与之关联的结点。邻接边邻接边: 关

8、联同一个结点的两条边。关联同一个结点的两条边。孤立边孤立边: 不与任何边相邻接的边。不与任何边相邻接的边。自回路（环）：关联同一个结点的一条边（自回路（环）：关联同一个结点的一条边（v，v）或）或v，v）。）。平行边平行边(多重边多重边):关联同一对结点的多条边。关联同一对结点的多条边。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) ) 如例如例10.1.1中的图，结点集中的图，结点集Va，b，c，d， 边集边集 Ee1， e2， e3， e4， e5， 其中其中 e1（a，b），），e2（a, c），），e3（a，d），）， e4（b, c），

9、）， e5（c, d）。）。 d与与a、 d与与c是邻接的，是邻接的， 但但d与与b不不邻接，邻接， 边边e3与与e5是邻接的。是邻接的。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) ) 【例【例10.1.3】设图设图GV ,E 如图如图10.1.3所示。所示。 这里这里Vv1，v2，v3， Ee1，e2，e3，e4，e5， 其中其中e1 =(v1, v2) ，e2=(v1，v3) ， e3 =(v3, v3), e4 =(v2, v3), e5=(v2，v3)。 在这个图中，在这个图中，e3是是关联同一个结点的一条边关联同一个结点的一条边,即

10、即自回路；边自回路；边e4和和e5都与结点都与结点v2、 v3关联，即它们关联，即它们是平行边。是平行边。 10.1 图的基本概念图的基本概念 图图 10 .1. 3第第1010章章 图论图论(Graph Theory ) ) 3. 图图G的分类的分类(1)按按G的结点个数和边数分为的结点个数和边数分为(n,m)图图,即即n个结点个结点, m条边的图条边的图;(2) 特别地特别地, (n,0)称为称为零图零图, (1,0) 图称为图称为平凡图平凡图 。(2) 按按G中关联于同一对结点的边数分为中关联于同一对结点的边数分为多重图和简多重图和简单图单图; 多重图多重图:含有平行边的图（如含有平行边

11、的图（如图图 10 .1. 3） ； 线线 图图: 非多重图称为线图；非多重图称为线图； 简单图简单图:不含平行边和自环的图。不含平行边和自环的图。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )G1、G2是多重图是多重图G3是线图是线图G4是简单图是简单图第第1010章章 图论图论(Graph Theory ) ) (3)按按G的边有序、无序分为的边有序、无序分为有向图、无向图和混合图有向图、无向图和混合图; 有向图：有向图：每条边都是有向边的图称为有向图每条边都是有向边的图称为有向图 （图图 10 .1.4 (b)； 无向图：无向图：每条边

12、都是无向边的图称为无向图；每条边都是无向边的图称为无向图； 混合图：混合图：既有无向边既有无向边, 又有有向边的图称为混合图。又有有向边的图称为混合图。 (4)按按G的边旁有无数量特征分为的边旁有无数量特征分为加权图、无权图加权图、无权图(如图如图 10.1.4); 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )图图 10 .1. 4(5)按按G的任意两个结点间是否有边分为的任意两个结点间是否有边分为完全图完全图Kn (如图如图 10.1.5)和和不完全图不完全图(如图如图 10.1.6)。 10.1 图的基本概念图的基本概念 第第1010章章

13、 图论图论(Graph Theory ) ) 完全图完全图：任意两个不同的结点都邻接的简单图称为：任意两个不同的结点都邻接的简单图称为完全图。完全图。n 个结点的无向完全图记为个结点的无向完全图记为Kn。 图图10.1.5给出了给出了K3和和K4。从图中可以看出。从图中可以看出K3有有条边，条边，K4有条边。有条边。 容易证明容易证明Kn有有 条边。条边。(1)2n n 10.1 图的基本概念图的基本概念 图图 10 .1. 6图图 10.1.5 K3与与K4示意图示意图第第1010章章 图论图论(Graph Theory ) )例例213213有向完全图有向完全图无向完全图无向完全图第第10

14、10章章 图论图论(Graph Theory ) )给定任意一个含有给定任意一个含有n个结点的图个结点的图G,总可以把它补成一个总可以把它补成一个具有同样结点的完全图具有同样结点的完全图,方法是把那些缺少的边添上。方法是把那些缺少的边添上。 定义定义10.1.2 设设GV, E是一个具有是一个具有n个结点的简单个结点的简单图。以图。以V为结点集，以从完全图为结点集，以从完全图Kn中删去中删去G的所有边后的所有边后得到的图（或由得到的图（或由G中所有结点和所有能使中所有结点和所有能使G成为成为完全图完全图的添加边组成的图）称为的添加边组成的图）称为G的的补图补图，记为，记为 。 例如，零图和完全

15、图互为补图。例如，零图和完全图互为补图。G 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )G相对于相对于Kn的补图是下图中的的补图是下图中的G第第1010章章 图论图论(Graph Theory ) )第第1010章章 图论图论(Graph Theory ) )互为补图互为补图互为补图互为补图互为补图互为补图第第1010章章 图论图论(Graph Theory ) ) 【例【例10.1.4】（拉姆齐问题）试证在任何一个有个（拉姆齐问题）试证在任何一个有个人的组里，人的组里， 存在个人互相认识，存在个人互相认识， 或者存在个人互或者存在个人互相不

16、认识。相不认识。 我们用个结点来代表人，我们用个结点来代表人， 并用邻接性来代表认并用邻接性来代表认识关系。识关系。 这样一来，这样一来， 该例就是要证明：该例就是要证明： 任意一个有任意一个有个结点的图个结点的图G中，中， 或者有个互相邻接的点，或者有个互相邻接的点， 或者或者有个互相不邻接的点。有个互相不邻接的点。 即，即， 对任何一个有个结点对任何一个有个结点的图的图G， G或或 中含有一个三角形（即中含有一个三角形（即K3）。）。 G 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) ) 证明证明: 设设GV ,E， |V|6， v是是G中一

17、结点。中一结点。 因为因为v 与与G的其余个结点或者在的其余个结点或者在 中邻接，中邻接， 或者在或者在G中邻接。中邻接。 故不失一般性可假定，故不失一般性可假定， 有个结点有个结点v1， v2， v3在在G中与中与v邻接。邻接。 如果这个结点中有两个结点（如如果这个结点中有两个结点（如v1， v2）邻接，）邻接， 则它们与则它们与v 就是就是G中一个三角形的个顶点。中一个三角形的个顶点。 如果这如果这3个结点中任意两个在个结点中任意两个在G中均不邻接，中均不邻接， 则则v1， v2， v3就就是是 中一个三角形的个顶点。中一个三角形的个顶点。 GG 10.1 图的基本概念图的基本概念 第第1

18、010章章 图论图论(Graph Theory ) ) 10.1.2 图的结点的度数及其计算图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念关联，这就引出了图的一个重要概念结点的度数结点的度数。 10.1 图的基本概念图的基本概念 定义定义: 在有向图中在有向图中, 以以v为终点的边数称为结点为终点的边数称为结点v 的入的入度，度， 记为记为 ;以以v为始点的边数称为结点为始点的边数称为结点v 的出的出度，度， 记为记为 。结点。结点v的入度与出度之和称为结的入度与出度之和称为结点点v的度数，记为的度数，记

19、为 d(v)或或deg(v)。 ( )dv( )dv第第1010章章 图论图论(Graph Theory ) )定义定义: 在无向图中，图中结点在无向图中，图中结点v所关联的边数所关联的边数(有环时计算两次有环时计算两次)称为结点称为结点v 的度数，记为的度数，记为d(v)或或deg(v) 。| )(min)( | )(max)( VvvdGVvvdG最小度最大度第第1010章章 图论图论(Graph Theory ) )例例245136G1顶点顶点2入度：入度：1 出度：出度：3顶点顶点4入度：入度：1 出度：出度：0例例157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：4第第

20、1010章章 图论图论(Graph Theory ) ) 定理定理 10.1.1 无向图无向图GV ,E中结点度数的总和等中结点度数的总和等于边数的两倍，于边数的两倍， 即即证明证明: 因为每条边都与两个结点关联，因为每条边都与两个结点关联， 所以加上一条所以加上一条边就使得各结点度数的和增加边就使得各结点度数的和增加 2， 由此结论成立。由此结论成立。 定义定义：无向图中，如果每个结点的度都是：无向图中，如果每个结点的度都是k,则称为则称为k-度正则图。度正则图。d( )2VE 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )推论推论: 无向图

21、无向图G中度数为奇数的结点必为偶数个。中度数为奇数的结点必为偶数个。证明证明: 设设V1和和V2分别是分别是G中奇数度数和偶数度数的结中奇数度数和偶数度数的结点集。点集。 由定理由定理10.1.1知知 由于由于 是偶数之和，是偶数之和， 必为偶数，必为偶数， 而而2|E|也为偶数，也为偶数， 故故 是偶数。是偶数。 由此由此|V1|必为偶数。必为偶数。1deg( )VEvvVvVv2)deg()deg(212)deg(Vvv 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) ) 定理定理 10.1.2 在任何有向图在任何有向图GV ,E中，中， 有有

22、( )( )v Vv VdvdvE图图10.1.4第第1010章章 图论图论(Graph Theory ) ) 10.1.3 子图和图的同构子图和图的同构 1.子图子图 在研究和描述图的性质时，子图的概念占有在研究和描述图的性质时，子图的概念占有重要地位。重要地位。 定义定义10.1.5 设有图设有图G=V , E和图和图 G= V, E 。 1) 若若VV， EE， 则称则称G是是G的的子图子图。 2) 若若G是是G的子图，且的子图，且EE，则称，则称G是是G 的的真子图真子图。 第第1010章章 图论图论(Graph Theory ) )356例例245136图与子图图与子图第第1010章

23、章 图论图论(Graph Theory ) ) 3) 若若V=V， EE，则称，则称G是是G的的生成子图生成子图。图图10.1.7给出了图给出了图G以及它的真子图以及它的真子图G1和生成子图和生成子图G2。 图图10.1.7 图图G以及其真子图以及其真子图G 1和生成子图和生成子图G2 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) )例例 画出画出K4的所有非同构的生成子图。的所有非同构的生成子图。第第1010章章 图论图论(Graph Theory ) )2221112222222222222 , , GV EGV Euvu vEGVGVG V

24、GEGEEEGV结点定义： 设图是图的子图。若对任意结点 和 ，如果，则由唯一地确定，并称是，记为或。如果无孤立结点，且集合的诱导子图边集的诱导子图由所唯一确定，则称是，记为或。第第1010章章 图论图论(Graph Theory ) ) 2. 图的同构图的同构 10.1 图的基本概念图的基本概念 试观察下面各图有何异同？试观察下面各图有何异同？第第1010章章 图论图论(Graph Theory ) ) 图图 10.1.8 同构的图同构的图 图图 10.1.9 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory ) ) 定义定义10.1.6 设有图设有图

25、 G=V , E和图和图G= V, E。 如果存在双射如果存在双射：VV，使得，使得 e=(u, v) E iff e=(u),(v)E， 且且 (u， v)与与(u),(v)有相同的重数，则称有相同的重数，则称G与与G 同构。记作同构。记作G G。 注：由同构的定义可知，不仅结点之间要具有一注：由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的的邻接关系。对于有向图的同构还要求保持边的方向。方向。 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph The

26、ory ) ) 【例【例10.1.5】考察图考察图10.1.9中的两个图中的两个图GV , E和和 G= V, E 。 显然，定义显然，定义：VV, (vi)v i , 可以验证可以验证是是满足定义满足定义10.1.6的双射，所以的双射，所以G G。 10.1 图的基本概念图的基本概念 图图 10.1.9第第1010章章 图论图论(Graph Theory ) ) 一般说来，证明两个图是同构的并非是一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。轻而易举的事情，往往需要花些气力。请读者证明下图中两个图是同构的。请读者证明下图中两个图是同构的。第第1010章章 图论图论(Gr

27、aph Theory ) )第第1010章章 图论图论(Graph Theory ) ) 根据图的同构定义，可以给出图同构的必要条件根据图的同构定义，可以给出图同构的必要条件如下：如下：(1) 结点数目相等；结点数目相等；(2) 边数相等；边数相等；(3) 度数相同的结点数目相等。度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。第第1010章章 图论图论(Graph Theory ) )下图中的下图中的(a)和和(b)满足上述三个条件，然而并不同满足上述三个条件，然而并不同构。构。因为在因为在(a)中度数为中度数为3的结点的结点x与两个度数为与两个度

28、数为1的结点的结点邻接，而邻接，而(b)中度数为中度数为3的结点的结点y仅与一个度数为仅与一个度数为1的的结点邻接。结点邻接。寻找一种简单有效的方法来判定图的同构，至今寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。仍是图论中悬而未决的重要课题。第第1010章章 图论图论(Graph Theory ) )第第1010章章 图论图论(Graph Theory ) ) 对于同构，对于同构，形象地说，若图的结点可以任意形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么的条件下，这

29、个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的看可能不一样，但它们的拓扑结构拓扑结构是一样的。是一样的。 第第1010章章 图论图论(Graph Theory ) )10.2 路与图的连通性路与图的连通性(Walks & The Connectivity of Graphs) 10.2.1 路与回路路与回路(Walks and Circuits) 10.2.2 图的连通性图的连通性(The Connectivity of Graphs) 第第1010章章 图论图论(Graph Theory ) )10.2.1

30、路与回路路与回路(Wlaks and Circuits) 定义定义 10.2.1 给定图给定图GV ,E, 设设v0, v1, , vkV， e1，e2，ekE，其中，其中ei是关联于结点是关联于结点vi-1和和vi的边，的边， 称交替序列称交替序列v0e1v1e2ekvk为为连接连接v0到到vk的路的路， v0和和vk分别分别称为路的起点与终点。路中边的数目称为路的起点与终点。路中边的数目k称作路的长度。称作路的长度。 当当v0=vk时时,这条路称为回路。这条路称为回路。 在在简单图简单图中一条路中一条路v0e1v1e2ekvk由它的结点序列由它的结点序列v0v1vk确定确定,所以简单图的路

31、所以简单图的路,可表示为可表示为v0v1vk 。如图。如图10.1.1表示的简单图中，表示的简单图中， 路路ae1be4ce5d可写成可写成abcd。 第第1010章章 图论图论(Graph Theory ) ) 定义定义 10.2.2 设设=v0e1v1e2ekvk是图是图G中连接中连接v0到到vk的的路。路。 1)若若e1， e2， ， ek都不相同，都不相同， 则称路则称路为简单路为简单路或迹；或迹； 2)若若v0， v1， ， vk都不相同，则称路都不相同，则称路为基本路为基本路或通路；或通路； 3) 圈中若出现的每条边恰好一次，称简单圈。若圈中若出现的每条边恰好一次，称简单圈。若出现

32、的每个结点恰好一次，称基本圈。出现的每个结点恰好一次，称基本圈。 10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory ) )结点重复情况结点重复情况边重复情况边重复情况路路 允许允许 允许允许简单路简单路 允许允许不允许不允许 基本路基本路 不允许不允许 不允许不允许 回路回路允许允许允许允许简单圈简单圈允许允许不允许不允许基本圈基本圈不允许不允许不允许不允许10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory ) )注意：不同的教材定义不同！注意：不同

33、的教材定义不同！途径途径(walk)：图：图G中一个点边交替出现的序列。中一个点边交替出现的序列。迹迹(trail)：边不重的途径。：边不重的途径。路路(path): 顶点不重复的迹。顶点不重复的迹。闭途径（闭途径（closed walk）：起点和终点相同的途径。）：起点和终点相同的途径。闭迹闭迹(closed trail)：起点和终点相同的迹，也称为回：起点和终点相同的迹，也称为回路（路（circuit）。）。圈圈(cycle): 起点和终点相同的路。起点和终点相同的路。10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory

34、 ) )例例157324G26例例245136G1路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，1第第1010章章 图论图论(Graph Theory ) ) 例如在图例如在图 10.2.1中，中， 有连接有连接v5到到v3的路的路v5e8v4e5v2e6v5e7v3， 这也是一条简单路；路这也是一条简单路

35、；路 v1e1v2 e3v3是一条基本路；是一条基本路； 路路v1e1v2e3v3e4v2e1v1是一是一 条回路，条回路， 但不是基本圈；但不是基本圈； 路路v1e1v2e3v3e2v1是一条是一条 回路，回路， 也是圈。也是圈。 图图 10.2.1 10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory ) ) 定义定义 10.2.3 在图在图G中，中， 若结点若结点vi到到vj有路连接有路连接（这时称（这时称vi和和vj是可达的），是可达的）， 其中长度最短的其中长度最短的路的长度称为路的长度称为vi到到vj 的距离，的

36、距离， 用符号用符号d(vi,vj)表表示。若从示。若从vi到到vj不存在路径不存在路径,则则d(vi,vj)=。 例如在图例如在图10.2.1中，中， （v1， v4）。）。 10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory ) ) 注意注意:在有向图中在有向图中,d(vi,vj)不一定等于不一定等于d(vj,vi), 但一般地满足以下性质但一般地满足以下性质: (1) d(vi,vj)0; (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)d(vi,vk)。 图图 10.2.1 10.2.1

37、路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory ) ) 定理定理 10.2.1 设设G是具有是具有n个结点的图，个结点的图， 如果从结点如果从结点v1到另一结点到另一结点v2存在一条路，则存在一条路，则从结点从结点v1到到v2必存在一条长度不大于必存在一条长度不大于n1的的基本路（通路）。基本路（通路）。 10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory ) ) 证明证明:假定从假定从v1到到v2存在一条路径存在一条路径,(v1,vi,v2)是所是所经的结点经

38、的结点,如果其中有相同的结点如果其中有相同的结点vk,例例 (v1,vi,vk,vk,v2),则删去从则删去从vk到到vk的这些边的这些边,它仍它仍是从是从v1到到v2的路径的路径,如此反复地进行直至如此反复地进行直至(v1,vi,v2)中中没有重复结点为止。此时没有重复结点为止。此时,所得的就是通路。通路的长所得的就是通路。通路的长度比所经结点数少度比所经结点数少1,图中共图中共n个结点个结点,故通路长度不超故通路长度不超过过n-1。 推论推论 设图设图GV ,E ， |V|n， 则则G中任一基本中任一基本圈长度不大于圈长度不大于n。10.2.1 路与回路路与回路(Wlaks and Cir

39、cuits)第第1010章章 图论图论(Graph Theory ) ) 1. 无向图无向图的连通性的连通性 定义定义 10.2.4 在无向图如果一个图的任何两个结点在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否之间都有一条路，那么我们称这个图是连通的，否则是不连通的。则是不连通的。 定义定义 10.2.5 图图G的一个连通的子图的一个连通的子图G（称为（称为 连通连通子图）若不包含在子图）若不包含在G的任何更大的连通子图中，的任何更大的连通子图中， 它它就被称作就被称作G的连通分支。我们把图的连通分支。我们把图G的连通分支个的连通分支个数记作数记作（G）。）。1

40、0.2.2 图的连通性图的连通性(The Connectivity of Graphs)第第1010章章 图论图论(Graph Theory ) )图图 10.2.3 图图G与与G 在图在图10.2.3中，中， G是不连通的，是不连通的， （G），）， 而而G是是连通的，连通的， （G）。）。 任何一个图都可划分为若干个连通分支。任何一个图都可划分为若干个连通分支。 显然，显然， 仅当图仅当图G的连通分支数的连通分支数 （G）时，）时， 图图G是连通的。是连通的。10.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory ) ) 在图的研究中，常常需要考虑删去与增加

41、结点、在图的研究中，常常需要考虑删去与增加结点、结点集、边和边集（或弧集）的问题。所谓从结点集、边和边集（或弧集）的问题。所谓从图图G=中删去结点集中删去结点集S，是指作，是指作V-S以及从以及从E中删去与中删去与S中的全部结点相联结的边而得到的中的全部结点相联结的边而得到的子图，记作子图，记作G-S；特别当；特别当S=v时，简记为时，简记为G-v；所谓从图所谓从图G=中删去边集（或弧集）中删去边集（或弧集）T，是指作是指作E-T，且，且T中的全部边所关联的结点仍在中的全部边所关联的结点仍在V中而得到的子图，记为中而得到的子图，记为G-T；特别当；特别当T=e 时，时，简记作简记作G-e。第第

42、1010章章 图论图论(Graph Theory ) ) 所谓图所谓图G=增加结点集增加结点集S，是指作，是指作VS以以及向及向E中并入中并入S中、中、S与与V中所成的边而得到的中所成的边而得到的图，记作图，记作G+S；特别当；特别当S=v 时，简记为时，简记为G+v；图图G=增加边集（或弧集）增加边集（或弧集）T是指作是指作ET所得到的图，记作所得到的图，记作G+T，这里，这里T中全部边（或中全部边（或弧）的关联结点属于弧）的关联结点属于V。第第1010章章 图论图论(Graph Theory ) ) 定义定义: 给定连通无向图给定连通无向图G=，S V。若。若(G-S)(G)，但，但 T

43、S有有 (G-T)= (G)，则称，则称S是是G的一个分离结点集。若图的一个分离结点集。若图G的分离结点集的分离结点集S=v ，则称，则称v是是G的的割点割点。 类似地可定义图类似地可定义图G的分离边集的分离边集T；若图；若图G的分离的分离边集边集T=e ，则称，则称e是是G的的割边或桥割边或桥。第第1010章章 图论图论(Graph Theory ) ) 对于连通的非平凡图对于连通的非平凡图G，称，称 (G)= |S|S是是G的分的分离结点集离结点集 为图为图G的的结点连通度，它表明产生不结点连通度，它表明产生不连通图而需要删去结点的最少数目连通图而需要删去结点的最少数目。于是，对。于是，对

44、于分离图于分离图G， (G)=0；对于存在割点的连通图；对于存在割点的连通图G， (G)=1。VSmin第第1010章章 图论图论(Graph Theory ) ) 类似地定义边连通度类似地定义边连通度 (G)= |T|T是是G的分离边的分离边集集 ，它，它表明产生不连通图而需要删去边的最少表明产生不连通图而需要删去边的最少数目数目。可见，对于分离图。可见，对于分离图G， (G)=0；对于平凡；对于平凡图图G， (G)=0；对于图；对于图K1， (K1)=0；对于存在割；对于存在割边的连通图边的连通图G， (G)=1；对于完全图；对于完全图Kn， (Kn)=n-1。ETmin第第1010章章

45、图论图论(Graph Theory ) ) 下面是由惠特尼下面是由惠特尼(H.Whitney)于于1932年得到的关年得到的关于结点连通度、边连通度和最小度的不等式联于结点连通度、边连通度和最小度的不等式联系的定理：系的定理：定理定理: 对于任何一个无向图对于任何一个无向图G，有，有 (G) (G)(G)。定理定理: 一个连通无向图一个连通无向图G中的结点中的结点v是割点是割点存在两存在两个结点个结点u和和w，使得联结，使得联结u和和w的每条链都经过的每条链都经过v。第第1010章章 图论图论(Graph Theory ) )定理定理: 一个连通无向图一个连通无向图G中的边中的边e是割边是割边

46、 存在两个存在两个结点结点u和和w，使得联结，使得联结u与与w的每条链都经过的每条链都经过e。下面再给出一个判定一条边是割边的充要条件。下面再给出一个判定一条边是割边的充要条件。定理定理: 连通无向图连通无向图G中的一条边中的一条边e是割边是割边e不包含不包含在图的任何基本圈中。在图的任何基本圈中。第第1010章章 图论图论(Graph Theory ) ) 2. 有向图有向图的连通性的连通性 定义定义10.2.6 在有向图中在有向图中,若从结点若从结点u到到v有一有一条路，则称条路，则称u可达可达v。 定义定义10.2.7 设有有向图设有有向图G， 1)若若G的任意两个结点中的任意两个结点中

47、,至少从一个结点可至少从一个结点可达另一个结点达另一个结点,则称图则称图G是单向连通的是单向连通的; 10.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory ) ) 2)如果如果G的任意两个结点都是相互可达的的任意两个结点都是相互可达的,则称图则称图G是强连通的是强连通的; 3)如果略去边的方向后，如果略去边的方向后， G成为连通的无向图，则成为连通的无向图，则称图称图G是弱连通的。是弱连通的。 从定义可知：从定义可知： 若图若图G是单向连通的，是单向连通的， 则必是弱连通的；若图则必是弱连通的；若图G是强连通的，是强连通的， 则则必是单向连通的，必是单向连通的

48、， 且也是弱连通的。且也是弱连通的。 但反但反之不真。之不真。 第第1010章章 图论图论(Graph Theory ) ) 定理定理 10.2.2一个有向图一个有向图G是强连通的，是强连通的， 当当且仅当且仅当G中有一个（有向）回路，中有一个（有向）回路， 它至少它至少包含每个结点一次。包含每个结点一次。 第第1010章章 图论图论(Graph Theory ) )证明证明: 必要性：如果有向图必要性：如果有向图G是强连通的，则任意是强连通的，则任意两个结点都是相互可达的。故必可作一回路经过两个结点都是相互可达的。故必可作一回路经过图中所有各结点。否则必有一回路不包含某一结图中所有各结点。否

49、则必有一回路不包含某一结点点v。这样，这样，v与回路上各结点就不能相互可达，与回路上各结点就不能相互可达， 这与这与G是强连通矛盾。是强连通矛盾。 充分性：如果充分性：如果G中有一个回路，它至少包含中有一个回路，它至少包含每个结点一次，则每个结点一次，则G中任意两个结点是相互可达的，中任意两个结点是相互可达的， 故故G是强连通的。是强连通的。 10.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory ) ) 定义定义 10.2.8 在有向图在有向图G=V,E中中,G是是G的子的子图图,若若G是强连通的是强连通的(单向连通的单向连通的,弱连通的弱连通的),没没有包含

50、有包含G的更大子图的更大子图G是强连通的是强连通的(单向连通单向连通的的,弱连通的弱连通的),则称则称G是是G的强分图的强分图(单向分图单向分图,弱弱分图分图)。 10.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory ) )连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分图连通分图例例245136第第1010章章 图论图论(Graph Theory ) )图图 10.2.5 10.2.2 图的连通性图的连通性(The Connectivity of Graphs)第第1010章章 图论图论(Graph Theory ) )在图在图1