边覆盖集与边独立集 ·Theorem8.7若图G(n个节点)不包含孤立点（即6(G)>o),则 a'(G)+β'(G)=n。 证明： 1.基于最大边独立集M,构造势为n-IM=n-a(G)的边 覆盖集→B'(G)≤n-a(G) 对每个未被M饱和的顶点，向M中增加它关联的一条边→构成势 为n-|M的边覆盖集 2. 基于最小边覆盖集L,构造势为n-L=n-B'(G)的边独 立集→a(G)≥n-B'(G) L是最小边覆盖集→GL的连通分支是星→G[L]有n-L个连通 分支→每个连通分支取一条边构成势为n一的边独立集 →a'(G)+β'(G)=n (不可能有长度大于等于3的通路或回路， 否则去掉这条边可以得到更小的边覆盖集) 12边覆盖集与边独立集 • Theorem 8.7 若图G (n 个节点) 不包含孤立点(即δ(G)>0)，则 α’(G)+β’(G)=n。 12 （不可能有长度大于等于3的通路或回路， 否则去掉这条边可以得到更小的边覆盖集）