v1 v v2 5 v2 v3 v3 边覆盖与完美匹配的力: 1)M,L都要求每个端点关联M,L中的边 2)但M要求边不相交而L无此要求 G有边覆盖的充要条件是8(G)>0。 当G中有孤立点时,图G不存在边覆盖2.边覆盖和边独立集 定义 8.17：若E的一个子集L使得G的每 一个顶点至少与L中一条边关联, 称L是G 的一个 边覆盖 。 若 G 中不含有满足 |L'|<|L|的边覆盖L'，则称L是G的最小边 覆盖。它的边数称为G的边覆盖数，记 为1 (G)。 边覆盖与完美匹配的区别: 1)M,L都要求每个端点关联M,L中的边 2)但M要求边不相交,而L无此要求 G有边覆盖的充要条件是(G)>0。 当G中有孤立点时,图G不存在边覆盖