中国学孜术大 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-点割集