边的独立、覆盖和支配 ■边支配集 ·补集中的每条边都与其中至少一条边相邻 ■极小边支配集 ·边支配集，且任何边支配集都不是其真子集 e14 e14 9 V10 e15 V2 e10 2023/4/17 17
n 边支配集 l 补集中的每条边都与其中至少一条边相邻 n 极小边支配集 l 边支配集，且任何边支配集都不是其真子集 2023/4/17 17 边的独立、覆盖和支配
边的独立、覆盖和支配 ■边支配集 ·补集中的每条边都与其中至少一条边相邻 ■极小边支配集 ●边支配集，且任何边支配集都不是其真子集 ■最小边支配集 ·边的数量最少的边支配集 e14 V e14 e V10 e15 e12 e8 e12 Vs e10 e10 2023/4/17 18
n 边支配集 l 补集中的每条边都与其中至少一条边相邻 n 极小边支配集 l 边支配集，且任何边支配集都不是其真子集 n 最小边支配集 l 边的数量最少的边支配集 2023/4/17 18 边的独立、覆盖和支配
边的独立、覆盖和支配 ■边支配集 ·补集中的每条边都与其中至少一条边相邻 ■极小边支配集 ●边支配集，且任何边支配集都不是其真子集 ■最小边支配集 ●边的数量最少的边支配集 ■边支配数 ●最小边支配集的大小，记作y(G e14 e14 9 V10 e12 e12 e10 2023/4/17
n 边支配集 l 补集中的每条边都与其中至少一条边相邻 n 极小边支配集 l 边支配集，且任何边支配集都不是其真子集 n 最小边支配集 l 边的数量最少的边支配集 n 边支配数 l 最小边支配集的大小，记作γ’(G) 2023/4/17 19 边的独立、覆盖和支配
边的独立、覆盖和支配 ■每个图都有边独立集、边覆盖集、边支配集吗？ 2023/4/17 20
n 每个图都有边独立集、边覆盖集、边支配集吗？ 2023/4/17 20 边的独立、覆盖和支配
边的独立、覆盖和支配 ■每个图都有边独立集、边覆盖集、边支配集吗？ ■阶为的图的边独立数的上界是多少？边覆盖数的下界是多少？ 边支配数的下界是多少？ 2023/4/17 21
n 每个图都有边独立集、边覆盖集、边支配集吗？ n 阶为n的图的边独立数的上界是多少？边覆盖数的下界是多少？ 边支配数的下界是多少？ 2023/4/17 21 边的独立、覆盖和支配