查找图的线覆盖数

问题陈述

下图的线覆盖数是多少？

解决方案

顶点数量 = |V| = n = 7

线覆盖数 = (α₁) ≥ ⌈ n / 2 ⌉ = 3

α₁ ≥ 3

使用 3 条边，我们可以覆盖所有顶点。

因此，线覆盖数为 3。

马赫什·帕拉哈

更新于： 2019-08-23

440 次浏览

开启你的职业生涯

完成课程，获得认证

开始吧