边覆盖集与边独立集 Theorem8.7若图G(n个节点)不包含孤立点（即6(G)>0),则 a'(G)+B'(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-l >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棵树构成