第3章-图论PPT优秀课件

《第3章-图论PPT优秀课件》由会员分享，可在线阅读，更多相关《第3章-图论PPT优秀课件（53页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章 图的连通度图的连通度l 割边、割点和块割边、割点和块l 连通度连通度l 应用应用l 图的宽距离和宽直径图的宽距离和宽直径G3G4删去任意一条边后仍连通，但删去任意一条边后仍连通，但删去点删去点u后便不连通后便不连通考察考察G3和和G4删去任意一条边或任意一个点后仍连通删去任意一条边或任意一个点后仍连通，但从直观上，但从直观上看，看，G4的连通程度比的连通程度比G3高高。删去任意一条边后便不连通删去任意一条边后便不连通G1uG2 图的连通性，主要用来刻画图的连通程度，其意义是图的连通性，主要用来刻画图的连通程度，其意义是 理论意义：理论意义：图的连通程度的高低，是图结构性质的重要图

2、的连通程度的高低，是图结构性质的重要表征，图的许多性质都与其相关，例如：连通图中任意两点表征，图的许多性质都与其相关，例如：连通图中任意两点间不相交路的条数就与图的连通程度有关。间不相交路的条数就与图的连通程度有关。 实际意义：实际意义：图的连通程度的高低，对应于通信网络图的连通程度的高低，对应于通信网络“可可靠性程度靠性程度”的高低。的高低。 网络可靠性，是指网络运作的好坏程度，即指如计算机网络可靠性，是指网络运作的好坏程度，即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。网络、通信网络等对某个组成部分崩溃的容忍程度。 网络可靠性，网络可靠性， 是用可靠性参数来描述的，其主要分为是

3、用可靠性参数来描述的，其主要分为“确定性参数确定性参数”与与“概率性参数概率性参数”。研究图的连通性的意义研究图的连通性的意义 确定性参数主要考虑网络在最坏情况下的可靠性度量，确定性参数主要考虑网络在最坏情况下的可靠性度量，常称为网络拓扑的常称为网络拓扑的“容错性度量容错性度量”，通常用图论概念给出，通常用图论概念给出，其中，本章将介绍的图的连通度就是网络确定性参数之一。其中，本章将介绍的图的连通度就是网络确定性参数之一。 近年来，人们又提出了近年来，人们又提出了“坚韧度坚韧度”、“核度核度”、“整整度度”等描述网络容错性的参数。等描述网络容错性的参数。 概率性参数主要考虑网络中处理器与信关以

4、随机的、概率性参数主要考虑网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下，网络的可靠彼此独立的按某种确定性概率损坏的情况下，网络的可靠性度量，常称为网络拓扑的性度量，常称为网络拓扑的“可靠性度量可靠性度量”。3.1 割边、割点和块割边、割点和块定义定义 设设e是图是图G的一条边，若的一条边，若(G- -e)(G)，则称，则称e为为G的的割割边边。 注：注：若若G连通，则割边是指删去后使连通，则割边是指删去后使G不连通的边，故非平不连通的边，故非平凡树的每条边均为割边。凡树的每条边均为割边。例例 下图中，边下图中，边e1和和e2为割边，而其余边均不为割边。为割边，而其余边均不

5、为割边。e1e2一、割边及其性质一、割边及其性质定理定理 e是图是图G的割边当且仅当的割边当且仅当e不在不在G的任何圈中。的任何圈中。证明证明 因结论若在因结论若在G的含的含e的连通分支中成立，则必在的连通分支中成立，则必在G中成中成立，所以我们不妨假定立，所以我们不妨假定G连通。连通。若若含含e，用，用P替换替换e后也可得到后也可得到G- -e中一条中一条(x, y)路，以上表明路，以上表明G- -e连通，这与连通，这与e是割边矛盾，所以是割边矛盾，所以e不在不在G的任何圈中。的任何圈中。必要性必要性 设设e=uv是图是图G的割边，若的割边，若e含在圈含在圈C中，令中，令P=C- -e。易知

6、易知P是是G- -e中一条中一条(u, v)路。路。任取任取G- -e中两个不同点中两个不同点x和和y，因，因G连通，故连通，故G中存在中存在(x, y)路路。若若不含不含e，则，则 也是也是G- -e中一条中一条(x, y)路；路；充分性充分性 设设e=uv，若，若e不是不是G的割边，则的割边，则G- -e仍连通，从而在仍连通，从而在G- -e中存在中存在(u, v) 路路P，这样，这样P+e便是便是G中含中含e的圈，这与假设的圈，这与假设“e不在不在G的任何圈中的任何圈中”矛盾。矛盾。所以，所以，e是是G的割边。的割边。注：注：以上定理表明圈中的边一定不是割边，所以删去圈中的以上定理表明圈

7、中的边一定不是割边，所以删去圈中的边不会破坏图的连通性。边不会破坏图的连通性。推论推论 设设e是连通图是连通图G的任意一条边，若的任意一条边，若e含在含在G的某圈中，则的某圈中，则G- -e仍连通。仍连通。例例 求证求证： (1) 若若G的每个顶点的度数均为偶数，则的每个顶点的度数均为偶数，则G没有割边没有割边; (2) 若若G为为k正则二部图正则二部图(k2)，则，则G无割边。无割边。证明证明 (1) 若不然，设若不然，设e=uv为为G的割边。的割边。则则G- -e的含有顶点的含有顶点u(或或v)的那个分支中点的那个分支中点u(或或v)的度数必为奇的度数必为奇数，而其余点的度数为偶数，与数，

8、而其余点的度数为偶数，与“度数为奇数的顶点的个数度数为奇数的顶点的个数为偶数为偶数”相矛盾。相矛盾。(2) 若不然，设若不然，设e=uv为为G的割边。的割边。假设假设G1为为G- -e的包含顶点的包含顶点u的连通分支，显然的连通分支，显然G1中除了点中除了点u的的度数为度数为k- -1外，其余点的度数均为外，其余点的度数均为k。不妨假设不妨假设S包含顶点包含顶点u，则，则ks- -1=|E(G1)|=kt。显然显然G1仍为偶图，设其二部划分为仍为偶图，设其二部划分为S和和T且且|S|=s，|T|=t。但是因但是因k2，所以等式不能成立！因此，所以等式不能成立！因此，e一定不是割边。一定不是割边

9、。二、割点及其性质二、割点及其性质定义定义 图图G=(V, E)的顶点的顶点v称为称为割点割点，如果，如果E可划分为两个非可划分为两个非空子集空子集E1和和E2，使得，使得GE1和和GE2恰有一个公共顶点恰有一个公共顶点v。例例 图中点图中点u1, u2, u3和和u4是割是割点，其余点均不为割点。点，其余点均不为割点。u1u2u3u4注：注：(1) 若若(G- -v)(G)，则，则v必为必为G的割点。的割点。 (2) 若若G无环，则无环，则v是是G的割点当且仅当的割点当且仅当 (G- -v)(G)。 (3) 若无环图若无环图G连通，则割点是指删去该点使连通，则割点是指删去该点使G不连通的不连

10、通的 点。点。定理定理 设设v是树是树G的顶点，则的顶点，则v是是G的割点当且仅当的割点当且仅当d(v)1。证明证明 必要性必要性 若不然，有若不然，有d(v)=1，即，即v是树叶，显然不可能是是树叶，显然不可能是割点。割点。充分性充分性 设顶点设顶点v的度数大于的度数大于1。设设x和和y是与是与v相邻的两点，由树的性质知，只有唯一的路连接相邻的两点，由树的性质知，只有唯一的路连接x与与y，所以，所以G- -v分离分离x与与y。因此，。因此，v是割点。是割点。定理定理 设设v是无环连通图是无环连通图G的一个顶点，则的一个顶点，则v是是G的割点当且仅的割点当且仅当当V(G- -v)可划分为两个非

11、空顶点子集可划分为两个非空顶点子集V1与与V2，使得对任意的，使得对任意的xV1，yV2，点，点v都在每一条都在每一条(x, y)路上。路上。证明证明 充分性充分性 若若v不是图不是图G的割点，那么的割点，那么G- -v连通，因此在连通，因此在G- -v中存在中存在(x, y)路，当然也是路，当然也是G中一条没有经过点中一条没有经过点v的的(x, y)路。与已知条件矛盾。路。与已知条件矛盾。必要性必要性 设设v是无环连通图是无环连通图G的割点，则的割点，则G- -v至少有两个连通分至少有两个连通分支。支。设设V1是其中一个连通分支的顶点集，是其中一个连通分支的顶点集，V2为其余顶点构成的集为其

12、余顶点构成的集合。合。对于任意的对于任意的xV1，yV2，如果点，如果点v不在某一条不在某一条(x, y)路上，路上，那么该路也是那么该路也是G- -v中连接中连接x与与y的一条路，这与的一条路，这与x, y处于处于G- -v的的不同连通分支矛盾。不同连通分支矛盾。例例 求证：无环非平凡连通图至少有两个点不是割点。求证：无环非平凡连通图至少有两个点不是割点。证明证明 由于由于G是无环非平凡连通图，所以存在非平凡生成树。是无环非平凡连通图，所以存在非平凡生成树。非平凡生成树至少两片树叶，它们不能为生成树的割点。非平凡生成树至少两片树叶，它们不能为生成树的割点。显然，它们也不能为显然，它们也不能为

13、G的割点。的割点。证明证明 设设T是是n阶连通简单图阶连通简单图G的任意一棵生成树。的任意一棵生成树。例例 求证：恰有两个非割点的连通简单图是一条路。求证：恰有两个非割点的连通简单图是一条路。一个简单图的任意生成树为路，则该图为圈或路。一个简单图的任意生成树为路，则该图为圈或路。由于由于G有有n- -2个割点，所以，个割点，所以，T有有n- -2个割点，因此个割点，因此T只有两片只有两片树叶，所以树叶，所以T是一条路。是一条路。这说明，这说明，G的任意生成树为路。的任意生成树为路。若为圈，则若为圈，则G没有割点，矛盾！所以没有割点，矛盾！所以G为路。为路。例例 求证：若求证：若v是简单图是简单

14、图G的割点，则的割点，则v不是不是G的补图的割点。的补图的割点。证明证明 容易验证，容易验证，因为因为v是是G的割点，所以的割点，所以 G- -v一定不是连通图。从而一定不是连通图。从而G- -v的补图的补图是连通图。是连通图。因此，在因此，在G的补图中删去顶点的补图中删去顶点v不会增加图的连通分支数。不会增加图的连通分支数。所以，所以，v不是不是G的补图的割点。的补图的割点。三、块及其性质三、块及其性质定义定义 没有割点的连通图称为没有割点的连通图称为块图块图，简称，简称块块。若图。若图G的子图的子图B是块，且是块，且G中没有真包含中没有真包含B的子图也是块，则称的子图也是块，则称B是是G的

15、的块块。注注： (1) 仅有一条边的块，仅有一条边的块，要么是割边，要么是环；要么是割边，要么是环； (2) 仅有一个点的块，要么是孤立点，要么是环；仅有一个点的块，要么是孤立点，要么是环； (3) 至少有两个点的块无环；至少有两个点的块无环； (4) 至少有三个点的块无割边。至少有三个点的块无割边。例例 图图G如图如图(a)所示，所示，G的所有块如图的所有块如图(b)所示。所示。(a)(b)定理定理 设图设图G的阶至少为的阶至少为3，则，则G是块当且仅当是块当且仅当G无环并且任意无环并且任意两点都位于同一个圈上。两点都位于同一个圈上。证明证明 充分性充分性 此时此时G显然连通。显然连通。若若

16、G不是块，则不是块，则G中有割点中有割点v。由于由于G无环，所以无环，所以G- -v至少有两个连通分支。至少有两个连通分支。设设x, y是是G- -v的两个不同分支中的点，则的两个不同分支中的点，则x, y在在G中不能位于中不能位于同一圈上，矛盾！同一圈上，矛盾！必要性必要性 G显然无环，否则显然无环，否则G中存在割点。中存在割点。下证下证G中任意两点中任意两点u和和v位于同一圈上，对距离位于同一圈上，对距离d(u, v)作归纳。作归纳。当当d(u, v)=1时，由于时，由于G是至少有是至少有3个点的块，所以，边个点的块，所以，边uv不能不能为割边。为割边。由割边性质知，由割边性质知，uv必然

17、在某圈中。必然在某圈中。设结论对距离小于设结论对距离小于k的任意两点成立。假定的任意两点成立。假定u, v为距离等于为距离等于k的任意两点。的任意两点。设设P是一条最短是一条最短(u, v)路，路，w是是v前面一点，则前面一点，则d(u, w)=k- -1。由归纳假设知，由归纳假设知，u与与w在同一圈在同一圈C上。上。 x u w v C P2P1 Q 若若v也在也在C中，则已得到证明。下设中，则已得到证明。下设v不在不在C中。中。因因G是块，无割点，故是块，无割点，故 G- -w仍连通，于是存在一条仍连通，于是存在一条 (u, v)路路Q。设点。设点x是是Q与与C的最后一个公共点。的最后一个

18、公共点。于是于是P1, Q的的x到到v段，段，边vw以及以及P2的的w到到u段共同构成一个圈段共同构成一个圈C*，且且u与与v均在均在C*上。上。点点x将将C划分为两条划分为两条(u, x)路路P1和和P2，不妨设，不妨设w在在P2上。上。推论推论 设设G的阶至少为的阶至少为3，则，则G是块当且仅当是块当且仅当G无孤立点且任无孤立点且任意两条边都在同一个圈上。意两条边都在同一个圈上。证明明 设G无孤立点且任意两条无孤立点且任意两条边都在同一个圈上。此都在同一个圈上。此时G无无环，因，因为环和任何一条和任何一条边都不可能在一个圈上。都不可能在一个圈上。此时，必然任意两个此时，必然任意两个点点也在

19、同一个圈上，因此也在同一个圈上，因此G是块。是块。反之，设反之，设G是块。显然是块。显然G无孤立点。无孤立点。任取任取G中两条中两条边e1和和e2。在在边e1和和e2上各插入一个新的上各插入一个新的顶点点v1和和v2，使，使e1和和e2均成均成为两两条条边，记这样得到的得到的图为G*。由于由于G是至少有三个点的块，从而是至少有三个点的块，从而G无割边，因此无割边，因此v1和和v2必然必然不是不是G*的割点，所以的割点，所以G*是是阶大于大于4的的块。因此因此v1和和v2在在G*的同一个圈上，于是的同一个圈上，于是e1和和e2在在G中位于同一个中位于同一个圈上。圈上。定理定理 点点v是图是图G的

20、割点当且仅当的割点当且仅当v至少属于至少属于G的两个不同的块。的两个不同的块。证明证明 必要性必要性 设设v是是G的割点。的割点。由割点定义知由割点定义知E(G)可以划分为两个边子集可以划分为两个边子集E1与与E2使得使得GE1与与GE2有唯一公共顶点有唯一公共顶点v。设设B1与与B2分别是分别是GE1和和GE2中包含中包含v的块，显然它们也是的块，显然它们也是G的块。因此的块。因此v至少属于至少属于G的两个不同块。的两个不同块。充分性充分性 设点设点v属于属于G的两个不同块的两个不同块B1和和B2。如果如果B1和和B2其中一个是环，显然其中一个是环，显然v是割点。是割点。现在假设现在假设B1

21、与与B2都不是环。都不是环。显然，显然，B1B2P 无割点。这与无割点。这与B1与与B2是块矛盾！是块矛盾！那么那么B1与与B2分别至少有两个顶点。分别至少有两个顶点。假如假如v不是割点，在不是割点，在B1与与B2中分别找异于中分别找异于v的一个点的一个点x与与y， 则则在在G- -v中有连接中有连接x与与y的路的路P。注：注：两个不同块的公共顶点只能是割点，即块与块只能由割两个不同块的公共顶点只能是割点，即块与块只能由割点相联结，因此可以通过割点搜寻块。点相联结，因此可以通过割点搜寻块。定义定义 设设G是非平凡连通图，是非平凡连通图，B1, B2, Bk是是G的全部块，而的全部块，而v1,

22、v2, vt是是G的全部割点。构作的全部割点。构作G的的块割点树块割点树bc(G)：它的顶点：它的顶点是是G的块和割点，的块和割点，uv是是bc(G)的一条边当且仅当的一条边当且仅当u与与v中有一个中有一个是是G的割点，另一个是该割点联结的块。的割点，另一个是该割点联结的块。例例注注：(1) bc(G)是一个没有圈的连通图，即为树。是一个没有圈的连通图，即为树。 (2) 若若G本身就是一个块，则本身就是一个块，则bc(G)是平凡图。是平凡图。 (3) 若若G本身不是块，则本身不是块，则bc(G)至少有三个点并且叶子点至少有三个点并且叶子点 为为G的只含一个割点的块。的只含一个割点的块。B1B5

23、B6B3B2B4125634GB1B2B3B7B4B5B6125634bc(G)B73.2 连通度连通度一、连通度和边连通度一、连通度和边连通度定义定义 给定连通图给定连通图G， 设设V 是是V(G)的顶点子集，若的顶点子集，若G - -V 不不连通，则称连通，则称V 为为G的的顶点割顶点割，含有，含有k个顶点的顶点割称为个顶点的顶点割称为G的的k顶点割顶点割。G中点数最少的顶点割称为中点数最少的顶点割称为最小点割最小点割。 例例G2V1=u，V2=u, v均为均为G1的顶点割，其中的顶点割，其中V1为为1点割，点割，V2为为2点割，点割，G2没有顶点割。没有顶点割。G1uvw注注：(1) 若

24、若G是非平凡连通图，则是非平凡连通图，则v是是G的割点当且仅当的割点当且仅当v是是 G的的1顶点割。顶点割。 (2) 完全图没有顶点割，实际上也只有以完全图为生成完全图没有顶点割，实际上也只有以完全图为生成 子图的图没有顶点割。子图的图没有顶点割。定义定义 对对n阶非平凡连通图阶非平凡连通图G，若，若G存在顶点割，则称存在顶点割，则称G的最小的最小顶点割中的点数为顶点割中的点数为G的的连通度连通度；否则称；否则称n- -1为其连通度。为其连通度。G的的连通度符号表示为连通度符号表示为(G)，简记为，简记为；非连通图或平凡图的连；非连通图或平凡图的连通度定义为通度定义为0。连通度也可描述为连通度

25、也可描述为“使图不连通或成为平凡图，至少需要删使图不连通或成为平凡图，至少需要删去的点数去的点数”。例例 (1) (Kn)=n- -1；(2) (Cn)=2，其中，其中Cn为为n圈，圈，n3。例例 求下列各图的连通度。求下列各图的连通度。G1G2G3G4解解 (G1)=1，(G2)=3，(G3)=1，(G4)=2。定义定义 若一个图的连通度至少为若一个图的连通度至少为k，则称该图是，则称该图是k连通的连通的。注：注：(1) 非平凡连通图均是非平凡连通图均是1连通的。连通的。 (2) 图图G是是2连通的当且仅当连通的当且仅当G连通、无割点且至少含有连通、无割点且至少含有3 个点。个点。 (3)

26、K2连通、无割点，但连通度为连通、无割点，但连通度为1。定义定义 设设G为连通图，称使为连通图，称使G- -E 不连通的不连通的G的边子集的边子集E 为为G的的边割边割，含有，含有k条边的边割称为条边的边割称为k边割边割。边数最少的边割称为。边数最少的边割称为最小边割最小边割。定义定义 设设G是非平凡连通图，若是非平凡连通图，若M是是G的最小边割，则称的最小边割，则称|M|为为G的的边连通度边连通度，记为记为(G)，简记为，简记为。非连通图或平凡图的。非连通图或平凡图的边连通度定义为边连通度定义为0。注：注：对连通图对连通图G，由定义易知，由定义易知， e是是G的割边当且仅当的割边当且仅当e是

27、是G的的1边割。边割。边连通度也可描述为边连通度也可描述为“使图不连通或成为平凡图，至少需要使图不连通或成为平凡图，至少需要删去的边数删去的边数”。例例 (1) (Kn)=n- -1；(2) (Cn)=2，其中，其中Cn为为n圈，圈，n2。例例e1e2定义定义 若一个图的边连通度至少为若一个图的边连通度至少为k，称该图是，称该图是k边连通的边连通的。注：注：(1) 非平凡连通图均是非平凡连通图均是1边连通的边连通的; (2) 图图G是是2边连通的当且仅当边连通的当且仅当G连通、无割边且至少含连通、无割边且至少含 有两个点。有两个点。=1=3=2=3例例 图图G是是1连通的，连通的，1边连通的，

28、边连通的， 但不是但不是2连通的，连通的，2边连通的。边连通的。v5v4v3v2v1v6G二、连通度的性质二、连通度的性质定理定理 对任意的图对任意的图G，有，有 (G)(G)(G)。 证明证明 若若G为平凡图或不连通，则为平凡图或不连通，则(G)=(G)=0，结论显然成，结论显然成立。下设立。下设G为非平凡连通图。为非平凡连通图。对任意的对任意的uV(G)，由于全体与，由于全体与u相关联的边构成的集合是相关联的边构成的集合是G的一个边割集，从而推知的一个边割集，从而推知(G)(G)成立。成立。下面对下面对(G)用归纳法证明用归纳法证明(G)(G)。当当(G)=1时，时，(G)=(G)=1。设

29、对所有满足设对所有满足(G)k (k2)的图的图G，(G)(G)成立。成立。 设设E 是是G的一个的一个k边割，取边割，取eE 。假设假设G为边连通度等于为边连通度等于k的任意一个图。的任意一个图。令令H=G- -e，则，则(H)=k- -1。由归纳假设知，。由归纳假设知，(H)k- -1。情况情况1 H含有完全图作为生成子图，则含有完全图作为生成子图，则G也如此。此时也如此。此时 (G)=|V(G)|- -1=|V(H)|- -1=(H)k- -1。情况情况2 H的任意生成子的任意生成子图均不均不为完全完全图。 设设S是是H的一个的一个(H)顶点割，于是顶点割，于是|S|k- -1。若若G-

30、 -S不连通，则不连通，则(G)|S|k- -1。若若G- -S连通，因连通，因H- -S不连通，故不连通，故e是是G- -S的割边。的割边。此时，若此时，若G- -S恰含两个点，则恰含两个点，则 |V(G)|=|S|+2。于是于是 (G)|V(G)|- -1=|S|+1k。若若G- -S至少含至少含3个点，则个点，则G- -S包含割点包含割点v，于是，于是Sv是是G的顶的顶点割，从而点割，从而 (G)|Sv|k。所以总有所以总有 (G)k=(G)。 例例 满足满足(G)(G)(G)的图的图=1=2=3 定理定理 设设G是具有是具有m条边的条边的n阶连通图，则阶连通图，则证明证明 由握手定理由

31、握手定理得得引理引理 设设G是是n阶简单图，若阶简单图，若(G) ， 则则G必连通。必连通。证明证明 若若G不连通，则不连通，则G至少有两个连通分支，从而必有一至少有两个连通分支，从而必有一个分支个分支H 满足满足|V(H)| 。因因G是简单图，从而是简单图，从而这与已知矛盾，所以这与已知矛盾，所以G必连通。必连通。 定理定理 设设G是是n阶简单图，对正整数阶简单图，对正整数kn，若，若则则G是是k连通的。连通的。于是于是证明证明 任意删去任意删去G中中k- -1个点，记所得之图为个点，记所得之图为H，则，则因因(H)是整数，故是整数，故而而n- -k+1是是H的点数，由引理知的点数，由引理知

32、H是连通的。是连通的。所以所以G是是k连通的。连通的。定理定理 设设G是是n阶简单图，若阶简单图，若(G) ，则，则(G)=(G)。证明证明 显然显然G是连通的。是连通的。若若(G)(G)，则，则(G)(G) 。此时此时G中存在边割中存在边割M，满足，满足|M|=(G)(G) ，故，故上式表明上式表明|V(G1)|p。因此因此G1中存在只与中存在只与G1中的点相邻的点，设此点为中的点相邻的点，设此点为x，于是，于是所以，所以，|V(G1)|(G)+1。同理，同理，|V(G2)|(G)+1。于是，于是，n=|V(G1)|+|V(G2)|2(G)+2。从而从而与已知条件矛盾，所以与已知条件矛盾，所

33、以(G)=(G)。三、三、Menger定理定理Menger定理定理是图的连通性问题的核心定理之一是图的连通性问题的核心定理之一，它揭示了，它揭示了图的连通度与不同顶点对间的不相交路的数目之间的关系。图的连通度与不同顶点对间的不相交路的数目之间的关系。定义定义 图中两条图中两条(x, y)路称为路称为内部不相交的内部不相交的或或独立的独立的，如果此，如果此两条路仅两条路仅x和和y是其公共点。是其公共点。定义定义 设设x与与y是图是图G中两个不同点，称一组点（边）中两个不同点，称一组点（边）分离分离x与与y，是指，是指G中删去这组点（边）后不再有中删去这组点（边）后不再有(x, y)路。路。例例点

34、集点集u1, u3分离点分离点a与与b。边集边集u1b, u2u3, au5分离点分离点a与与b。u5abu4u2u1u3定理定理 (1) 设设x和和y是图是图G中的两个中的两个不相邻点不相邻点，则，则G中分离中分离x和和y的的 最少点数等于独立的最少点数等于独立的(x, y)路的最大数目。路的最大数目。 (2) 设设x和和y是图是图G中的两个不同点，则中的两个不同点，则G中分离中分离x和和y的最的最 少边数等于边不重的少边数等于边不重的(x, y)路的最大数目。路的最大数目。 例例在该图中，独立的在该图中，独立的(u, v)路的最大条数是路的最大条数是2，分离点，分离点u与与v的最的最小点集

35、是小点集是u1, u2，包含，包含2个顶点。个顶点。在该图中，边不重的在该图中，边不重的(u, v)路的最大条数是路的最大条数是3，分离点，分离点u与与v的的最小边集是最小边集是u1v, u2v, u2u3，包含，包含3条边。条边。uu4vu3u2u1定理定理 (1) 一个非平凡图一个非平凡图G是是k (k2)连通的当且仅当连通的当且仅当G的任的任 意两个不同顶点间至少存在意两个不同顶点间至少存在k条独立的路；条独立的路； (2) 一个非平凡图一个非平凡图G是是k (k2)边连通的当且仅当边连通的当且仅当G的的 任意两个不同顶点间至少存在任意两个不同顶点间至少存在k条边不重的路。条边不重的路。

36、例例 设设G是是k连通图，连通图，S是由是由G中任意中任意k个顶点构成的集合。若个顶点构成的集合。若图图H是由是由G通过添加一个新点通过添加一个新点w以及连接以及连接w到到S中所有顶点得中所有顶点得到的新图，求证：到的新图，求证：H是是k连通的。连通的。证明证明 首先，分离属于首先，分离属于G的两个不相邻顶点至少需要的两个不相邻顶点至少需要k个点。个点。注：注：上述定理是上述定理是Whitney在在1932年借助年借助Menger定理给出的。定理给出的。这也是人们熟知的所谓的这也是人们熟知的所谓的“Menger定理定理”。注：注：由由“任意两个不相邻的顶点之间存在任意两个不相邻的顶点之间存在k

37、条独立的路条独立的路”必必能推出能推出“任意两个相邻的顶点之间也存在任意两个相邻的顶点之间也存在k条独立的路条独立的路”。其次，分离其次，分离w与与G的不属于的不属于S的顶点至少需要的顶点至少需要k个点。个点。因此，分离因此，分离H中任意两个不相邻的顶点至少需要中任意两个不相邻的顶点至少需要k个点，从而，个点，从而，H中任意两个不相邻的顶点间至少存在中任意两个不相邻的顶点间至少存在k条独立的路。条独立的路。所以，所以，H中任意两个不同顶点间至少存在中任意两个不同顶点间至少存在k条独立的路，因此条独立的路，因此H是是k连通的。连通的。推论推论 设设G是阶数至少为是阶数至少为3的图，则以下三个命题

38、等价：的图，则以下三个命题等价： (1) G是是2连通的无环图；连通的无环图； (2) G无环且任意两点都位于同一个圈上；无环且任意两点都位于同一个圈上； (3) G无孤立点且任意两条边都在同一个圈上。无孤立点且任意两条边都在同一个圈上。证明证明 (1)(2) 因为因为G是是2连通的，则连通的，则G的任意两个顶点间存的任意两个顶点间存在两条独立的路在两条独立的路P1与与P2，显然，显然P1与与P2构成包含这两个顶点的构成包含这两个顶点的一个圈。一个圈。(2)(3) G中显然没有孤立点。中显然没有孤立点。设设e1与与e2是是G的任意两条边，在的任意两条边，在e1与与e2上分别添加两点上分别添加两

39、点u与与v得得图图H，不难证明，不难证明H是是2连通图。连通图。(3)(1) G显然无环，因为环和任何一条边不在同一个圈上。显然无环，因为环和任何一条边不在同一个圈上。设设u与与v是图是图G的任意两个不相邻顶点，由于的任意两个不相邻顶点，由于G无孤立点，所无孤立点，所以可设以可设e1, e2分别与分别与u, v相关联。相关联。因为因为e1, e2在同一个圈上，所以在同一个圈上，所以u与与v在同一个圈上，因此分离在同一个圈上，因此分离u与与v至少要删去两个点，即至少要删去两个点，即G是是2连通的。连通的。因此，因此，H的任意两个顶点在同一个圈上，即的任意两个顶点在同一个圈上，即u与与v在在H的同

40、一的同一个圈上，从而个圈上，从而e1与与e2在在G的同一个圈上。的同一个圈上。3.3 应用应用 一个通讯网络可以模型化为一个图，图中的点代表通讯一个通讯网络可以模型化为一个图，图中的点代表通讯站，边代表通讯线。这样，图的点（边）连通度对应了网络站，边代表通讯线。这样，图的点（边）连通度对应了网络中容许失灵的通讯站（线）数目的一个界限。即中容许失灵的通讯站（线）数目的一个界限。即图的连通度图的连通度对应系统的可靠性对应系统的可靠性。问题：问题：如何构造出在给定可靠性的条件下使成本尽量低的如何构造出在给定可靠性的条件下使成本尽量低的系系统统? ?图论模型：图论模型：对一个赋权图对一个赋权图G，试确

41、定试确定G的一个具有最小权的的一个具有最小权的k 连通生成子图。连通生成子图。注：注：(1) 对对k=1，此问题即为求最小生成树的问题；此问题即为求最小生成树的问题； (2) 对对k1，这是一个还未解决的困难问题。，这是一个还未解决的困难问题。当当G是完全图，各边的权均为是完全图，各边的权均为1的特殊情况，问题是有解的。的特殊情况，问题是有解的。此时即求边数最少的具有此时即求边数最少的具有n个顶点的个顶点的k连通图连通图G。由前面定理知，由前面定理知，m条边的条边的n阶阶k连通图满足连通图满足所以若能构造出边数达到所以若能构造出边数达到 的的n阶阶k连通图，则边数将已连通图，则边数将已达到最少

42、。达到最少。因此因此1962年，数学家年，数学家Harary构造了这类图构造了这类图Hk, n，称为，称为Harary图图。Hk, n的构造的构造设设V(Hk, n)=0, 1, 2, n- -1。情况情况1. k为偶为偶，设，设 k=2r。此时此时0与与 1, 2, r 连线；连线；1与与2, 3, r+1连线；连线；n- -1与与0, 1, r-1连线。如下图中的连线。如下图中的H4, 8 所示。所示。 情况情况2. k=2r+1，n为偶为偶。先作。先作H2r, n ，再在再在i与与(i+n/2)间添加边间添加边 i(i+n/2) (0in/2)。如下图中的如下图中的H5, 8 所示。所示

43、。01765432 H4, 8 01765432 H5, 8 情况情况3. k=2r+1，n为奇为奇。先作。先作H2r, n，再在再在0和和(n- -1)/2， (n+1)/2，以及以及i和和i+(n+1)/2 (1i(n- -1)/2)间添加边。如下图中的间添加边。如下图中的H5, 9所示。所示。012345678H5, 9可以证明：可以证明：Hk, n是是k连通的。连通的。3.4 图的宽距离和宽直径图的宽距离和宽直径一、问题背景一、问题背景分析评价互联网络的性能有多个指标，如网络的分析评价互联网络的性能有多个指标，如网络的开销开销(通信通信与材料开销与材料开销)， 网络的网络的容错性容错性

44、(连通性连通性)，网络中信息传递的，网络中信息传递的传输延迟传输延迟等。等。所谓所谓传输延迟传输延迟，又称为，又称为时间延迟时间延迟，是指信息从信息源传到，是指信息从信息源传到目的地所需要的时间。目的地所需要的时间。如何度量网络的传输延迟？如何度量网络的传输延迟？信息从信息源到目的地需要经过若干中间站存储和转发。信息从信息源到目的地需要经过若干中间站存储和转发。因此，信息传输延迟可以用图的顶点间距离来度量。当然，因此，信息传输延迟可以用图的顶点间距离来度量。当然，每条边的长度可以定义为每条边的长度可以定义为1。于是，网络的最大通信延迟可以通过图的直径来度量。图于是，网络的最大通信延迟可以通过图

45、的直径来度量。图的直径定义为：的直径定义为：例例 d(Pn)=n- -1， d(Cn)=n/2，d(Kn)=1。在信息的单路径传输中，分析通信延迟，只需要考虑网络的在信息的单路径传输中，分析通信延迟，只需要考虑网络的直径即可。但是，如果要一次传输的信息量较大，远远超出直径即可。但是，如果要一次传输的信息量较大，远远超出链路带宽，就需要所谓的链路带宽，就需要所谓的分包传送分包传送。分包传送，就是按照带宽要求，把信息在起点进行分割打包，分包传送，就是按照带宽要求，把信息在起点进行分割打包，每个信息小包按照若干内部不交路从起点传到终点。每个信息小包按照若干内部不交路从起点传到终点。上世纪上世纪90年

46、代初，年代初，D. Frank Hsu等图论学者和一些计算机专等图论学者和一些计算机专家从图论角度对信息分包传送的若干问题展开研究。家从图论角度对信息分包传送的若干问题展开研究。研究的典型问题是：研究的典型问题是：(1) 分包传送的通信延迟度量；分包传送的通信延迟度量；(2) 分包传送的路由选择，即网络中平行寻径算法；分包传送的路由选择，即网络中平行寻径算法；(3) 互联网络的设计与网络结构分析问题；互联网络的设计与网络结构分析问题；(4) 基于分包传送下互联网络的容错分析。基于分包传送下互联网络的容错分析。为了描述通信延迟，为了描述通信延迟，D. Frank Hsu等拓展了图的普通距离和等拓

47、展了图的普通距离和普通直径的概念，提出了用普通直径的概念，提出了用宽距离宽距离来描述点对间信息传递的来描述点对间信息传递的通信延迟，用所谓的通信延迟，用所谓的宽直径宽直径来描述网络的最大通信延迟。来描述网络的最大通信延迟。由此而形成的组合网络理论研究成为最近几十年来图论和通由此而形成的组合网络理论研究成为最近几十年来图论和通信网络相结合的热点研究问题。信网络相结合的热点研究问题。二、宽直径二、宽直径定义定义 设设x和和y是图是图G中两个不同点，中两个不同点，Cw (x, y)表示表示G中中w条独条独立的立的(x, y)路构成的路族，称之为路构成的路族，称之为x-y容器容器，简称，简称容器容器；

48、w称称为该容器的为该容器的宽度宽度。容器。容器Cw (x, y)中最长路的路长定义为该容中最长路的路长定义为该容器的器的长度长度，记为，记为l (Cw(x, y)。在该图中，在该图中，G的一个宽度为的一个宽度为3的的u-v容器为：容器为：uvGP3P2P1该容器的长度为：该容器的长度为：例例定义定义 设设x, yV(G)，定义，定义x与与y间所有宽度为间所有宽度为w的容器的的容器的长度的最小值为长度的最小值为x与与y的的w宽距离宽距离，记为，记为dw(x , y)。即。即在该图中，在该图中，u与与v间的间的3宽距离为：宽距离为：uvGP3P2P1例例定义定义 设设G是是w连通的，连通的，G的所

49、有点对间的的所有点对间的w宽距离的最大值，宽距离的最大值，称为称为G的的w宽直径宽直径，记为，记为dw (G)。即。即例例 求求n点圈点圈Cn和和n阶完全图阶完全图Kn的宽直径，其中的宽直径，其中n3。分析：分析：对于对于Cn来说，连通度为来说，连通度为2，因此，可以求它的，因此，可以求它的1宽宽直径和直径和2宽直径；而对于宽直径；而对于Kn来说，连通度是来说，连通度是n- -1，所以，所以，可以考虑它的可以考虑它的1到到n- -1宽直径。宽直径。注：注：1宽距离就是普通距离，宽距离就是普通距离，1宽直径就是普通直径。宽直径就是普通直径。注：注：若图若图G是是k连通的连通的, G中任意两点间均

50、存在中任意两点间均存在k条内部不相条内部不相交的路交的路, 所以所以k连通图的连通图的k宽直径宽直径, k- -1宽直径宽直径, 1宽直径宽直径均均存在。存在。解解：(1) 显然显然因为因为Cn中任意点对间只有一个唯一的宽度为中任意点对间只有一个唯一的宽度为2的容器，点的容器，点对间的对间的2宽距离就是该点对的唯一容器的长度。当宽距离就是该点对的唯一容器的长度。当x与与y相相邻时，容器的长度最长为邻时，容器的长度最长为n- -1, 所以，由宽直径定义得：所以，由宽直径定义得：(2) 显然，显然，d1(Kn)=1。对于任意的对于任意的w (2wn- -1)，任意点对间的，任意点对间的w宽距离为宽

51、距离为2。所以，有所以，有注：注：从定义看出，对一般图来说，计算从定义看出，对一般图来说，计算w宽直径是一件很困宽直径是一件很困难的工作。难的工作。对宽直径的研究，主要有两方面：对宽直径的研究，主要有两方面：(1) 对一般图而言，研究对一般图而言，研究w宽直径的界；宽直径的界；(2) 根据各种互联网络的结构特征，确定其宽直径。根据各种互联网络的结构特征，确定其宽直径。定理定理 对于任意连通图对于任意连通图G，若图，若图G的的w宽直径存在，则宽直径存在，则定理定理 设设G是是n阶阶w连通图连通图(w2)，则，则而且上界和下界都能达到。而且上界和下界都能达到。定理定理 设设G是是w连通连通w正则图正则图(w2)，则，则Thank you!个人观点供参考，欢迎讨论