尊敬的先生，
我正在使用代表 2 人正常形式游戏(博弈论)的特定图形结构。我知道我可以通过 Tarjans 计算 O(V+E) 中有向图的所有强连通分量，但想知道计算强连通分量的所有简单循环的复杂性是多少？并且，在给定定义强连通分量的顶点数量的情况下，此类简单循环的数量是否存在已知上限？
我正在寻找与这两个问题相关的任何文献/算法。谢谢!
最佳答案
在您的情况下，可能的简单 2k 周期数为 (n 选择 k) * (m 选择 k)。如果 n、m 和 k 不小，则会呈指数增长。
枚举周期是不可行的。我怀疑是否有可能在合理的时间内将它们计算为任意图表。即使使用动态编程技术，这也需要指数时间和空间(但指数低于没有这些技术的指数)。
关于math - 顶点=|V|的有向图中的最大循环数和边缘=|E|，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10152447/