复旦大学计算机科学与工程系 吴永辉 离散数学 连通度,网络,匹配

第八章 连通度，网络，匹配与Petri网8.1 8.2 8.3 8.4 8.5 连通度与块 网络最大流 图与二分图的匹配 独立集，覆盖 Petri网

8.1 连通度与块一、点连通度与边连通度

衡量一个图的连通程度 图8.1 点 边

1,定义8.1(点割/割点) 设图G的顶点子集V’, (G-V’)> (G), 称V’为G的一个点割。|V’|=1时，V’中的顶 点称为割点。

2,定义8.2(点连通度/连通度) 设有图G,为产生一个不连通图或 平凡图需要从G中删去的最少顶点数称为 G的点连通度，记为k(G),简称为G的连 通度。 不连通图或平凡图：k(G)=0; 连通图，有割点：k(G)=1; 完全图：k(G)=n-1;

3,定义8.3(边连通度) 设有图G,为产生一个不连通图或 平凡图需要从G中删去的最少边数称为G 的边连通度，记为 (G)。 不连通图或平凡图： (G)=0; 连通图，有一桥： (G)=1; 完全图： (G)=n-1;

4,例8.1/图8.2(点连通度和边连通度的 用处) n个顶点表示n个站，e条边表示铁路 或者电话线。 为了使n个站连接得“最好”,必须 构造一个具有n个顶点e条边的连通图， 使其具有最大的点连通度和边连通度。

5,定理8.1(点连通度，边连通度与最小顶点 度数的关系) 对任何一个图G,k(G) (G) (G)。

证明方法：分而治之。

证明： (1)证明 (G) (G)。 若G没有边，则 (G)= (G)=0; 否则，存在顶点v,d(v)= (G)。删除v的 所有关联边，得到的图必定不连通，所 以 (G) (G)。

(2)证明k(G) (G)。 若G是不连通图或平凡图，则k(G)= (G)=0。 若G是连通图，取断集 ，记E’关 E ' E ( 1 V1 ),| E ' | (G) 联于V1V中的点集为V’,关联于 中的点集为V”, |V | 分三种情况分析。1

1) V1-V’或 V1 V "中至少有一个非空。不失一般性， 设V1-V’ ,则G-V’不连通，于是有k(G) |V’| |E’|= (G)成立。 2) V1 V ' V1 V " ,但 min(| V |,| V |) 1,不失一般性，设 | V1 | =1, 则G-V1为平凡图。于是有k(G) |V1| |E’|= (G)成立。 3)V1-V’= -V”= ,但min(|V1|, )>1,则从V1和 | V1 | V 中各取若干与E’中边关联的顶点，这些顶点构成子V 集V2,且使得V1-V2 , -V2 , V2中顶点关联E’ V 中全部边，|V2| |E’|,那么G-V2不连通。于是 k(G) |V2| |E’|= (G)成立。1 11

1

1

6,例8.2 证明：设G是有n个顶点的简单图，且 n-2,则k(G)= 。

证明方法：分而治之。证明： 当 =n-1时G=Kn,所以k(G)= 。 当 =n-2时，若顶点v1, v2不相邻，则对任意第3 个顶点v3, G中有边{v1,v2}, {v1,v3}。此时对任意n-3 个顶点构成的子集V’,均有G-V’连通(在G中删去 任意n-3个顶点依然连通)。所以k(G) n-2= 。由定 理8.1, (G) ,即得k(G)= 。

6,定义8.4( k-连通的) 若图G的k(G) k,称G为k-连通的。

7,定义8.5( k-边连通的) 若图G的 (G) k,称G为k-边连通的。

二、割点与块1,定理8.2 设v是连通图G的一个顶点，下列论断是 等价的： (1) v是G的一个割点。 (2)对于顶点v,存在两个不同的顶点u和 w,使顶点v在每一条从u到w的路上。 (3)存在V-{v}的一个分成U和W的划分， 使对任意两顶点u U和w W,顶点v在 每一条从u到w的路上。

证明方法： (1) (3) (3) (2) (2) (1) /* 参考定理7.1证明 */

证明：(1) (3)/* v是G的一个割点 存在V-{v}的一个分成U和W的 划分，使对任意两顶点u U和w W,顶点v在每一 条从u到w的路上*/

因为v是G的一个割点，G-{v}是不 连通的，它至少有两条分支。设U是由 其中一个分支中的顶点，W由其余顶点 组成，形成V-{v}的一个划分。于是任意 两顶点u U和w W在G-{v}的不同分支 中。因此G中每一条从u到w的路中包含 顶点v。