边覆盖集(Edge Cover) ·边覆盖集(edge cover) ·L是G的边覆盖集：u∈V(G),v∈V(G),(u,v)∈L ·隐含要求：G中无孤立顶点，即6(G>0 仔细观察边覆 ·极小边覆盖集(minimal edge cover) 盖数和边独立 ·边数极少（任何一个真子集都不再是边覆盖集） ·最小边覆盖集(minimum edge cover) 数，你有什么 ·边数最少 预感？ ·边覆盖数(edge cover number) ·'(G:最小边覆盖集的势 11
边覆盖集(Edge Cover) • 边覆盖集(edge cover) • L是G的边覆盖集：∀u∈V(G), ∃v∈V(G), (u, v)∈L • 隐含要求：G中无孤立顶点，即δ(G)>0 • 极小边覆盖集(minimal edge cover) • 边数极少（任何一个真子集都不再是边覆盖集） • 最小边覆盖集(minimum edge cover) • 边数最少 • 边覆盖数(edge cover number) • β’(G)：最小边覆盖集的势 11 仔细观察边覆 盖数和边独立 数，你有什么 预感？
边覆盖集与边独立集 Theorem8.7若图G(n个节点)不包含孤立点（即6(G)>o),则 a'(G)+β'(G)=n。 如果有一条边覆盖两个这样的点， 证明概要： 1,β'(G)<=a(G+n-2a(G)=n-a(G: 这条边可以放入“最大边独立集” >最大边独立集覆盖2a'(G)个点；其余点可由n-2a(G)条边覆盖 >{ 因此：a(G+β'G<=n 2,X是某个最小边覆盖集，(=|X='(G),观察由x导出的图F >各个连通分量都是星型结构：没有长度超过2的通路 >F是一个森林 02视 有n个节点、k条边的森林，由n-k棵树构成 >因此，F由-棵星树构成，从每棵树中取一条边，构成一个边独立集 因此，a(G)>=n-( >a(G)+β'(G)>=n-什t=n
边覆盖集与边独立集 • Theorem 8.7 若图G (n 个节点) 不包含孤立点(即δ(G)>0)，则 α’(G)+β’(G)=n。 证明概要： 1，β’(G)<=α’(G)+(n-2α’(G))=n-α’(G): ➢ 最大边独立集覆盖2α’(G)个点；其余点可由n-2α’(G)条边覆盖 ➢ 因此：α’(G)+β’(G)<=n 2，X是某个最小边覆盖集，l =|X|=β’(G),观察由X导出的图F ➢ 各个连通分量都是星型结构：没有长度超过2的通路 ➢ F是一个森林 ➢ 因此，F由n-l 棵星树构成，从每棵树中取一条边，构成一个边独立集 ➢ 因此， α’(G)>= n-l ➢ α’(G)+β’(G)>=n-l+l = n 如果有一条边覆盖两个这样的点， 这条边可以放入“最大边独立集” 有n个节点、k条边的森林，由n-k棵树构成