图论课件第三章 图的连通性精.ppt

《图论课件第三章 图的连通性精.ppt》由会员分享，可在线阅读，更多相关《图论课件第三章 图的连通性精.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论课件第三章 图的连通性1第1页，本讲稿共29页第三章第三章 图的连通性图的连通性主要内容主要内容一、割边、割点和块一、割边、割点和块二、图的连通度与敏格尔定理二、图的连通度与敏格尔定理三、图的宽直径简介三、图的宽直径简介教学时数教学时数安排安排6学时讲授本章内容学时讲授本章内容图的连通性刻画图的连通性刻画2第2页，本讲稿共29页本次课主要内容本次课主要内容(一一)、割边及其性质、割边及其性质(二二)、割点及其性质、割点及其性质(三三)、块及其性质、块及其性质割边、割点和块割边、割点和块3第3页，本讲稿共29页研究图的连通性的意义研究图的连通性的意义 研究图的连通性，主要研究图的连通程度的刻

2、画，其意义是：研究图的连通性，主要研究图的连通程度的刻画，其意义是：图论意义：图的连通程度的高低，是图结构性质的重要表征，图论意义：图的连通程度的高低，是图结构性质的重要表征，图的许多性质都与其相关，例如：连通图中任意两点间不相交路图的许多性质都与其相关，例如：连通图中任意两点间不相交路的条数就与图的连通程度有关。的条数就与图的连通程度有关。实际意义：图的连通程度的高低，在与之对应的通信网络中，实际意义：图的连通程度的高低，在与之对应的通信网络中，对应于网络对应于网络“可靠性程度可靠性程度”的高低。的高低。网络可靠性，是指网络运作的好坏程度，即指如计算机网网络可靠性，是指网络运作的好坏程度，即

3、指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。络、通信网络等对某个组成部分崩溃的容忍程度。网络可靠性，网络可靠性，是用可靠性参数来描述的。参数主要分是用可靠性参数来描述的。参数主要分确定性参数与概率性参数。确定性参数与概率性参数。4第4页，本讲稿共29页 确定性参数主要考虑网络在最坏情况下的可靠性度量，常确定性参数主要考虑网络在最坏情况下的可靠性度量，常称为网络拓扑的称为网络拓扑的“容错性度量容错性度量”，通常用图论概念给出，其，通常用图论概念给出，其中，本章将介绍的图的连通度就是网路确定性参数之一。近中，本章将介绍的图的连通度就是网路确定性参数之一。近年来，人们又提出了年来，人们又

4、提出了“坚韧度坚韧度”、“核度核度”、“整度整度”等描等描述网络容错性的参数。述网络容错性的参数。概率性参数主要考虑网络中处理器与信关以随机的、彼此概率性参数主要考虑网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下，网络的可靠性度量，独立的按某种确定性概率损坏的情况下，网络的可靠性度量，常称为网络拓扑的常称为网络拓扑的“可靠性度量可靠性度量”。(一一)、割边及其性质、割边及其性质 定义定义1 边边e为图为图G的一条割边，如果的一条割边，如果 。红色边为该图的割边红色边为该图的割边5第5页，本讲稿共29页 注：割边又称为图的注：割边又称为图的“桥桥”。图的割边有如下性质：图的割

5、边有如下性质：定理定理1 边边 e 是图是图G的割边当且仅当的割边当且仅当 e 不在不在G的任何圈中。的任何圈中。证明：可以假设证明：可以假设G连通。连通。若不然。设若不然。设 e 在图在图G的某圈的某圈 C 中，且令中，且令e=u v.考虑考虑P=C-e,则则P是一条是一条u v路。下面证明路。下面证明G-e连通。连通。对任意对任意 x,y V(G-e)由于由于G连通，所以存在连通，所以存在x-y路路Q.若若Q不含不含e，则，则x与与y在在G-e里连通；若里连通；若Q含有含有e，则可选择路：，则可选择路：x-u P v-y,说明说明x与与y在在G-e里也连通。所以里也连通。所以,若边若边e在

6、在G的某圈中，的某圈中，则则G-e连通。连通。但这与但这与e是是G的割边矛盾！的割边矛盾！“必要性必要性”6第6页，本讲稿共29页 “充分性充分性”如果如果e不是不是G的割边，则的割边，则G-e连通，于是在连通，于是在G-e中存在一条中存在一条u-v 路，显然：该路并上边路，显然：该路并上边e得到得到G中一个包含边中一个包含边e的圈，矛盾。的圈，矛盾。推论推论1 e为连通图为连通图G的一条边，如果的一条边，如果e含于含于G的某圈中，则的某圈中，则G-e连连通。通。证明：若不然，证明：若不然，G-e不连通，于是不连通，于是e是割边。由定理是割边。由定理1，e不不在在G的任意圈中，矛盾！的任意圈中

7、，矛盾！例例1 求证求证:(1)若若G的每个顶点的度数均为偶数，则的每个顶点的度数均为偶数，则G没有割边没有割边;(2)若若G为为k正则二部图正则二部图(k2)2)，则，则G G无割边。无割边。证明证明:(1)若不然，设若不然，设e=uv 为为G的割边。则的割边。则G-e的含有顶点的含有顶点u的那个分支中点的那个分支中点u的度数为奇，而其余点的度数为偶数，与握的度数为奇，而其余点的度数为偶数，与握手定理推论相矛盾！手定理推论相矛盾！7第7页，本讲稿共29页 (2)若不然，设若不然，设e=uv 为为G的割边。取的割边。取G-e的其中一个分支的其中一个分支G1,显显然，然，G1中只有一个顶点的度数

8、是中只有一个顶点的度数是k-1,其余点的度数为其余点的度数为k。并且。并且G1仍然为偶图。仍然为偶图。假若假若G1的两个顶点子集包含的顶点数分别为的两个顶点子集包含的顶点数分别为m与与n，并且，并且包含包含m个顶点的顶点子集包含度为个顶点的顶点子集包含度为k-1的那个点，那么有：的那个点，那么有：k m-1=k n。但是因。但是因k22，所以等式不能成立！，所以等式不能成立！注：该题可以直接证明注：该题可以直接证明G中任何一条边均在某一圈中，由中任何一条边均在某一圈中，由定理定理1得出结论。得出结论。边割集简介边割集简介 边割集跟回路、树等概念一样，是图论中重要概念。在应用边割集跟回路、树等概

9、念一样，是图论中重要概念。在应用上，它是电路网络图论的基本概念之一。所以，下面作简单介上，它是电路网络图论的基本概念之一。所以，下面作简单介绍。绍。8第8页，本讲稿共29页 定义定义2 一个具有一个具有n个顶点的连通图个顶点的连通图G,定义定义n-1为该连通图的秩；为该连通图的秩；具有具有p个分支的图的秩定义为个分支的图的秩定义为n-p。记为。记为R(G)。(1)R(G-S)=n-2;定义定义3 设设S是连通图是连通图G的一个边子集，如果：的一个边子集，如果：(2)对对S的任一真子集的任一真子集S1,有有R(G-S1)=n-2。称称S为为G的一个边割集，简称的一个边割集，简称G的一个边割。的一

10、个边割。例例2 边子集：边子集：S1=a,c,e,S2=a,b,S3=f是否是下是否是下图图G的边割？的边割？agedcbhfi图图G9第9页，本讲稿共29页 解解:S1不是；不是；S2与与S3是。是。定义定义4 在在G中，与顶点中，与顶点v关联的边的集合，称为关联的边的集合，称为v的关联集，的关联集，记为：记为：S(v)。agedcbhfi图图G 例例3 关联集是割集吗？为什么？关联集是割集吗？为什么？答：不一定！如在下图中，关联集答：不一定！如在下图中，关联集a,c,e是割集，但是，是割集，但是，关联集关联集d,e,f不是割集。不是割集。10第10页，本讲稿共29页 定义定义5 在在G中，

11、如果中，如果V=V1VV2 2,V,V1 1VV2 2=,E,E1 1是是G G中端点分属中端点分属于于V V1 1与与V V2 2的的G G的边子集，称的边子集，称E E1 1是是G G的一个断集。的一个断集。agedcbhfi图图G 在上图在上图G中：中：d,e,f,e,d,f等都是等都是G的断集。一的断集。一个图若按断集个图若按断集S来画，形式为：来画，形式为：S11第11页，本讲稿共29页 注：割集、关联集是断集，但逆不一定。断集和关联集之间注：割集、关联集是断集，但逆不一定。断集和关联集之间的关系为：的关系为：定理定理2 任意一个断集均是若干关联集的环和。任意一个断集均是若干关联集的

12、环和。定理定理3 连通图连通图G的断集的集合作成子图空间的一个子空间，其的断集的集合作成子图空间的一个子空间，其维数为维数为n-1。该空间称为图的断集空间。该空间称为图的断集空间。(其基为其基为n-1个线性无关的个线性无关的关联集关联集)例例4 求出下图求出下图G的所有断集。的所有断集。edcbaf123412第12页，本讲稿共29页 解：容易知道：解：容易知道：S(1),S(2),S(3)是线性无关断集。是线性无关断集。cba1234S(1)daf123S(2)ecf1234S(3)dcbf1234ebaf123413第13页，本讲稿共29页edca1234edb1234 上图形成的断集空间

13、为：上图形成的断集空间为：定义定义6 设设G是连通图，是连通图，T是是G的一棵生成树。如果的一棵生成树。如果G的一个割的一个割集集S恰好包含恰好包含T的一条树枝，称的一条树枝，称S是是G的对于的对于T的一个基本割集。的一个基本割集。14第14页，本讲稿共29页 例如：在图例如：在图G中中fedcba图图G G的相对于的相对于T的基本割集为：的基本割集为：a,e,f,c,f,b,e,d.关于基本割集，有如下重要结论：关于基本割集，有如下重要结论：定理定理4 连通图连通图G的断集均可表为的断集均可表为G的对应于某生成树的对应于某生成树T的基本的基本割集的环和。割集的环和。15第15页，本讲稿共29

14、页 定理定理5 连通图连通图G对应于某生成树对应于某生成树T的基本割集的个数为的基本割集的个数为n-1,它们作成断集空间的一组基。它们作成断集空间的一组基。注：到目前为止，我们在子图空间基础上，先后引进了图注：到目前为止，我们在子图空间基础上，先后引进了图的回路空间和断集空间，它们都是子图空间的子空间，这些的回路空间和断集空间，它们都是子图空间的子空间，这些概念，均是网路图论的基本概念，当然也是代数图论的基本概念，均是网路图论的基本概念，当然也是代数图论的基本概念。概念。(二二)、割点及其性质、割点及其性质 定义定义7 在在G中，如果中，如果E(G)可以划分为两个非空子集可以划分为两个非空子集

15、E1与与E2,使使GE1和和GE2以点以点v为公共顶点，称为公共顶点，称v为为G的一个割点。的一个割点。16第16页，本讲稿共29页 在图在图G1中，点中，点v1,v2均是割点；在均是割点；在G2中，中，v5是割点。是割点。v1v2v3v4e3e1e2e4e5e6图图G1v1v3v2v4v5图图G2 定理定理6 G无环且非平凡，则无环且非平凡，则v是是G的割点，当且仅当的割点，当且仅当 证明：证明：“必要性必要性”设设v是是G的割点。则的割点。则E(G)可划分为两个非空边子集可划分为两个非空边子集E1与与E2,使使GE1,GE2恰好以恰好以v为公共点。由于为公共点。由于G没有环，所没有环，所1

16、7第17页，本讲稿共29页以，以，GE1,GE2分别至少包含异于分别至少包含异于v的的G的点，这样，的点，这样，G-v的的分支数比分支数比G的分支数至少多的分支数至少多1，所以：，所以：“充分性充分性”由割点定义结论显然。由割点定义结论显然。定理定理7 v是树是树T的顶点，则的顶点，则v是割点，当且仅当是割点，当且仅当v是树的分支点。是树的分支点。证明：证明：“必要性必要性”若不然，有若不然，有deg(v)=1,即即v是树叶，显然不能是割点。是树叶，显然不能是割点。“充分性充分性”设设v是分支点，则是分支点，则deg(v)1.于是设于是设x与与y是是v的邻点，由树的性的邻点，由树的性质，只有唯

17、一路连接质，只有唯一路连接x与与y，所以，所以G-v分离分离x与与y.即即v为割点。为割点。18第18页，本讲稿共29页 定理定理8 设设v是无环连通图是无环连通图G的一个顶点，则的一个顶点，则v是是G的割点，当的割点，当且仅当且仅当V(G-v)可以划分为两个非空子集可以划分为两个非空子集V1与与V2,使得对任意使得对任意x V1,y V2,点点v在每一条在每一条x y路上。路上。证明：证明：“必要性必要性”v是无环连通图是无环连通图G的割点，由定理的割点，由定理6，G-v至少有两个连通分至少有两个连通分支。设其中一个连通分支顶点集合为支。设其中一个连通分支顶点集合为V1,另外连通分支顶点集合

18、另外连通分支顶点集合为为V2,即即V1与与V2构成构成V的划分。的划分。“充分性充分性”对于任意的对于任意的x V1,y V2，如果点，如果点v不在某一条不在某一条xy路上，路上，那么，该路也是连接那么，该路也是连接G-v中的中的x与与y的路，这与的路，这与x,y处于处于G-v的的不同分支矛盾。不同分支矛盾。若若v不是图不是图G的割点，那么的割点，那么G-v连通，因此在连通，因此在G-v中存在中存在x,y路，路，当然也是当然也是G中一条没有经过点中一条没有经过点v的的x,y路。矛盾。路。矛盾。19第19页，本讲稿共29页 例例5 求证：无环非平凡连通图至少有两个非割点。求证：无环非平凡连通图至

19、少有两个非割点。证明：证明：由于由于G是无环非平凡连通图，所以存在非平凡生成是无环非平凡连通图，所以存在非平凡生成树，而非平凡生成树至少两片树叶，它不能为割点，所以，它也树，而非平凡生成树至少两片树叶，它不能为割点，所以，它也不能为不能为G的割点。的割点。证明：设证明：设T是是G的一棵生成树。由于的一棵生成树。由于G有有n-2个割点，所以，个割点，所以，T有有n-2个割点，即个割点，即T只有两片树叶，所以只有两片树叶，所以T是一条路。这说明，是一条路。这说明，G的任意生成树为路。的任意生成树为路。例例6 求证：恰有两个非割点的连通单图是一条路。求证：恰有两个非割点的连通单图是一条路。一个单图的

20、任意生成树为路，则该图为圈或路，若为圈，一个单图的任意生成树为路，则该图为圈或路，若为圈，则则G没有割点，矛盾，所以，没有割点，矛盾，所以，G为路。为路。例例7 求证：若求证：若v是单图是单图G的割点，则它不是的割点，则它不是G的补图的割点。的补图的割点。20第20页，本讲稿共29页 证明：证明：v是单图是单图G的割点，则的割点，则G-v至少两个连通分支。现任取至少两个连通分支。现任取 ,如果如果x,y在在G-v的同一分支中，令的同一分支中，令u是与是与x,y处于不同分支的点，处于不同分支的点，那么，通过那么，通过u，可说明，可说明，x与与y在在G-v的补图中连通。若的补图中连通。若x,y在在

21、G-v的不同分支中，则它们在的不同分支中，则它们在G-v的补图中邻接。所以，若的补图中邻接。所以，若v是是G的割的割点，则点，则v不是其补图的割点。不是其补图的割点。(三三)、块及其性质、块及其性质 定义定义8 没有割点的连通图称为是一个块图，简称块；没有割点的连通图称为是一个块图，简称块；G的的一个子图一个子图B称为是称为是G的一个块，如果的一个块，如果(1),它本身是块；它本身是块；(2),若没有若没有真包含真包含B的的G的块存在。的块存在。例例7 找出下图找出下图G中的所有块。中的所有块。21第21页，本讲稿共29页 解：由块的定义得：解：由块的定义得：图图G22第22页，本讲稿共29页

22、 定理定理9 若若|V(G)|3,3,则则G G是是块块，当且，当且仅仅当当G G无无环环且任意两且任意两顶顶点位点位于同一圈上。于同一圈上。证明：证明：(必要性）设必要性）设G是块。因是块。因G没有割点，所以，它不能有没有割点，所以，它不能有环。对任意环。对任意u,v V(G),下面证明下面证明u,v位于某一圈上。位于某一圈上。对对d(u,v)作数学归纳法证明。作数学归纳法证明。当当d(u,v)=1时，由于时，由于G是至少是至少3个点的块，所以，边个点的块，所以，边uv不能不能为割边，否则，为割边，否则，u或或v为割点，矛盾。由割边性质，为割点，矛盾。由割边性质，uv必然在某必然在某圈中。圈

23、中。设当设当d(u,v)k时结论成立。时结论成立。设当设当d(u,v)=k。设设P是一条最短是一条最短(u,v)路，路，w是是v前面一点，则前面一点，则d(u,v)=k-123第23页，本讲稿共29页 由归纳假设，由归纳假设，u与与w在同一圈在同一圈C=P1PP2 2上。上。uwvPP2P1 考虑考虑G-w.由于由于G是块，所以是块，所以G-w连通。设连通。设Q是一条在是一条在G-w中的中的(u,v)路，并且设它与路，并且设它与C的最后一个交点为的最后一个交点为x。uwvQP2P1x24第24页，本讲稿共29页 则则uP1xvwP2为包含为包含u,v的圈。的圈。(充分性充分性)：若：若G不是块

24、，所以不是块，所以G中有割点中有割点v。由于。由于G无环，所以无环，所以G-v至少两个分支。设至少两个分支。设x,y是是G-v的两个不同分支中的点，则的两个不同分支中的点，则x,y在在G中不中不能位于同一圈上，矛盾！能位于同一圈上，矛盾！定理定理10 点点v是图是图G的割点当且仅当的割点当且仅当v至少属于至少属于G的两个不同的的两个不同的块。块。证明：证明：(必要性必要性)设设v是是G的割点。由割点定义：的割点。由割点定义：E(G)可以划分为可以划分为两个边子集两个边子集E1与与E2。显然。显然GE1与与GE2有唯一公共顶点有唯一公共顶点v。设。设B1与与B2分分别是别是GE1和和GE2中包含

25、中包含v的块，显然它们也是的块，显然它们也是G的块。即证明的块。即证明v至至少属于少属于G的两个不同块。的两个不同块。(充分性充分性)如果如果v属于属于G的两个不同块，我们证明：的两个不同块，我们证明：v 一定是图一定是图G的割的割点。点。25第25页，本讲稿共29页 如果包含如果包含v的其中一个块是环，显然的其中一个块是环，显然v是割点；是割点；设包含设包含v的两个块是的两个块是B1与与B2。如果包含。如果包含v的两个块不是环，那么的两个块不是环，那么两个块分别至少有两个顶点。假如两个块分别至少有两个顶点。假如v不是割点，在不是割点，在B1与与B2中分别找中分别找异于异于v的一个点的一个点x

26、与与y,x V(B1),y V(B2),则在则在G-v中有连接中有连接x与与y的的路路P。显然：显然：B1BB2 2PP无割点。这与无割点。这与B B1 1,B,B2 2是块矛盾！是块矛盾！注：该定理揭示了图中的块与图中割点的内在联系：不同块的公共点注：该定理揭示了图中的块与图中割点的内在联系：不同块的公共点一定是图的割点。也就是说，图的块可以按割点进行寻找。所以，该定一定是图的割点。也就是说，图的块可以按割点进行寻找。所以，该定理的意义在于：可以得到寻找图中全部块的算法。理的意义在于：可以得到寻找图中全部块的算法。为了直观反映图的块和割点之间的联系，引进所谓的块割点树。为了直观反映图的块和割

27、点之间的联系，引进所谓的块割点树。26第26页，本讲稿共29页 设设G是非平凡连通图。是非平凡连通图。B1,B2,Bk是是G的全部块，而的全部块，而v1,v2,vt是是G的全部割点。构作的全部割点。构作G的块割点树的块割点树bc(G):它的顶点是它的顶点是G的块和割的块和割点，连线只在块割点之间进行，一个块和一个割点连线，当且仅点，连线只在块割点之间进行，一个块和一个割点连线，当且仅当该割点是该块的一个顶点。当该割点是该块的一个顶点。例例8 画下图画下图G中的块割点树。中的块割点树。125436B3B2B1B5B4B6B7GB7B6B5B4B3B2B1543216b c(G)27第27页，本讲稿共29页 作业作业 P65-66 习题习题3：1,2,3,5,7,828第28页，本讲稿共29页Thank You!29第29页，本讲稿共29页