边的独立、覆盖和支配 ■对于任意一个不含孤立点的图G:(G)+B'(G)=v(G ●你能自己证明B'(G≤v(G-a(G)吗？ (基于最大边独立集构造边覆盖集) (vI -a(G)+(v(G)-2·a(G)=v(G)-a(G) e e10 V11 ●你能自己证明a(G≥v(G)-B'(G吗？ (基于最小边覆盖集构造边独立集) 一最小边覆盖集的边导出子图的连通分支 是星 -连通分支的数量：(G)-B(G) 一从每个连通分支中取一条边 V2 2023/4/17 27
n 对于任意一个不含孤立点的图G：α’(G) + β’(G) = ν(G) l 你能自己证明β’(G) ≤ ν(G) – α’(G)吗？ （基于最大边独立集构造边覆盖集） – α’(G) + (ν(G) – 2 ⋅ α’(G)) = ν(G) – α’(G) l 你能自己证明α’(G) ≥ ν(G) – β’(G)吗？ （基于最小边覆盖集构造边独立集） – 最小边覆盖集的边导出子图的连通分支 是星 – 连通分支的数量： ν(G) – β’(G) – 从每个连通分支中取一条边 2023/4/17 27 边的独立、覆盖和支配
边的独立、覆盖和支配 ■对于任意一个图G:(G)≥y(G) ●你能自己证明吗？ (基于最大边独立集构造边支配集) V4 g e e e e12 V5 v8e16 2023/4/17 28
n 对于任意一个图G： α’(G) ≥ γ’(G) l 你能自己证明吗？ （基于最大边独立集构造边支配集） 2023/4/17 28 边的独立、覆盖和支配
边的独立、覆盖和支配 ■对于任意一个图，存在一个最小边支配集是极大边独立集 ■对于任意一个图，边支配数是最小的极大边独立集包含的边数 2023/4/17 29
n 对于任意一个图，存在一个最小边支配集是极大边独立集 n 对于任意一个图，边支配数是最小的极大边独立集包含的边数 2023/4/17 29 边的独立、覆盖和支配
边的独立、覆盖和支配 ■如何找出图中的最大边独立集？ ■如何找出图中的最小边覆盖集？ ■ 如何找出图中的最小边支配集？ 2023/4/17 30
n 如何找出图中的最大边独立集？ n 如何找出图中的最小边覆盖集？ n 如何找出图中的最小边支配集？ 2023/4/17 30 边的独立、覆盖和支配
边的独立、覆盖和支配 ■如何找出图中的最大边独立集？ ■如何找出图中的最小边覆盖集？ ■如何找出图中的最小边支配集？ 2023/4/17 31
n 如何找出图中的最大边独立集？ n 如何找出图中的最小边覆盖集？ n 如何找出图中的最小边支配集？ 2023/4/17 31 边的独立、覆盖和支配