第十一章连通度,网络,匹配与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；