割集学习教程

研究图的连通性的意义 研究图的连通性，主要研究图的连通程度的刻画，其意义是：图论意义：图的连通程度的高低，是图结构性质的重要表征，图的许多性质都与其相关，例如：连通图中任意两点间不相交路的条数就与图的连通程度有关。第1页/共42页实际意义：图的连通程度的高低，在与之对应的通信网络中，对应于网络“可靠性程度”的高低。网络可靠性，是指网络运作的好坏程度，即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。网络可靠性，是用可靠性参数来描述的。参数主要分确定性参数与概率性参数。确定性参数主要考虑网络在最坏情况下的可靠性度量，常称为网络拓扑的“容错性度量”，通常用图论概念给出。第2页/共42页边割集简介 边割集跟回路、树等概念一样，是图论中重要概念。在应用上，它是电路网络图论的基本概念之一。所以，下面作简单介绍。4.1 割集与断集第3页/共42页(一)割边及其性质 定义1 称边e为图G的一条割边，如果在图G中删去e后，图G的连通分支数增加，即:第4页/共42页定理 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的圈。第5页/共42页 另一种证明：证明：可以假设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在G的某圈中，则G-e连通。但这与e是G的割边矛盾！第6页/共42页 “充分性”如果e不是G的割边，则G-e连通，于是在G-e中存在一条u-v 路，显然：该路并上边e得到G中一个包含边e的圈，矛盾。第7页/共42页推论：当且仅当连通图G的每一条边均为割边时，G才是棵树证明：显然树的每一条边均为割边。反之，若图G的每一条边均为割边，则G连通无圈，因此是棵树第8页/共42页 例1 求证:(1)若G的每个顶点的度数均为偶数，则G没有割边;(2)若G为k正则二部图(k2)，则G无割边。证明:(1)若不然，设e=uv 为G的割边。则G-e的含有顶点u的那个分支中点u的度数为奇，而其余点的度数为偶数，与握手定理推论相矛盾！第9页/共42页 (2)若不然，设e=uv 为G的割边。取G-e的其中一个分支G1,显然，G1中只有一个顶点的度数是k-1,其余点的度数为k。并且G1仍然为二部图。假若G1的两个顶点子集包含的顶点数分别为m与n，并且包含m个顶点的顶点子集包含度为k-1的那个点，那么有：k（m-1）=kn。但是因k2，所以等式不能成立！第10页/共42页定定义义2 若若S E(G)，S,使使得得k(G S)k(G),而而对对 SE(G),k(G S)=k(G),则则称称S为为G的的边边割割集集.若若e为边割集为边割集,则称则称e为割边或桥为割边或桥.对于连通图来说，对于连通图来说，若若S是是G的的边边集集合合的的一一个个子子集集，若若G去去掉掉S中中的的边边后后不不连连通通但但是是去去掉掉S的的任任意意真真子子集集中中的的边边后后仍仍能能保持连通，则称保持连通，则称S为为G的边割集的边割集.第11页/共42页说明：Kn无点割集.n 阶空图既无点割集，也无边割集.若G连通，E为边割集，则k(GE)=2.若G连通，V为点割集，则k(GV)2.第12页/共42页Q1abcedf(a,b,e)为割集结论1：有几个顶点（非孤立点）就可得几个割集第13页/共42页第14页/共42页abfcedabfcedabfced(b,d,e,f)是割集(a,d,e)是割集(a,c,e,f)是割集第15页/共42页abcde fge1e2e3e4e5e6e7e8e9割点:e,f,点割集:e,f,c,d 割边:e8,e9边割集:e8,e9,e1,e2,e1,e3,e6,e1,e3,e4,e7实例第16页/共42页点割集：v2,v4,v3,v5割点：v3,v5边割集:e5,e6,e1,e2,e1,e3,e1,e4,e2,e3,e2,e4,e3,e4桥:e5,e6 e4v1v3v4v5v6e1e2e5e6v2e3第17页/共42页e4v1v3v4v5v6e1e2e5e6v2e3e2,e4 e5,e5是割集吗？第18页/共42页例2 边子集：S1=a,c,e,S2=a,b,S3=f是否是下图G的边割？agedcbhfi图G第19页/共42页解:S1不是；S2与S3是。定义4 在G中，与顶点v关联的边的集合，称为v的关联集，记为：S(v)。例3 关联集是割集吗？为什么？答：不一定！如在下图中，关联集a,c,e是割集，但是，关联集d,e,f不是割集。agedcbhfi图G第20页/共42页 定义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(G-S)=p-1。称S为G的一个边割集。第21页/共42页agedcbhfiagedcbhfi第22页/共42页agedcbhfi连通图的割集将该图的顶点集合分成两部分，分成两个连通分支第23页/共42页连通图的将该图的顶点集合分成两部分的边集合未必是图的割集agedcbhfi第24页/共42页 定义5 在G中，如果V=V1V2,V1V2=,E（V1V2）是G中端点分属于V1与V2的G的边子集，称,E（V1V2）是G的一个断集。agedcbhfi图G第25页/共42页2、断集的确定 可以用在连通图G上作闭合面的方法判断确定一个割集。如果在G上作一个闭合面，使其包围G的某些顶点，于是，若把与此闭合面相交的所有边全部移去，G将被分离为两个部分，则这样边的集合便构成一个断集。第26页/共42页e4v1v3v4v5v6e1e2e5e6v2e3第27页/共42页e4v1v3v4v5v6e1e2e5e6v2e3第28页/共42页一个图若按断集S来画，形式为：S第29页/共42页定理：设T是连通图G的一颗生成树，并且e为任一树枝，则（1）连枝集中不包含G的割集（2）包含G的一个唯一的割集定理：连通图G的一个割集至少包含生成树的一个树枝第30页/共42页第31页/共42页定义：设v是G图的一个顶点，与v关联的所有边的集合，称为顶点v的关联集，记作S(v)bav2cv3v14bav2fdcev3v14S(v1)第32页/共42页定理：图G的任一断集均可表示为若干个关联集的环和。推论：图G的任一关联集都可以表示为其余各点关联集的环合思考：图G的各个顶点的关联集的关系是怎样的？线性相关还是线性无关？如何定义线性相关？第33页/共42页e4v1v3v4v5v6e1e2e5e6v2e3S(v4)S(v3)第34页/共42页e4v1v3v4v5v6e1e2e5e6v2e3S(v4)S(v3)S(v6)第35页/共42页 例4 下图G的所有的关联集。ba2fdce314S(1)=a,b,c S(2)=a,d,f S(3)=c,e,fS(4)=b,d,e第36页/共42页ba2c314a2fd3142fce314第37页/共42页第一至四章小测验1.请仔细观察下图，指出（1）该图是几阶图？最大度数和最小度数各是多少？请陈述握手定理。(2)该图是欧拉图吗？若是，请画出一条欧拉图 圈或欧拉路 （3）该图存在哈密顿圈吗？如果存在，请画出哈密顿圈。第38页/共42页2.(1)请画出下图的两颗不同的生成树；（2）写出下图的任意两个顶点的关联集；（3）写出下图的一个不是关联集的边割集，再写出一个断集，该图有割点吗？e10v1v2v3v4v5v6v7e1e2e3e4e5e6e9e7e8v8第39页/共42页5v1v2v3v4v5v6v78996778910v83.求出上面赋权图的两颗不同的最小生成树第40页/共42页 注：割集、关联集是断集，但逆不一定。断集和关联集之间的关系为：定理2 任意一个断集均是若干关联集的环和。定理3 连通图G的断集的集合作成子图空间的一个子空间，其维数为n-1。该空间称为图的断集空间。(其基为n-1个线性无关的关联集)第41页/共42页感谢您的观看！第42页/共42页