So finden Sie zwei disjunkte Spannbäume eines ungerichteten Graphen - Algorithmus, Graphentheorie

Gibt es einen anwendbaren Ansatz, um zwei disjunkte Spanning-Bäume eines ungerichteten Graphen zu finden oder um zu überprüfen, ob ein bestimmter Graph zwei disjunkte Spanning-Bäume hat

Antworten:

2 für die Antwort № 1

Nicht sicher, dass es in der anwendbaren Seite viel hilft, aber Tutte [1961a] und Nash-Williams [1961] charakterisierten unabhängig Graphen mit k paarweise kanten-disjunkten Spannbäumen:

Ein Graph G hat k paarweise kanten-disjunkte Spannbäume wenn Für jede Partition der Ecken von G in r Mengen gibt es mindestens k (r-1) Kanten von G, deren Endpunkte sich in verschiedenen Sätzen der Partition befinden.

Verwenden Sie k = 2 und es kann Ihnen einen Anhaltspunkt für Ihre Bedürfnisse geben.

---

2 für die Antwort № 2

Dies ist ein Beispiel für die Matroid-Vereinigung. Betrachten Sie die grafische Matroid, wo die Basis durch die Spannbäume gegeben sind. Jetzt ist die Vereinigung dieses Matroiden mit sich selbst wieder ein Matroid. Ihre Frage betrifft die Größe der Basis dieses Matroids. (Ob es eine Basis der Größe $ 2 (| V | -1) $ gibt.

Der kanonische Algorithmus dafür ist MatroidPartitionierungsalgorithmus. Es gibt einen Algorithmus, der Folgendes tut: Er verwaltet eine Menge von Kanten mit einer Aufteilung in zwei Gesamtstrukturen. Bei jedem Schritt, der eine neue Kante $ e $ erhält, entscheidet er, ob es eine Umordnung der aktuellen Partition in eine neue Partition gibt, so dass die neue Kante der Menge hinzugefügt werden kann und die Partition unabhängig bleibt. Und wenn nicht, wird es irgendwie ein Zertifikat liefern, das es nicht kann.

Für Details schauen Sie sich einen Kurs in Comb an. Optimierung oder das Buch von Schriver.

---

1 für die Antwort № 3

Gemäß Eine Anmerkung zum Auffinden minimaler kosten-separater Spanning Treeskann dies gelöst werden OK²n²) woher k ist die Anzahl der disjunkten Spannbäume und n ist die Anzahl der Ecken.

Leider sind alle außer der ersten Seite des Artikels hinter einer Paywall.

---

0 für die Antwort № 4

Unter der Annahme, dass der Wunsch darin besteht, überspannende Bäume mit disjunkten Kantensätzen zu finden, was ist mit:

1. Gegeben ein Graph G bestimmt die minimaler aufspannender Baum A von G.
2. Definieren von B = G - A durch Löschen aller Kanten von G, die ebenfalls in A liegen.
3. Überprüfen, ob B verbunden ist.

Die Art eines minimalen Spannbaumsmacht mich intuitiv glauben, dass die Wahl eines der beiden sich überspannenden Bäume Ihnen maximale Freiheit bei der Konstruktion des anderen gibt (was sich hoffentlich als Rand-Disjunktiv herausstellt).

Was denkt ihr?

bearbeiten

Der obige Algorithmus macht keinen Sinn als a spannender Baum ist ein Baum und muss daher azyklisch sein. Aber es gibt keine Garantie, dass B = G - A acyclisch ist.

Diese Beobachtungen (thx @ Tormer) führten mich jedoch zu einer anderen Idee:

1. Gegeben ein Graph G bestimmt den minimalen Spannbaum A von G.
2. Definiere B = (V [G], E [G] E [A]) wobei V [G] die Ecken von G beschreibt und E [G] die Kanten von G (A bzw.) beschreibt.
3. Bestimmen Sie, ob B einen Spannbaum hat.

Es könnte sehr gut der obige Algorithmus seinscheitert, obwohl G tatsächlich zwei disjunktive Spanning-Bäume hat - nur keiner von ihnen ist G's minimaler Spannbaum. Ich kann das (jetzt) ​​nicht beurteilen, also frage ich nach Ihrer Meinung, wenn es klug ist, immer zu wählen der minimale Spannbaum als einer der beiden.

---