无向非加权图中的最大顶点对数

Question

给定具有任何类型连通性的无向非加权图，即它可以包含 1 到多个组件，有或没有单个节点，每个节点可以有 0 到多个连接，允许循环（但没有从节点到循环本身）。

假设每个顶点只能使用一次，我需要找到最大数量的顶点对，例如。如果图有节点 1、2、3 并且节点 3 连接到节点 1 和 2，答案是一个（1-3 或 2-3）。

我正在考虑以下方法：

1. 删除所有单个节点。
2. 找到连接边数最少的节点和边数最多的节点的边（如果有多个 - 取其中任何一个），计算并从图中删除这对节点。
3. 当图形具有连接节点时重复步骤 2。

我的问题是：

1. 它是否提供了任何情况下的最大对数？我是 担心一些极端情况，比如与某些事物相关的周期 单个或多个路径等

2. 有没有更快更正确的算法？

   我可以使用 java 或 python，但伪代码或算法描述完全没问题。

Answer 1

即使在无环图的情况下，您的方法也不能保证提供最大数量的顶点对。例如，在下图中，您的方法将到达 select 边 (B,C)。在那个不幸的选择之后，没有更多的顶点对可供选择，因此您最终会得到大小为 1 的解决方案。显然，最佳解决方案包含两个顶点对，因此您的方法不是最佳的。

您要解决的问题是最大匹配问题（不要与 Maximal Matching Problem 混淆，后者很容易解决）：

Find the largest subset of edges S such that no vertex is incident to more than one edge in S.

The Blossom Algorithm 解决了 O(EV^2) 中的这个问题。

该算法的工作方式并不简单，它引入了重要的概念（如收缩匹配、森林扩展和开花）来建立最佳匹配。如果您只是想在不完全理解其复杂性的情况下使用该算法，您可以在线找到它的现成的实现（例如 this Python implementation）。