2

我找到了一些算法来找到一个最小的顶点覆盖，比如使用二叉搜索树，但我读到使用三叉树更好。但我找不到任何关于它的信息或想出一个算法。

有人知道怎么做吗？

4

1 回答 1

2

给定一个图，选择任意边 uv 作为枢轴。三元搜索树的三个分支是 (1) 我们取 u 但不取 v (2) 我们取 v 但不取 u (3) 我们取 u 和 v。在情况 (1) 中我们被迫取 v邻居，在情况（2）中，我们被迫带走你的邻居。要构造子问题，请删除所采用的顶点及其入射边。

于 2020-11-01T18:52:20.707 回答