3

这里我有一个有向图G。我需要确定是否存在一组顶点不相交的循环，以便每个顶点都属于一个循环。

我不确定这是否可以在多项式时间内完成，或者它是否是 NP-Complete？谁能至少指出我正确的方向？

4

1 回答 1

5

将每个顶点拆分为“入”顶点和“出”顶点。然后一个顶点不相交的循环覆盖对应于该图上的完美​​匹配。您可以尽快找到完美匹配的答案（即多项式时间）

于 2014-11-05T04:20:01.083 回答