gpt4 book ai didi

vertex - 一组顶点不相交的循环,以便每个顶点都属于一个循环

转载 作者:行者123 更新时间:2023-12-04 00:37:21 26 4
gpt4 key购买 nike

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

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

最佳答案

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

关于vertex - 一组顶点不相交的循环,以便每个顶点都属于一个循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23121799/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com