algorithm - NP-Complete 和图上的一些决策问题？

Question

我们知道 NP-Complete 和 NP-Hard，以及 NP 类。我想总结一些关于以下问题的技巧，这些技巧取自麻省理工学院 2008 年中期考试。

以下哪个连通无向加权图 G 问题的决策版本是 NP 完全的？

a) finding maximal matching.

b) finding maximum Hamiltonian cycle

c) finding maximum Eulelrian cycle

d) finding maximum cut

如何将这些问题以简单的方式对我进行归类？即 NP 或 NP-Complete 或 NP-Hard。

Answer 1

有用于计算最大匹配的多时间算法(例如，贪婪；Edmonds 的 Blossom 算法计算多时间的最大匹配)和欧拉循环。决策版本一般属于 NP(实际上是 P)。

哈密尔顿循环和最大割是众所周知的 NP 难问题。决策版本在 NP 中，因此是 NP 完全的。