Haben zwei übergreifende Bäume eines einfachen Diagramms immer einige gemeinsame Kanten?

24

Ich habe nur wenige Fälle ausprobiert und festgestellt, dass zwei Spannbäume eines einfachen Diagramms einige gemeinsame Kanten haben. Ich meine, ich konnte bisher kein Gegenbeispiel finden. Aber das konnte ich auch nicht beweisen oder widerlegen. Wie kann man diese Vermutung beweisen oder widerlegen?

graphs graph-theory spanning-trees Herr Sigma.
quelle

46

Nein, betrachten Sie das vollständige Diagramm : $K_4$

Es hat die folgenden kantengetrennten Bäume: Bildbeschreibung hier eingeben

Bjørn Kjos-Hanssen
quelle

2

Sie können jeden Baum planar machen, indem Sie einen förmigen und einen förmigen Baum nehmen . Sie können das Ganze planar machen, indem Sie die Kante vom oberen rechten zum unteren linken Eckpunkt als Kurve außerhalb des Quadrats zeichnen.

N

$N$

Z

$Z$

Akkumulation

@kelalaka Wir haben keine brauchen eine komplette grafische Darstellung, nicht (man stelle sich, dies zu tun gleiche Art der Sache auf - es sei denn , ich meine Vermutung verpasst haben, Sie haben ein paar nicht verwendete Kanten , die entfernt werden kann, so dass es nicht mehr vollständig (weil Jeder Scheitelpunkt benötigt 2-4 überquerte Kanten, und jeder Scheitelpunkt in verfügt über 5 Kanten, sodass jeder Scheitelpunkt an mindestens eine nicht verwendete Kante angehängt wird. ist wahrscheinlich das beste Beispiel - es ist bekannt, leicht zu visualisieren (vergleichsweise wenige Kanten) und hat sehr einfache Spannbäume.

K_{5}

$K_5$

K_{5}

$K_5$

K_{4}

$K_4$

Fund Monica's Lawsuit

14

Für interessierte Leser gibt es einige Untersuchungen zur Zerlegung von Graphen in kantendisjunkte Bäume .

Die klassischen Arbeiten über das Problem der Zerlegung eines Graphen in Faktoren $n$ durch WT Tutte und kantendisjunkte Bäume endlicher Graphen von C. St.JA Nash-Williams beschreiben Graphen, die paarweise kantendisjunkte enthalten Bäume überspannen. $k$

Zum Beispiel zeigt die Arbeit Bizyklische Zerlegung vollständiger Graphen in aufspannende Bäume von Dalibor Froncek, wie vollständige Graphen in isomorphe aufspannende Bäume zerlegt werden . $K_{4k+2}$ ${2k+1}$

Zum Beispiel zeigt die Arbeit Factorizations of Complete Graphs in Spanning Trees mit allen möglichen Maximalgraden von Petr Kovář und Michael Kubesa, wie man zu Spanning Trees mit einem bestimmten Maximalgrad faktorisiert . $K_{2n}$

Sie können nach mehr suchen. Zum Beispiel eine Google-Suche nach der Zerlegung eines Graphen in übergreifende Bäume .

Apass.Jack
quelle

9

$K_4$

Nein, es stimmt nicht, dass zwei übergreifende Bäume eines Diagramms gemeinsame Kanten haben.

Betrachten Sie das Raddiagramm:

Sie können einen Spannbaum mit Kanten "innerhalb" der Schleife und einen anderen aus der äußeren Schleife erstellen.

Gokul
quelle

3

aber die äußere Schleife erreicht nicht den

Mittelknoten

Sie haben Recht, ich werde diese Antwort löschen, da die andere ausreicht.

Gokul

10

Sie können dies ändern, indem Sie die Out-Schleife abzüglich eines "Akkords" plus eines "Radius" und seines Komplements nehmen.

Boboquack

Ja. Eigentlich hatte ich nur so gesehen. @ Boboquack

Herr Sigma.

3

$K_n$ $n\geq4$

$2$

$K_n$ $n\geq4$ $n\geq4$ $2$

$2$

$2$ $2$
Gibt es einen anderen Graphen als das Rad oder das Rad als Untergraphen, der über Bäume mit unzusammenhängenden Kanten verfügt?

Herr Sigma.
quelle

Diese und weitere Fragen wurden in den von mir zitierten Papieren beantwortet. Wenn Sie interessiert sind, können Sie einen Blick darauf werfen.

Apass.Jack

Danke @ Apass.Jack Ich habe deine Antwort gesehen. Werde es anschauen.

Herr Sigma.

1

$K_{2k}$

G_{1} = {(v_{2 i}, v_{2 i + 1}), (v_{2 i}, v_{2 i + 2}), \dots, (v_{2 k - 2}, v_{2 k - 1})},

$G_1 = \{ (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),\dots,(v_{2k-2},v_{2k-1})\},$

G_{2} = {(v_{2 i + 1}, v_{2 i + 2}), (v_{2 i}, v_{2 i}), \dots (v_{2 (k - 1)}, v_{2 (k - 1)})}

$G_2 = \{ (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),\dots(v_{2(k-1)},v_{2(k-1)})\}$

$0\leq i < k$

$n$ $n+1$

Akkumulation
quelle

0

Wenn der Graph eine Brücke hat (dh eine Kante, deren Entfernung den Graph trennt), muss diese Kante zu jedem Spannbaum gehören. Intuitiv ist eine Brücke die einzige Kante, die ihre beiden Endpunkte verbindet, und gehört daher notwendigerweise zu jedem verbundenen Untergraphen.

Wenn andererseits eine Kante des Graphen zu einem Zyklus gehört, gibt es einen Spannbaum, der diese Kante nicht enthält.

Wenn also jede Kante eines Diagramms zu einem Zyklus gehört, ist keine Kante allen übergreifenden Bäumen gemeinsam (dh der Schnittpunkt der Kantensätze der übergreifenden Bäume ist der leere Satz).

mo2019
quelle

Haben zwei übergreifende Bäume eines einfachen Diagramms immer einige gemeinsame Kanten?

Antworten: