边的独立、覆盖和支配 ■每个图都有边独立集、边覆盖集、边支配集吗？ ■ 阶为n的图的边独立数的上界是多少？边覆盖数的下界是多少？ 边支配数的下界是多少？ ■完全图K的边独立数、边覆盖数、边支配数分别是多少？ V5 V2 2023/4/17
n 每个图都有边独立集、边覆盖集、边支配集吗？ n 阶为n的图的边独立数的上界是多少？边覆盖数的下界是多少？ 边支配数的下界是多少？ n 完全图Kn的边独立数、边覆盖数、边支配数分别是多少？ 2023/4/17 22 边的独立、覆盖和支配 v1 v5 v4 v2 v3
边的独立、覆盖和支配 ■ 每个图都有边独立集、边覆盖集、边支配集吗？ ■ 阶为n的图的边独立数的上界是多少？边覆盖数的下界是多少？ 边支配数的下界是多少？ ■完全图K的边独立数、边覆盖数、边支配数分别是多少？ ■边独立集、极小边覆盖集、极小边支配集的边导出子图的每个 连通分支分别有什么特征？ 随堂小测 2023/4/17 23
n 每个图都有边独立集、边覆盖集、边支配集吗？ n 阶为n的图的边独立数的上界是多少？边覆盖数的下界是多少？ 边支配数的下界是多少？ n 完全图Kn的边独立数、边覆盖数、边支配数分别是多少？ n 边独立集、极小边覆盖集、极小边支配集的边导出子图的每个 连通分支分别有什么特征？ 2023/4/17 23 边的独立、覆盖和支配
边的独立、覆盖和支配 ■对于任意一个不含孤立点的图G:a(G)≤B'(G ●你能自己证明吗？ (基于最大边独立集分析边覆盖数) V7 e e V5 V8 2023/4/17 24
n 对于任意一个不含孤立点的图G：α’(G) ≤ β’(G) l 你能自己证明吗？ （基于最大边独立集分析边覆盖数） 2023/4/17 24 边的独立、覆盖和支配
边的独立、覆盖和支配 ■对于任意一个不含孤立点的图G:α(G)+B(G)=v(G ●你能自己证明B'(G≤v(G-a(G)吗？ ，e4 (基于最大边独立集构造边覆盖集) ●你能自己证明a(G)≥(G)-B'(G吗？ (基于最小边覆盖集构造边独立集) e a 2023/4/17 25
n 对于任意一个不含孤立点的图G：α’(G) + β’(G) = ν(G) l 你能自己证明β’(G) ≤ ν(G) – α’(G)吗？ （基于最大边独立集构造边覆盖集） l 你能自己证明α’(G) ≥ ν(G) – β’(G)吗？ （基于最小边覆盖集构造边独立集） 2023/4/17 25 边的独立、覆盖和支配
边的独立、覆盖和支配 ■对于任意一个不含孤立点的图G:α(G)+B'(G)=v(G) ●你能自己证明B(G)≤WG)-a(G)吗？ ..e9 (基于最大边独立集构造边覆盖集) -a(G)+(G)-2·a(G)=(G-a(G) e12 ●你能自己证明α(G≥v(G-B'(G)吗？ 14 (基于最小边覆盖集构造边独立集) V V6 eis e2 V5 2023/4/17 26
n 对于任意一个不含孤立点的图G：α’(G) + β’(G) = ν(G) l 你能自己证明β’(G) ≤ ν(G) – α’(G)吗？ （基于最大边独立集构造边覆盖集） – α’(G) + (ν(G) – 2 ⋅ α’(G)) = ν(G) – α’(G) l 你能自己证明α’(G) ≥ ν(G) – β’(G)吗？ （基于最小边覆盖集构造边独立集） 2023/4/17 26 边的独立、覆盖和支配