algorithm - 删除直接连接的组件后的最小元素数

Question

假设我有一个由邻接矩阵表示的无向:

[[0, 1, 0, 0],
 [1, 0, 0, 1],
 [0, 0, 0, 1],
 [0, 1, 1, 0]]

a[i][j] = 1 如果节点 i 和 j 已连接。一个操作包括从图中删除任何两个直接连接的组件。例如，在上图中，您可以删除节点 0 和 1。在任意数量的操作之后剩余的最小节点数是多少？

显然，我们可以在 O(N^2 * 2^N) 中通过暴力强制组件的每个组合来做到这一点。我在想有一个贪婪的方法可以在 O(N) 或 O(N^2) 中解决这个问题。

编辑:

如果 A[i][j] = 1，则两个节点直接相连。这不是可传递的，因此如果 (i, j) 直接连接并且 (j, k) 直接连接，则 (i, k) 不一定直接连接。

Answer 1

正如 Nico Schelter 所写，您想查找的是 maximum matching .

您可以使用 blossom algorithm为此。