第四章割集ppt课件.ppt

《第四章割集ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章割集研究图的连通性的意义研究图的连通性，主要研究图的连通程度的刻画，其意义是：图论意义：图的连通程度的高低，是图结构性质的重要表征，图的许多性质都与其相关，例如：连通图中任意两点间不相交路的条数就与图的连通程度有关。实际意义：图的连通程度的高低，在与之对应的通信网络中，对应于网络“可靠性程度”的高低。网络可靠性，是指网络运作的好坏程度，即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。网络可靠性，是用可靠性参数来描述的。参数主要分确定性参数与概率性参数。确定性参数主要考虑网络在最坏情况下的可靠

2、性度量，常称为网络拓扑的“容错性度量”，通常用图论概念给出。边割集简介边割集跟回路、树等概念一样，是图论中重要概念。在应用上，它是电路网络图论的基本概念之一。所以，下面作简单介绍。4.1割集与断集(一)割边及其性质定义1称边e为图G的一条割边，如果在图G中删去e后，图G的连通分支数增加，即:定理e为G的割边e不在G的任一圈中。证明：令e=xy，则x与y在G的同一分支中。于是，e为G的割边(G-e)=(G)+1x与y不在G-e的同一分支中G-e中无(x,y)-路G中无含e的圈。另一种证明：证明：

3、可以假设G连通。“必要性”若不然。设e在图G的某圈C中，且令e=uv.考虑P=C-e,则P是一条uv路。下面证明G-e连通。对任意x,y属于V(G-e)，由于G连通，所以存在x---y路Q.若Q不含e，则x与y在G-e里连通；若Q含有e，则可选择路：x---uPv---y,说明x与y在G-e里也连通。所以,若边e在G的某圈中，则G-e连通。但这与e是G的割边矛盾！“充分性”如果e不是G的割边，则G-e连通，于是在G-e中存在一条u---v路，显然：该路并上边e得到G中一个包含边e的圈，矛盾。推论：当且仅当连

4、通图G的每一条边均为割边时，G才是棵树证明：显然树的每一条边均为割边。反之，若图G的每一条边均为割边，则G连通无圈，因此是棵树例1求证:(1)若G的每个顶点的度数均为偶数，则G没有割边;(2)若G为k正则二部图(k≧2)，则G无割边。证明:(1)若不然，设e=uv为G的割边。则G-e的含有顶点u的那个分支中点u的度数为奇，而其余点的度数为偶数，与握手定理推论相矛盾！(2)若不然，设e=uv为G的割边。取G-e的其中一个分支G1,显然，G1中只有一个顶点的度数是k-1,其余点的度数为k。并且G1仍然为二部图。

5、假若G1的两个顶点子集包含的顶点数分别为m与n，并且包含m个顶点的顶点子集包含度为k-1的那个点，那么有：k（m-1）=kn。但是因k≧2，所以等式不能成立！定义2若SE(G)，S,使得k(GS)>k(G),而对SE(G),k(GS)=k(G),则称S为G的边割集.若{e}为边割集,则称e为割边或桥.对于连通图来说，若S是G的边集合的一个子集，若G去掉S中的边后不连通但是去掉S的任意真子集中的边后仍能保持连通，则称S为G的边割集.说明：Kn无点割集.n阶空图既无点割集，也无边割集.若G连通

6、，E为边割集，则k(GE)=2.若G连通，V为点割集，则k(GV)2.Q1abcedf(a,b,e)为割集结论1：有几个顶点（非孤立点）就可得几个割集abfcedabfcedabfced(b,d,e,f)是割集(a,d,e)是割集(a,c,e,f)是割集abcdefge1e2e3e4e5e6e7e8e9割点:{e},{f},点割集:{e},{f},{c,d}割边:e8,e9边割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}实例点割集：{v2,v4},{

7、v3},{v5}割点：{v3},{v5}边割集:{e5},{e6},{e1,e2},{e1,e3},{e1,e4},{e2,e3},{e2,e4},{e3,e4}桥:{e5},{e6}e4v1v3v4v5v6e1e2e5e6●●●v2e3●●●e4v1v3v4v5v6e1e2e5e6●●●v2e3●●●{e2,e4e5,e5}是割集吗？例2边子集：S1=｛a,c,e｝,S2=｛a,b｝,S3=｛f｝是否是下图G的边割？agedcbhfi图G解:S1不是；S2与S3是。定义4在G中，与顶点v关联的边的集合，称

8、为v的关联集，记为：S(v)。例3关联集是割集吗？为什么？答：不一定！如在下图中，关联集｛a,c,e｝是割集，但是，关联集｛d,e,f｝不是割集。agedcbhfi图G定义2连通图G的顶点数减1为图G的秩。具有k个分支的图的秩定义为n-k。记为R(G)。因此，一个具有p个顶点的连通图G,它的秩为p-1；定义3设S是连通图G(p,q)的一个边子集，如果：(1)R(G-S)=p-2;(2)对S的任一真子集S,有R(