第3章-图论PPT优秀课件.ppt

yzwang@第三章第三章 图的连通度图的连通度l 割边、割点和块割边、割点和块l 连通度连通度l 应用应用l 图的宽距离和宽直径图的宽距离和宽直径G3G4删去任意一条边后仍连通，但删去任意一条边后仍连通，但删去点删去点u后便不连通后便不连通考察考察G3和和G4删去任意一条边或任意一个点后仍连通删去任意一条边或任意一个点后仍连通，但从直观上，但从直观上看，看，G4的连通程度比的连通程度比G3高高删去任意一条边后便不连通删去任意一条边后便不连通G1uG2 图的连通性，主要用来刻画图的连通程度，其意义是图的连通性，主要用来刻画图的连通程度，其意义是 理论意义：理论意义：图的连通程度的高低，是图结构性质的重要图的连通程度的高低，是图结构性质的重要表征，图的许多性质都与其相关，例如：连通图中任意两点表征，图的许多性质都与其相关，例如：连通图中任意两点间不相交路的条数就与图的连通程度有关间不相交路的条数就与图的连通程度有关 实际意义：实际意义：图的连通程度的高低，对应于通信网络图的连通程度的高低，对应于通信网络“可可靠性程度靠性程度”的高低 网络可靠性，是指网络运作的好坏程度，即指如计算机网络可靠性，是指网络运作的好坏程度，即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。

网络、通信网络等对某个组成部分崩溃的容忍程度 网络可靠性，网络可靠性， 是用可靠性参数来描述的，其主要分为是用可靠性参数来描述的，其主要分为“确定性参数确定性参数”与与“概率性参数概率性参数”研究图的连通性的意义研究图的连通性的意义 确定性参数主要考虑网络在最坏情况下的可靠性度量，确定性参数主要考虑网络在最坏情况下的可靠性度量，常称为网络拓扑的常称为网络拓扑的“容错性度量容错性度量”，通常用图论概念给出，，通常用图论概念给出，其中，本章将介绍的图的连通度就是网络确定性参数之一其中，本章将介绍的图的连通度就是网络确定性参数之一 近年来，人们又提出了近年来，人们又提出了“坚韧度坚韧度”、、“核度核度”、、“整整度度”等描述网络容错性的参数等描述网络容错性的参数 概率性参数主要考虑网络中处理器与信关以随机的、概率性参数主要考虑网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下，网络的可靠彼此独立的按某种确定性概率损坏的情况下，网络的可靠性度量，常称为网络拓扑的性度量，常称为网络拓扑的“可靠性度量可靠性度量”3.1 割边、割点和块割边、割点和块定义定义 设设e是图是图G的一条边，若的一条边，若ω(G- -e)>ω(G)，则称，则称e为为G的的割割边边。

注：注：若若G连通，则割边是指删去后使连通，则割边是指删去后使G不连通的边，故非平不连通的边，故非平凡树的每条边均为割边凡树的每条边均为割边例例 下图中，边下图中，边e1和和e2为割边，而其余边均不为割边为割边，而其余边均不为割边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易知易知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的割边注：注：以上定理表明圈中的边一定不是割边，所以删去圈中的以上定理表明圈中的边一定不是割边，所以删去圈中的边不会破坏图的连通性边不会破坏图的连通性推论推论 设设e是连通图是连通图G的任意一条边，若的任意一条边，若e含在含在G的某圈中，则的某圈中，则G- -e仍连通例例 求证求证：： (1) 若若G的每个顶点的度数均为偶数，则的每个顶点的度数均为偶数，则G没有割边没有割边; (2) 若若G为为k正则二部图正则二部图(k≥2)，则，则G无割边证明证明 (1) 若不然，设若不然，设e=uv为为G的割边则则G- -e的含有顶点的含有顶点u(或或v)的那个分支中点的那个分支中点u(或或v)的度数必为奇的度数必为奇数，而其余点的度数为偶数，与数，而其余点的度数为偶数，与“度数为奇数的顶点的个数度数为奇数的顶点的个数为偶数为偶数”相矛盾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但是因但是因k≥2，所以等式不能成立！因此，，所以等式不能成立！因此，e一定不是割边一定不是割边二、割点及其性质二、割点及其性质定义定义 图图G=(V, E)的顶点的顶点v称为称为割点割点，如果，如果E可划分为两个非可划分为两个非空子集空子集E1和和E2，使得，使得G[E1]和和G[E2]恰有一个公共顶点恰有一个公共顶点v例例 图中点图中点u1, u2, u3和和u4是割是割点，其余点均不为割点点，其余点均不为割点u1u2u3u4注：注：(1) 若若ω(G- -v)>ω(G)，则，则v必为必为G的割点 (2) 若若G无环，则无环，则v是是G的割点当且仅当的割点当且仅当 ω(G- -v)>ω(G) (3) 若无环图若无环图G连通，则割点是指删去该点使连通，则割点是指删去该点使G不连通的不连通的 点。

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

支设设V1是其中一个连通分支的顶点集，是其中一个连通分支的顶点集，V2为其余顶点构成的集为其余顶点构成的集合对于任意的对于任意的x∈∈V1，，y∈∈V2，如果点，如果点v不在某一条不在某一条(x, y)路上，路上，那么该路也是那么该路也是G- -v中连接中连接x与与y的一条路，这与的一条路，这与x, y处于处于G- -v的的不同连通分支矛盾不同连通分支矛盾例例 求证：无环非平凡连通图至少有两个点不是割点求证：无环非平凡连通图至少有两个点不是割点证明证明 由于由于G是无环非平凡连通图，所以存在非平凡生成树是无环非平凡连通图，所以存在非平凡生成树非平凡生成树至少两片树叶，它们不能为生成树的割点非平凡生成树至少两片树叶，它们不能为生成树的割点显然，它们也不能为显然，它们也不能为G的割点证明证明 设设T是是n阶连通简单图阶连通简单图G的任意一棵生成树的任意一棵生成树例例 求证：恰有两个非割点的连通简单图是一条路求证：恰有两个非割点的连通简单图是一条路一个简单图的任意生成树为路，则该图为圈或路一个简单图的任意生成树为路，则该图为圈或路由于由于G有有n- -2个割点，所以，个割点，所以，T有有n- -2个割点，因此个割点，因此T只有两片只有两片树叶，所以树叶，所以T是一条路。

是一条路这说明，这说明，G的任意生成树为路的任意生成树为路若为圈，则若为圈，则G没有割点，矛盾！所以没有割点，矛盾！所以G为路例例 求证：若求证：若v是简单图是简单图G的割点，则的割点，则v不是不是G的补图的割点的补图的割点证明证明 容易验证，容易验证，因为因为v是是G的割点，所以的割点，所以 G- -v一定不是连通图从而一定不是连通图从而G- -v的补图的补图是连通图是连通图因此，在因此，在G的补图中删去顶点的补图中删去顶点v不会增加图的连通分支数不会增加图的连通分支数所以，所以，v不是不是G的补图的割点的补图的割点三、块及其性质三、块及其性质定义定义 没有割点的连通图称为没有割点的连通图称为块图块图，简称，简称块块若图G的子图的子图B是块，且是块，且G中没有真包含中没有真包含B的子图也是块，则称的子图也是块，则称B是是G的的块块注注：： (1) 仅有一条边的块，仅有一条边的块，要么是割边，要么是环；要么是割边，要么是环； (2) 仅有一个点的块，要么是孤立点，要么是环；仅有一个点的块，要么是孤立点，要么是环； (3) 至少有两个点的块无环；至少有两个点的块无环； (4) 至少有三个点的块无割边。

至少有三个点的块无割边例例 图图G如图如图(a)所示，所示，G的所有块如图的所有块如图(b)所示a)(b)定理定理 设图设图G的阶至少为的阶至少为3，则，则G是块当且仅当是块当且仅当G无环并且任意无环并且任意两点都位于同一个圈上两点都位于同一个圈上证明证明 充分性充分性 此时此时G显然连通显然连通若若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必然在某圈中必然在某圈中设结论对距离小于设结论对距离小于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的最后一个公共点的最后一个公共点于是于是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无无环，因，因为环和任何一条和任何一条边都不可能在一个圈上都不可能在一个圈上此时，必然任意两个此时，必然任意两个点点也在同一个圈上，因此也在同一个圈上，因此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的割点当且仅当的割点当且仅当v至少属于至少属于G的两个不同的块的两个不同的块证明证明 必要性必要性 设设v是是G的割点由割点定义知由割点定义知E(G)可以划分为两个边子集可以划分为两个边子集E1与与E2使得使得G[E1]与与G[E2]有唯一公共顶点有唯一公共顶点v。

设设B1与与B2分别是分别是G[E1]和和G[E2]中包含中包含v的块，显然它们也是的块，显然它们也是G的块因此的块因此v至少属于至少属于G的两个不同块的两个不同块充分性充分性 设点设点v属于属于G的两个不同块的两个不同块B1和和B2如果如果B1和和B2其中一个是环，显然其中一个是环，显然v是割点现在假设现在假设B1与与B2都不是环都不是环显然，显然，B1∪∪B2∪∪P 无割点这与无割点这与B1与与B2是块矛盾！是块矛盾！那么那么B1与与B2分别至少有两个顶点分别至少有两个顶点假如假如v不是割点，在不是割点，在B1与与B2中分别找异于中分别找异于v的一个点的一个点x与与y，， 则则在在G- -v中有连接中有连接x与与y的路的路P注：注：两个不同块的公共顶点只能是割点，即块与块只能由割两个不同块的公共顶点只能是割点，即块与块只能由割点相联结，因此可以通过割点搜寻块点相联结，因此可以通过割点搜寻块定义定义 设设G是非平凡连通图，是非平凡连通图，B1, B2,…, Bk是是G的全部块，而的全部块，而v1, 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的只含一个割点的块的只含一个割点的块B1B5B6B3B2B4125634GB1B2B3B7B4B5B6125634bc(G)B73.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) 若若G是非平凡连通图，则是非平凡连通图，则v是是G的割点当且仅当的割点当且仅当{v}是是 G的的1顶点割。

顶点割 (2) 完全图没有顶点割，实际上也只有以完全图为生成完全图没有顶点割，实际上也只有以完全图为生成 子图的图没有顶点割子图的图没有顶点割定义定义 对对n阶非平凡连通图阶非平凡连通图G，若，若G存在顶点割，则称存在顶点割，则称G的最小的最小顶点割中的点数为顶点割中的点数为G的的连通度连通度；否则称；否则称n- -1为其连通度为其连通度G的的连通度符号表示为连通度符号表示为κ(G)，简记为，简记为κ；非连通图或平凡图的连；非连通图或平凡图的连通度定义为通度定义为0连通度也可描述为连通度也可描述为“使图不连通或成为平凡图，至少需要删使图不连通或成为平凡图，至少需要删去的点数去的点数”例例 (1) κ(Kn)=n- -1；；(2) κ(Cn)=2，其中，其中Cn为为n圈，圈，n≥3例例 求下列各图的连通度求下列各图的连通度G1G2G3G4解解 κ(G1)=1，，κ(G2)=3，，κ(G3)=1，，κ(G4)=2定义定义 若一个图的连通度至少为若一个图的连通度至少为k，则称该图是，则称该图是k连通的连通的注：注：(1) 非平凡连通图均是非平凡连通图均是1连通的。

连通的 (2) 图图G是是2连通的当且仅当连通的当且仅当G连通、无割点且至少含有连通、无割点且至少含有3 个点 (3) K2连通、无割点，但连通度为连通、无割点，但连通度为1定义定义 设设G为连通图，称使为连通图，称使G- -E ′不连通的不连通的G的边子集的边子集E ′为为G的的边割边割，含有，含有k条边的边割称为条边的边割称为k边割边割边数最少的边割称为边数最少的边割称为最小边割最小边割定义定义 设设G是非平凡连通图，若是非平凡连通图，若M是是G的最小边割，则称的最小边割，则称|M|为为G的的边连通度边连通度，，记为记为λ(G)，简记为，简记为λ非连通图或平凡图的非连通图或平凡图的边连通度定义为边连通度定义为0注：注：对连通图对连通图G，由定义易知，，由定义易知， e是是G的割边当且仅当的割边当且仅当{e}是是G的的1边割边连通度也可描述为边连通度也可描述为“使图不连通或成为平凡图，至少需要使图不连通或成为平凡图，至少需要删去的边数删去的边数”例例 (1) λ(Kn)=n- -1；；(2) λ(Cn)=2，其中，其中Cn为为n圈，圈，n≥2。

例例e1e2定义定义 若一个图的边连通度至少为若一个图的边连通度至少为k，称该图是，称该图是k边连通的边连通的注：注：(1) 非平凡连通图均是非平凡连通图均是1边连通的边连通的; (2) 图图G是是2边连通的当且仅当边连通的当且仅当G连通、无割边且至少含连通、无割边且至少含 有两个点有两个点λ=1λ=3λ=2λ=3例例 图图G是是1连通的，连通的，1边连通的，边连通的， 但不是但不是2连通的，连通的，2边连通的边连通的v5v4v3v2v1v6G二、连通度的性质二、连通度的性质定理定理 对任意的图对任意的图G，有，有 κ(G)≤λ(G)≤δ(G) 证明证明 若若G为平凡图或不连通，则为平凡图或不连通，则κ(G)=λ(G)=0，结论显然成，结论显然成立下设G为非平凡连通图为非平凡连通图对任意的对任意的u∈∈V(G)，由于全体与，由于全体与u相关联的边构成的集合是相关联的边构成的集合是G的一个边割集，从而推知的一个边割集，从而推知λ(G)≤δ(G)成立。

成立下面对下面对λ(G)用归纳法证明用归纳法证明κ(G)≤λ(G)当当λ(G)=1时，时，κ(G)=λ(G)=1设对所有满足设对所有满足λ(G)

若若G- -S至少含至少含3个点，则个点，则G- -S包含割点包含割点v，于是，于是S∪∪{v}是是G的顶的顶点割，从而点割，从而 κ(G)≤|S∪∪{v}|≤k所以总有所以总有 κ(G)≤k=λ(G) 例例 满足满足κ(G)<λ(G)<δ(G)的图的图κ=1λ=2δ=3 定理定理 设设G是具有是具有m条边的条边的n阶连通图，则阶连通图，则证明证明 由握手定理由握手定理得得引理引理 设设G是是n阶简单图，若阶简单图，若δ(G)≥ ，， 则则G必连通证明证明 若若G不连通，则不连通，则G至少有两个连通分支，从而必有一至少有两个连通分支，从而必有一个分支个分支H 满足满足|V(H)|≤ 因因G是简单图，从而是简单图，从而这与已知矛盾，所以这与已知矛盾，所以G必连通 定理定理 设设G是是n阶简单图，对正整数阶简单图，对正整数k

是连通的所以所以G是是k连通的定理定理 设设G是是n阶简单图，若阶简单图，若δ(G)≥ ，则，则λ(G)=δ(G)证明证明 显然显然G是连通的是连通的若若λ(G)≠δ(G)，则，则λ(G)<δ(G) 此时此时G中存在边割中存在边割M，满足，满足|M|=λ(G)<δ(G) ，同时，同时G- -M是由两是由两个不相交的子图个不相交的子图G1和和G2所构成设设M中的边和中的边和G1的的p个点相关联，显然个点相关联，显然 p≤λ(G) 由握手定理可得由握手定理可得由于由于δ(G)>λ(G) ，故，故上式表明上式表明|V(G1)|>p因此因此G1中存在只与中存在只与G1中的点相邻的点，设此点为中的点相邻的点，设此点为x，于是，于是所以，所以，|V(G1)|≥δ(G)+1同理，同理，|V(G2)|≥δ(G)+1于是，于是，n=|V(G1)|+|V(G2)|≥2δ(G)+2从而从而与已知条件矛盾，所以与已知条件矛盾，所以λ(G)=δ(G)三、三、Menger定理定理Menger定理定理是图的连通性问题的核心定理之一是图的连通性问题的核心定理之一，它揭示了，它揭示了图的连通度与不同顶点对间的不相交路的数目之间的关系。

图的连通度与不同顶点对间的不相交路的数目之间的关系定义定义 图中两条图中两条(x, y)路称为路称为内部不相交的内部不相交的或或独立的独立的，如果此，如果此两条路仅两条路仅x和和y是其公共点是其公共点定义定义 设设x与与y是图是图G中两个不同点，称一组点（边）中两个不同点，称一组点（边）分离分离x与与y，是指，是指G中删去这组点（边）后不再有中删去这组点（边）后不再有(x, y)路例例点集点集{u1, u3}分离点分离点a与与b边集边集{u1b, u2u3, au5}分离点分离点a与与bu5abu4u2u1u3定理定理 (1) 设设x和和y是图是图G中的两个中的两个不相邻点不相邻点，则，则G中分离中分离x和和y的的 最少点数等于独立的最少点数等于独立的(x, y)路的最大数目路的最大数目 (2) 设设x和和y是图是图G中的两个不同点，则中的两个不同点，则G中分离中分离x和和y的最的最 少边数等于边不重的少边数等于边不重的(x, y)路的最大数目路的最大数目 例例在该图中，独立的在该图中，独立的(u, v)路的最大条数是路的最大条数是2，分离点，分离点u与与v的最的最小点集是小点集是{u1, u2}，包含，包含2个顶点。

个顶点在该图中，边不重的在该图中，边不重的(u, v)路的最大条数是路的最大条数是3，分离点，分离点u与与v的的最小边集是最小边集是{u1v, u2v, u2u3}，包含，包含3条边uu4vu3u2u1定理定理 (1) 一个非平凡图一个非平凡图G是是k (k≥2)连通的当且仅当连通的当且仅当G的任的任 意两个不同顶点间至少存在意两个不同顶点间至少存在k条独立的路；条独立的路； (2) 一个非平凡图一个非平凡图G是是k (k≥2)边连通的当且仅当边连通的当且仅当G的的 任意两个不同顶点间至少存在任意两个不同顶点间至少存在k条边不重的路条边不重的路例例 设设G是是k连通图，连通图，S是由是由G中任意中任意k个顶点构成的集合若个顶点构成的集合若图图H是由是由G通过添加一个新点通过添加一个新点w以及连接以及连接w到到S中所有顶点得中所有顶点得到的新图，求证：到的新图，求证：H是是k连通的证明证明 首先，分离属于首先，分离属于G的两个不相邻顶点至少需要的两个不相邻顶点至少需要k个点注：注：上述定理是上述定理是Whitney在在1932年借助年借助Menger定理给出的。

定理给出的这也是人们熟知的所谓的这也是人们熟知的所谓的“Menger定理定理”注：注：由由“任意两个不相邻的顶点之间存在任意两个不相邻的顶点之间存在k条独立的路条独立的路”必必能推出能推出“任意两个相邻的顶点之间也存在任意两个相邻的顶点之间也存在k条独立的路条独立的路”其次，分离其次，分离w与与G的不属于的不属于S的顶点至少需要的顶点至少需要k个点因此，分离因此，分离H中任意两个不相邻的顶点至少需要中任意两个不相邻的顶点至少需要k个点，从而，个点，从而，H中任意两个不相邻的顶点间至少存在中任意两个不相邻的顶点间至少存在k条独立的路条独立的路所以，所以，H中任意两个不同顶点间至少存在中任意两个不同顶点间至少存在k条独立的路，因此条独立的路，因此H是是k连通的推论推论 设设G是阶数至少为是阶数至少为3的图，则以下三个命题等价：的图，则以下三个命题等价： (1) G是是2连通的无环图；连通的无环图； (2) G无环且任意两点都位于同一个圈上；无环且任意两点都位于同一个圈上； (3) G无孤立点且任意两条边都在同一个圈上无孤立点且任意两条边都在同一个圈上。

证明证明 (1)(2) 因为因为G是是2连通的，则连通的，则G的任意两个顶点间存的任意两个顶点间存在两条独立的路在两条独立的路P1与与P2，显然，显然P1与与P2构成包含这两个顶点的构成包含这两个顶点的一个圈(2)(3) G中显然没有孤立点中显然没有孤立点设设e1与与e2是是G的任意两条边，在的任意两条边，在e1与与e2上分别添加两点上分别添加两点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的同一的同一个圈上，从而个圈上，从而e1与与e2在在G的同一个圈上的同一个圈上。

3.3 应用应用 一个通讯网络可以模型化为一个图，图中的点代表通讯一个通讯网络可以模型化为一个图，图中的点代表通讯站，边代表通讯线这样，图的点（边）连通度对应了网络站，边代表通讯线这样，图的点（边）连通度对应了网络中容许失灵的通讯站（线）数目的一个界限即中容许失灵的通讯站（线）数目的一个界限即图的连通度图的连通度对应系统的可靠性对应系统的可靠性问题：问题：如何构造出在给定可靠性的条件下使成本尽量低的如何构造出在给定可靠性的条件下使成本尽量低的系系统统? ?图论模型：图论模型：对一个赋权图对一个赋权图G，，试确定试确定G的一个具有最小权的的一个具有最小权的k 连通生成子图连通生成子图注：注：(1) 对对k=1，，此问题即为求最小生成树的问题；此问题即为求最小生成树的问题； (2) 对对k>1，这是一个还未解决的困难问题这是一个还未解决的困难问题当当G是完全图，各边的权均为是完全图，各边的权均为1的特殊情况，问题是有解的的特殊情况，问题是有解的此时即求边数最少的具有此时即求边数最少的具有n个顶点的个顶点的k连通图连通图G由前面定理知，由前面定理知，m条边的条边的n阶阶k连通图满足连通图满足所以若能构造出边数达到所以若能构造出边数达到 的的n阶阶k连通图，则边数将已连通图，则边数将已达到最少。

达到最少因此因此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) (0≤i

等所谓所谓传输延迟传输延迟，又称为，又称为时间延迟时间延迟，是指信息从信息源传到，是指信息从信息源传到目的地所需要的时间目的地所需要的时间如何度量网络的传输延迟？如何度量网络的传输延迟？信息从信息源到目的地需要经过若干中间站存储和转发信息从信息源到目的地需要经过若干中间站存储和转发因此，信息传输延迟可以用图的顶点间距离来度量当然，因此，信息传输延迟可以用图的顶点间距离来度量当然，每条边的长度可以定义为每条边的长度可以定义为1于是，网络的最大通信延迟可以通过图的直径来度量图于是，网络的最大通信延迟可以通过图的直径来度量图的直径定义为：的直径定义为：例例 d(Pn)=n- -1，， d(Cn)=[n/2]，，d(Kn)=1在信息的单路径传输中，分析通信延迟，只需要考虑网络的在信息的单路径传输中，分析通信延迟，只需要考虑网络的直径即可但是，如果要一次传输的信息量较大，远远超出直径即可但是，如果要一次传输的信息量较大，远远超出链路带宽，就需要所谓的链路带宽，就需要所谓的分包传送分包传送分包传送，就是按照带宽要求，把信息在起点进行分割打包，分包传送，就是按照带宽要求，把信息在起点进行分割打包，每个信息小包按照若干内部不交路从起点传到终点。

每个信息小包按照若干内部不交路从起点传到终点上世纪上世纪90年代初，年代初，D. Frank Hsu等图论学者和一些计算机专等图论学者和一些计算机专家从图论角度对信息分包传送的若干问题展开研究家从图论角度对信息分包传送的若干问题展开研究研究的典型问题是：研究的典型问题是：(1) 分包传送的通信延迟度量；分包传送的通信延迟度量；(2) 分包传送的路由选择，即网络中平行寻径算法；分包传送的路由选择，即网络中平行寻径算法；(3) 互联网络的设计与网络结构分析问题；互联网络的设计与网络结构分析问题；(4) 基于分包传送下互联网络的容错分析基于分包传送下互联网络的容错分析为了描述通信延迟，为了描述通信延迟，D. Frank Hsu等拓展了图的普通距离和等拓展了图的普通距离和普通直径的概念，提出了用普通直径的概念，提出了用宽距离宽距离来描述点对间信息传递的来描述点对间信息传递的通信延迟，用所谓的通信延迟，用所谓的宽直径宽直径来描述网络的最大通信延迟来描述网络的最大通信延迟由此而形成的组合网络理论研究成为最近几十年来图论和通由此而形成的组合网络理论研究成为最近几十年来图论和通信网络相结合的热点研究问题。

信网络相结合的热点研究问题二、宽直径二、宽直径定义定义 设设x和和y是图是图G中两个不同点，中两个不同点，Cw (x, y)表示表示G中中w条独条独立的立的(x, y)路构成的路族，称之为路构成的路族，称之为x-y容器容器，简称，简称容器容器；；w称称为该容器的为该容器的宽度宽度容器Cw (x, y)中最长路的路长定义为该容中最长路的路长定义为该容器的器的长度长度，记为，记为l (Cw(x, y))在该图中，在该图中，G的一个宽度为的一个宽度为3的的u-v容器为：容器为：uvGP3P2P1该容器的长度为：该容器的长度为：例例定义定义 设设x, y∈∈V(G)，定义，定义x与与y间所有宽度为间所有宽度为w的容器的的容器的长度的最小值为长度的最小值为x与与y的的w宽距离宽距离，记为，记为dw(x , y)即在该图中，在该图中，u与与v间的间的3宽距离为：宽距离为：uvGP3P2P1例例定义定义 设设G是是w连通的，连通的，G的所有点对间的的所有点对间的w宽距离的最大值，宽距离的最大值，称为称为G的的w宽直径宽直径，记为，记为dw (G)即例例 求求n点圈点圈Cn和和n阶完全图阶完全图Kn的宽直径，其中的宽直径，其中n≥3。

分析：分析：对于对于Cn来说，连通度为来说，连通度为2，因此，可以求它的，因此，可以求它的1宽宽直径和直径和2宽直径；而对于宽直径；而对于Kn来说，连通度是来说，连通度是n- -1，所以，，所以，可以考虑它的可以考虑它的1到到n- -1宽直径注：注：1宽距离就是普通距离，宽距离就是普通距离，1宽直径就是普通直径宽直径就是普通直径注：注：若图若图G是是k连通的连通的, G中任意两点间均存在中任意两点间均存在k条内部不相条内部不相交的路交的路, 所以所以k连通图的连通图的k宽直径宽直径, k- -1宽直径宽直径,…, 1宽直径宽直径均均存在解解：：(1) 显然显然因为因为Cn中任意点对间只有一个唯一的宽度为中任意点对间只有一个唯一的宽度为2的容器，点的容器，点对间的对间的2宽距离就是该点对的唯一容器的长度当宽距离就是该点对的唯一容器的长度当x与与y相相邻时，容器的长度最长为邻时，容器的长度最长为n- -1, 所以，由宽直径定义得：所以，由宽直径定义得：(2) 显然，显然，d1(Kn)=1对于任意的对于任意的w (2≤w≤n- -1)，任意点对间的，任意点对间的w宽距离为宽距离为2。

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