第3章 图论 PPT.ppt

第三章图的连通度割边、割点和块图的宽距离和宽直径1G3G4删去任意一条边后仍连通,但删去点u后便不连通考察G3和G4删去任意一条边或任意一个点后仍连通,但从直观上看,G4的连通程度比G3高。删去任意一条边后便不连通G1uG22图的连通性,主要用来刻画图的连通程度,其意义是理论意义:图的连通程度的高低,是图结构性质的重要表征,图的许多性质都与其相关,例如:连通图中任意两点间不相交路的条数就与图的连通程度有关。实际意义:图的连通程度的高低,对应于通信网络“可靠性程度”的高低。网络可靠性,是指网络运作的好坏程度,即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。网络可靠性,是用可靠性参数来描述的,其主要分为“确定性参数”与“概率性参数”。研究图的连通性的意义确定性参数主要考虑网络在最坏情况下的可靠性度量,常称为网络拓扑的“容错性度量”,通常用图论概念给出,其中,本章将介绍的图的连通度就是网络确定性参数之一。近年来,人们又提出了“坚韧度”、“核度”、“整度”等描述网络容错性的参数。概率性参数主要考虑网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下,网络的可靠性度量,常称为网络拓扑的“可靠性度量”。、割点和块定义设e是图G的一条边,若ω(G-e)>ω(G),则称e为G的割边。注:若G连通,则割边是指删去后使G不连通的边,故非平凡树的每条边均为割边。例下图中,边e1和e2为割边,而其余边均不为割边。e1e2一、割边及其性质5定理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)路;6充分性设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无割边。7证明(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一定不是割边。8大家有疑问的,可以询问和交流可以互相讨论下,但要小声点9二、割点及其性质定义图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不连通的点。10