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)or中解决这个问题O(N^2)。

编辑：

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

标签： algorithm

Answer 1

正如 Nico Schelter 所写，您要找到的是最大匹配。

您可以为此使用开花算法。