Effizienter Algorithmus, der entscheidet, ob eine Kante zu einem Zyklus gehört

Question

Ich versuche einen effizienten Algorithmus zu strukturieren, erhält ungerichteten Graphen und Kante e (u, v) und entscheidet, ob die Kante zu irgendeinem Zyklus im Graphen gehört, aber nicht alle Zyklen! Mein Ansatz besteht darin, die Kante (u, v) aus dem Diagramm herauszunehmen und BFS auszuführen, um zu sehen, ob v noch von u erreichbar ist. Wenn ja, dann hat der ursprüngliche Graph einen Zyklus, der e enthält, sonst nicht. Aber ich bin nicht so sicher, wie man den Algorithmus zwickt, der entscheidet, wenn die Kante nicht zu allen Zyklen des Diagramms gehört.

Answer 1

Ein ungerichteter Graph kann nur dann eine Kante enthalten, die zu allen Zyklengraphen gehört, wenn dieser Graph einen einzelnen Zyklus hat.

Schauen wir uns ein Beispiel an. Kante (2,3) gehört zu zwei Zyklen, aber Sie können immer einen dritten Zyklus finden, zu dem eine solche Kante nicht gehört.

Nachdem Sie überprüft haben, dass der Rand bis zu einem gewissen Zyklus gehört, können Sie überprüfen, ob dies den einzigen Zyklus im Graphen ist durch diese Kante zu entfernen und prüfen, ob die reduzierte Graph überhaupt keine Zyklen hat. Danke an @nomanpouigt für das Aufzeigen.