青岛理工大学-离散数学7.2

1、1,7.2 通路、回路、图的连通性,简单通(回)路, 初级通(回)路, 复杂通(回)路 无向连通图, 连通分支 弱连通图, 单向连通图, 强连通图 点割集与割点 边割集与割边(桥),图的连通性,2,3,通路与回路,通路，回路及路的长度 简单通路，简单回路 初级通路，初级回路,4,通路与回路(续),说明: 表示方法 用顶点和边的交替序列(定义), 如=v0e1v1e2elvl 用边的序列, 如=e1e2el 简单图中, 用顶点的序列, 如=v0v1vl 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5,5,通路与回路(续),定理 在n阶图G中，若从顶点vi到vj（vivj）存在通

2、 路，则从vi到vj存在长度小于等于n1的通路.,6,在图G中，如果A到B存在一条通路，则称A到B是可达的。 1、无向图的连通性 如果无向图中，任意两点是可达的，图为连通图。否则为 不连通图。 当图是不连通时，定是由几个连通子图构成。称这样的连 通图是连通分支。,图的连通性,7,p（G） p（G）,p（G） 3,8,例7.2.1 求证：若图中只有两个奇度数顶点，则二顶点必连通。 证明 用反证法来证明。 设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。,图的

3、连通性（续）,例7.2.2 在一次国际会议中，由七人组成的小组 a, b, c, d, e, f, g中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？,9,图的连通性（续）,10,解: 作无向图G=, 其中V=v | v为参加会议的人, E=(u,v) | u,vV u与v有共同语言 uv。于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。,图的连通性（

4、续）,11,2、有向图的连通性 对于有向图，“图中任意两点都有通路相连”，这个要求很高，因为有向图虽然是连在一起的，但受到边的方向的限制，任意两点不一定有通路。以下分三种情况讨论：连通图，单向连通图，强连通图。,图的连通性（续）,12,例7.2.3 判断下图中4个图的连通性。,图的连通性（续）,13,在实际问题中, 除了考察一个图是否连通外, 往往还要研究一个图连通的程度, 作为某些系统的可靠性度量。 图的连通性在计算机网、通信网和电力网等方面有着重要的应用。,图的连通性的应用,14,割集,在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某个顶点v，就是将顶点v和与v关

5、联的所有的边均删去；删除边只需将该边删除。,15,例如前例“国际会议对话”任何一人请假，图G-v还连通，小组对话仍可继续进行，但如果f、g二人同时不在，G-f，g是非连通图，则小组中的对话无法再继续进行。,割集（续）,16,点割集,记 Gv: 从G中删除v及关联的边 GV : 从G中删除V 中所有的顶点及关联的边 Ge : 从G中删除e GE: 从G中删除E中所有边 定义 设无向图G=, V V, 若p(GV )p(G)且V V , p(GV )=p(G), 则称V 为G的点割集. 若v为点割集, 则称v为割点.,17,点割集(续),例7.2.4 v1,v4, v6是点割集, v6是割点. v

6、2,v5是点割集吗？,18,边割集,定义 设无向图G=, E E, 若p(GE )p(G)且E E , p(GE )=p(G), 则称E 为G的边割集. 若e为边割集, 则称e 为割边或桥. 例7.2.5 e1,e2，e1,e3,e5,e6，e8等是边割集， e8是桥，e7,e9,e5,e6是边割集吗？,割集（续）,几点说明： 割点或割边都是图连通的关键部位, 并不是所有的图都有割点或割边。 没有割点和割边的连通图, 需要去掉几条边或几个点, 图才会变得不连通。 Kn无点割集。 n阶零图既无点割集，也无边割集。,19,割集（续）,一个连通图G，若存在点割集和边割集，一般并不唯一，且各个点（边）

7、割集中所含的点（边）的个数也不尽相同。我们用含元素个数最少的点割集和边割集来刻画它的连通度。,20,21,下面从数量观点来描述图的连通性。 定义 设G = (V, E)是连通图, k(G) = min | V | | V是G的点割集称为G的点连通度; (G) = min | E | | E是G的边割集称为G的边连通度。 图G的点连通度是为了使G成为一个非连通图,需要删除的点的最少数目。 若图G中存在割点, k(G) = 1。 图G的边连通度是为了使G成为一个非连通图, 需要删除的边的最少数目。 若图G中存在割边, (G) = 1。,割集（续）,22,例7.2.5 下图中的两个连通图都是n=8，e=16， 其中, k（G1）=4, (G1）=4, k （G2）=1，（G2）=3。,假设n个顶点代表n个站，e条边表示铁路或者桥梁或者电话线，en-1。为了使n个站之间的连接不容易被破坏，必须构造一个具有n个顶点e条边的连通图，并使其具有最大的点连通度和边连通度。按图中G1的连接法，如果3个站被破坏，或者3条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。但按图中G2的连接法，如果v站被破坏，余下的站就不能保持连通。,23,Whitney定理 对任意的图G = (V, E), 有 k(G) (G) (