Ich habe ein gerichtetes Diagramm und mein Problem ist, alle aufzuzählenminimal (Zyklen, die nicht als Vereinigung anderer Zyklen konstruiert werden können) gerichtete Zyklen dieses Graphen. Dies unterscheidet sich von dem, was der Tarjan-Algorithmus ausgibt. Zum Beispiel für den gerichteten Graphen beiDiese Wikipedia-SeiteIch möchte c -> d und d -> h als zwei getrennte gerichtete Zyklen erhalten.

Ich weiß nicht, ob dieses Problem polynomisch ist oder nicht. Ich habe einen Artikel "Aufzählung minimaler Dicuts und stark verbundener Teilgraphen" gelesen, der den Schluss zu ziehen scheint, dass dieses Problem ein inkrementelles Polynom ist (ich weiß nicht, was es bedeutet), kann aber keinen Algorithmus für diesen Artikel extrahieren. Ich bin mir auch nicht sicher, ob eine minimale, stark verbundene Komponente einem minimalen Zyklus entspricht, wie ich ihn definiere.

Kennt jemand die Antwort auf dieses Problem?

Danke im Voraus!!!