graph-theory - 当节点 h 以最小成本与所有其他节点连接时，从 1 使每个节点 2 的度数

Question

总共有 n 个节点（n 的最大值可以是 2000）。现在节点 h 已经连接到所有其他节点，并且我们得到了连接邻接矩阵中每对节点的成本。我们需要以最小成本使每个节点的度数至少为 2（最初每个节点的度数为 1，因为它最初与节点 h 连接）。

注意：
（1）节点的度数是nos。连接到该节点的边数。
(2)h 始终等于 1 。

我们应该怎么做 ？我有一个贪心算法，我们对每 2 个节点之间的成本对进行排序，并以最低成本挑选对，使所有节点都达到 2 级，但这肯定会失败。

Answer 1

我们可以忽略h并将问题视为添加边，使得每个顶点的度数至少为 1。如果顶点的数量是偶数，这只是一个完美匹配。否则，它是一个完美匹配加上一个连接到另一个顶点的顶点（给定顶点度数 2）。您可以通过简单地尝试额外顶点的所有可能性并解决n 个完美匹配问题来解决这些问题。