《刀塔2》刀塔奥数至尊！

小学组：

中学组：

大学组：

在 Dota 2 中，地图可以抽象为一个无向连通图 G = (V, E)，其中：

●每个节点 v ∈ V 表示一个关键位置

●每条边表示两个位置之间可以直接移动

●图的最大度数为 Δ

你操控英雄“赏金猎人”，其技能“追踪”具有如下效果：

你可以选择若干个节点施放标记，每个被标记的节点可以监控它自身以及所有与它相邻的节点。

问题1：

证明：存在一个节点集合 S ⊆ V，使得任意节点 v ∈ V，都满足：

v ∈ S，或 v 与 S 中某个节点相邻。

并给出上界：

|S| ≤ (|V| / (Δ + 1)) × (1 + ln(Δ + 1))

问题2：

说明该问题等价于图的最小支配集问题，并证明：

●该问题是 NP-hard 的

●给出一个贪心算法，并说明其近似比为 O(log Δ)

问题3：

现在假设存在对抗过程：

●每一回合，敌方可以删除一个未被监控的节点

●每一回合，你可以新增一个标记节点

问：是否存在一种策略，使你无论在任何图上都能最终监控整个图？

若存在，请说明策略；若不存在，请构造反例。