中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）图论补充内容

中国学孜术大 Unive rsity of Science and Technology of China 图论补充内容

University of Science and Technology of China 图论补充内容

图的连通性 ■网络流 ■网络编码 ■图着色 ■超图

2 ◼ 图的连通性 ◼ 网络流 ◼ 网络编码 ◼ 图着色 ◼ 超图

图的连通性 ■之前介绍过割点、割边、连通图的概念; ■这里再补充一些概念和理论。 ■在连通图中,连通的程度也是有高有低; ■定义一种参数来度量连通图连通程度的高低

3 图的连通性 ◼ 之前介绍过割点、割边、连通图的概念； ◼ 这里再补充一些概念和理论。 ◼ 在连通图中，连通的程度也是有高有低； ◼ 定义一种参数来度量连通图连通程度的高低

割点 口定义:设v∈V(G),如果w(G-v)>w(G),则称v为G的 一个割点 MG表示图G的连通分支数 去掉V后,连通 分支增加了

4 ◼ 割点  定义：设 ，如果 ，则称v为G的 一个割点。 ◼ w(G)表示图G的连通分支数。 v V (G) w(G − v)  w(G) u v 去掉v后，连通 分支增加了

■点割集(顶点割集) 口定义: 对图G,若VG的子集V使得v(G-)>w(G),则称V为图G 的一个点割集; 含有k个顶点的点割集称为k点割集; 若Ⅴ是图G的一个点割集,而Ⅴ减少任意一个点都不再是G的 点割集,则称V是G的一个极小点割集; G中含点数最少的点割集称为G的最小点割集。 口说明 割点是1一顶点割集; 全图没有点割集 {u,是2点割集

5 ◼ 点割集（顶点割集）  定义： ◼ 对图G，若V(G)的子集V’使得 ，则称V’为图G 的一个点割集； ◼ 含有k个顶点的点割集称为k-点割集； ◼ 若V’是图G的一个点割集，而V’减少任意一个点都不再是G的 点割集，则称V’是G的一个极小点割集； ◼ G中含点数最少的点割集称为G的最小点割集。  说明 ◼ 割点是1－顶点割集； ◼ 完全图没有点割集。 w(G −V )  w(G) u v {u,v}是2-点割集

■连通度 口定义:连通度为K(G)=mnV‖V是G的顶点割集} ■完全图的连通度定义为K(Kn)=n-1,空图的连通度定义为0; 使得|V"F(G)的顶点割集V就是G的最小点割集; 若k(G)≥k,则称G为k连通的; ■若G不连通,则κ(G)=0 若G是平凡图,则(G)=0; 所有非平凡连通图都是1-连通的

6 ◼ 连通度  定义：连通度为 是G的顶点割集} ◼ 完全图的连通度定义为 ，空图的连通度定义为0； ◼ 使得 的顶点割集V’就是G的最小点割集； ◼ 若 ，则称G为k连通的； ◼ 若G不连通，则 ； ◼ 若G是平凡图，则 ； ◼ 所有非平凡连通图都是1-连通的。  (G) = min{| V  ||V  ( ) 1  K n n = − |V  |= (G)  (G)  k  (G) = 0  (G) = 0

■割边 口定义:设e∈E(G),如果w(G-e)>w(G),则称e为G的 条割边。 边e是G的割边当且仅当e不在G的任何回路中 一个连通图是树当且仅当它的每条边都是割边

7 ◼ 割边  定义：设 ，如果 ，则称e为G的一 条割边。 e  E(G) w(G − e)  w(G) • 边e是G的割边当且仅当e不在G的任何回路中； • 一个连通图是树当且仅当它的每条边都是割边。 u v

■边割集 口定义:对图G,若E(G的子集E使得W(G-E)>w(G), 则称E为图G的一个边割集。含有k条边的边割集称为 k边割集。 对非平凡图G,若E是一个边割集,则G\E不连通; 条割边构成一个1一边割集; 设S∈V(G),S'cV(G),S,S'≠p,记号[S,S]表示一端在S中 另一端在S中的所有边的集合。对图G的每个边割集,必存在 非空的ScV(G),使得[SS]是G的一个边割集,其中S=\S。 若E是图G的一个边割集,而E减少任意 一条边都不再是G的边割集,则称E是G 的一个极小边割集; ·G中含边数最少的边割集称为G的最小边 割集

8 ◼ 边割集  定义：对图G，若E(G)的子集E’使得 ， 则称E’为图G的一个边割集。含有k条边的边割集称为 k-边割集。 ◼ 对非平凡图G，若E’是一个边割集，则 不连通； ◼ 一条割边构成一个1－边割集； ◼ 设 ， ， ，记号[S,S’] 表示一端在S中 另一端在S’中的所有边的集合。对图G的每个边割集，必存在 非空的 ，使得 是G的一个边割集，其中 。 w(G − E)  w(G) G \ E [S, S ] S = V \ S S  V (G) S  V (G) S, S   • 若E’是图G的一个边割集，而E’减少任意 一条边都不再是G的边割集，则称E’是G 的一个极小边割集； • G中含边数最少的边割集称为G的最小边 割集。 S  V (G)

■边连通度: 口定义:K(G)=min{[S,S]‖ScVG)2S≠} ■完全图的边连通度定义为(K,)=v-1; 空图的边连通度定义为0; 对平凡图或不连通图G,K'(G)=0; ■若图G是含有割边的连通图,则K'(G)=1; 若K(G)≥k,则称G为k一边连通的; 所有非平凡连通图都是1一边连通的; 使得|E"Fκ'(G)的边割集E就是G的最小边割集。 口定理:κ(G)≤x'(G)≤δ(G) 图G的结点中最小的度 点连通度 边连通度

9 ◼ 边连通度：  定义： ◼ 完全图的边连通度定义为 ； ◼ 空图的边连通度定义为0； ◼ 对平凡图或不连通图G， ； ◼ 若图G是含有割边的连通图，则 ； ◼ 若 ，则称G为k－边连通的； ◼ 所有非平凡连通图都是1－边连通的； ◼ 使得 的边割集E’就是G的最小边割集。  定理：   ( ) min{|[ , ]|| ( ), } G S S S V G S =    (K ) = −1  (G) = 0( ) 1 G = ( ) G k  | E |= (G)  (G)  (G)   (G) 图G的结点中最小的度 点连通度 边连通度

■可靠通信网络的设计 口问题描述: 要设计一个有线通讯网,使得敌人炸坏几通讯站后,其余的通 讯站仍然可彼此通话; 显然,有两个要求是必要的:一是不怕被敌人炸坏站的数目要 多,一是整个造价要小。 口可靠网络设计问题:给定赋权图G和正整数m,求G的 具有最小权的m连通生成子图; 当m=1时,就是求最小生成树问题 ■当m>1时,问题尚未解决; 当G=Kn且每边权皆为1时,问题成为:求K中边数最少的m连 通生成子图。这一问题于1962年由 Harary解决。 10

10 ◼ 可靠通信网络的设计  问题描述： ◼ 要设计一个有线通讯网，使得敌人炸坏几通讯站后，其余的通 讯站仍然可彼此通话； ◼ 显然，有两个要求是必要的：一是不怕被敌人炸坏站的数目要 多，一是整个造价要小。  可靠网络设计问题：给定赋权图G和正整数m，求G的 具有最小权的m连通生成子图； ◼ 当m=1时，就是求最小生成树问题； ◼ 当m>1时，问题尚未解决； ◼ 当G=Kn且每边权皆为1时，问题成为：求Kn中边数最少的m-连 通生成子图。这一问题于1962年由Harary解决