Entfernen von Zyklen aus dem Diagramm

Question

Angenommen, ich habe einen zusammenhängenden ungerichteten Graphen$G=(V,E)$, möchte ich eine kleinste Teilmenge von finden$E$zu entfernen, damit alle Zyklen entfernt werden.

Von der Wikipedia-Seite zum Schaltungsrang funktioniert, wenn ich das richtig verstehe, der folgende Ansatz: Finden Sie einen beliebigen Zyklus in$G$, entfernen Sie alle Kanten des Zyklus und wiederholen Sie den Vorgang. Gibt es eine einfache Möglichkeit zu beweisen, dass dies funktioniert?

Answer 1

Definieren Sie den Schaltungsrang eines endlichen Graphen$G=(V,E)$wie$r(G)=|E|-|V|+c$wo$c$ist die Anzahl der Zusammenhangskomponenten von$G$. Beachten Sie, dass ein verbundener Graph$G$hat$r(G)\geq 0$und$r(G)=0$iff$G$ist ein Baum. Außerdem, wenn die angeschlossenen Komponenten von$G$sind$G_1,\dots,G_n$, dann$r(G)=\sum_{i=1}^n r(G_i)$. Es folgt dem$r(G)=0$iff$G$ist ein Wald, dh$G$hat keine Zyklen.

Betrachten Sie nun, was passiert, wenn Sie eine Kante aus einem Graphen entfernen$G$. Wenn diese Kante Teil eines Zyklus ist, nehmen Sie ab$|E|$durch$1$aber nicht ändern$|V|$oder$c$, Also$r(G)$sinkt um$1$. Wenn die Kante nicht Teil eines Zyklus ist, erhöhen Sie zusätzlich$c$durch$1$(da Sie eine Komponente in zwei Teile teilen), also$r(G)$ändert sich nicht.

Also, wenn Sie abnehmen möchten$r(G)$bis zu$0$Indem Sie so wenig Kanten wie möglich entfernen, sollten Sie immer Kanten entfernen, die Teil eines Zyklus sind, und es dauert$r(G)$Schritte.