边覆盖集(Edge Cover) ·边覆盖集(edge cover) ·L是G的边覆盖集：u∈V(G),3v∈V(G),(u,)∈L ·隐含要求：G中无孤立顶点，即6(G)>0 仔细观察边覆 ·极小边覆盖集(minimal edge cover)) 盖数和边独立 ·边数极少（任何一个真子集都不再是边覆盖集） ·最小边覆盖集(minimum edge cover) 数，你有什么 ·边数最少 预感？ ·边覆盖数(edge cover number) ·B(G):最小边覆盖集的势 11边覆盖集(Edge Cover) • 边覆盖集 (edge cover) • L是G的边覆盖集：∀u∈V(G), ∃v∈V(G), (u, v)∈L • 隐含要求：G中无孤立顶点，即δ(G)>0 • 极小边覆盖集 (minimal edge cover) • 边数极少（任何一个真子集都不再是边覆盖集） • 最小边覆盖集 (minimum edge cover) • 边数最少 • 边覆盖数 (edge cover number) • β’(G)：最小边覆盖集的势 11 仔细观察边覆 盖数和边独立 数，你有什么 预感？