第十一章连通度,网络,匹配与Peti ●11.1连通度与块 ●11.2网络最大流 ●11.3图与二分图的匹配 ●114独立集,覆盖 ●115 Petri网
第十一章 连通度，网络，匹配与Petri 网 11.1 连通度与块 11.2 网络最大流 11.3 图与二分图的匹配 11.4 独立集，覆盖 11.5 Petri 网
11。1连通度与块 点连通度与边连通度 ●衡量一个图的连通程度 ●图11.1 点 ●边
11.1 连通度与块 一、点连通度与边连通度 衡量一个图的连通程度 图11.1 点 边
●1,定义11.1(点割点) 设图G的顶点子集∨,o(GV)>oG), 称V为G的一个点割。ⅣV|=付时,v中的顶 点称为割点
1，定义11.1（点割 /割点） 设图 G的顶点子集 V ’ ， (G-V ’)> (G) ， 称 V ’ 为 G的一个点割。|V ’|=1时， V ’中的顶 点称为割点
●2,定义112(点连通度/连通度) 设有图G,为产生一个不连通图或 平凡图需要从G中删去的最少顶点数称为 G的点连通度,记为k(G,简称为G的连 通度。 ●不连通图或平凡图:k(G=0; ●连通图,有割点:k(G=1; ●完全图:k(G)=n-1;
2，定义11.2（点连通度 /连通度） 设有图 G，为产生一个不连通图或 平凡图需要从 G中删去的最少顶点数称为 G 的点连通度，记为k(G)，简称为 G 的 连 通度。 不连通图或平凡图：k(G)=0 ； 连通图，有割点：k(G)=1 ； 完全图：k(G)=n-1 ；
●3,定义11.3(边连通度) 设有图G,为产生一个不连通图或 平凡图需要从G中删去的最少边数称为G 的边连通度,记为G) ●不连通图或平凡图:(G)=0 ●连通图,有一桥:4(G)=1 ●完全图:AG)=n-1;
3，定义11.3（边连通度） 设有图G，为产生一个不连通图或 平凡图需要从G中删去的最少边数称为G 的边连通度，记为(G)。 不连通图或平凡图：(G)=0； 连通图，有一桥：(G)=1； 完全图：(G)=n-1；
●4,例(点连通度和边连通度的用处) n个顶点表示n个站,e条边表示铁路 或者电话线。 为了使η个站连接得“最好”,必须 构造一个具有个顶点e条边的连通图, 使其具有最大的点连通度和边连通度
4，例（点连通度和边连通度的用处） n个顶点表示n个站，e条边表示铁路 或者电话线。 为了使n个站连接得“最好”，必须 构造一个具有n个顶点e条边的连通图， 使其具有最大的点连通度和边连通度
5,定理111(点连通度,边连通度与最小顶 点度数的关系) 对任何一个图G,k(G)≤4(G)≤o(G)。 ●证明方法:分历治之
5，定理11.1（点连通度，边连通度与最小顶 点度数的关系） 对任何一个图G，k(G)(G)(G)。 证明方法：分而治之
●证明: ●(1)证明A(G)≤8(G)。 若G没有边,则(G)=G)=0; 否则,存在顶点v,d(v)=(G)。删除v的 所有关联边,得到的图必定不连通,所 以(G)≤G)
证明： （1）证明(G)(G)。 若G没有边，则(G)=(G)=0； 否则，存在顶点v，d(v)=(G)。删除v的 所有关联边，得到的图必定不连通，所 以(G)(G)
(2)证明kG)≤2(G)。 ●若G是不连通图或平凡图,则k(G)=G)=0 若G是连通图,取断集E=刈E(记E关 联于V,中的点集为V,关联于中的点集为V”, 分三种情况分析
（ 2）证明k(G)(G) 。 若 G是不连通图或平凡图，则k(G)= (G)=0 。 若 G是连通图，取断集 ，记 E’关 联于 V 1中的点集为 V’，关联于 中的点集为 V ” ， 分三种情况分析。 1 1 E' ( ),| '| ( ) EV V E G 1 | | V
●1)VV或V"中至少有一个非空。不失一般性, 设V1V≠,则GV不连通,于是有k(G|V|s E1=2(G成立。 ●2)-=1-=但 min(VIvID=1不失一般性,设=1, 则GV为平凡图。于是有k(G)≤E1=(G成立 3V1V=1V”=a,但miV山Z)≥>1,则从V和 中各取若干与E中边关联的顶点,这些顶点构成子 集V2,且使得∨-V2≠,-V2,V2中顶点关联E 中全部边,ⅣV2E1,那么G-V2不连通。于是 k(G)s|VsE|=4(G成立
1) V 1-V’或 中至少有一个非空。不失一般性， 设 V 1-V’，则G-V’不连通，于是有k(G) |V’| |E’|= (G)成立。 2) 但 不失一般性，设 =1 ， 则G-V 1为平凡图。于是有k(G) |V 1| |E’|= (G)成立。 3) V 1-V’= -V ” = ，但min(|V 1|, )>1，则从 V 1 和 中各取若干与 E’中边关联的顶点，这些顶点构成子 集 V2，且使得 V 1-V2， -V2， V2中顶点关联 E’ 中全部边，|V2| |E’|，那么G-V2不连通。于是 k(G) |V2| |E’|= (G)成立。 1 V V " 1 1 VV VV ' ", min(| |,| |) 1, V V 1 1 1 | | V V 1 1 | | V V1 V 1