TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 312

Man bestimme alle Bäume T, für die auch $T^K$ ein Baum ist. $T^K$ bezeichne einen komplementären Graphen definiert durch: $V(T^K)=V(T)$ und $E(T^K)=(V\times V)\setminus (E(T)\cup \{(x,x)\mid x\in V\})$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Ein Baum ist ein zusammenhängender Graph, der keine Kreise enthält. Die Anzahl der Knoten ist gleich der Anzahl der Kanten plus 1. $\left|V\right|=\left|E\right|+1$

Die Anzahl der Kanten in einem vollständigen Graphen (bezieht sich auf $V\times V$) berechnet sich über $\frac{n(n-1)}{2}$.

Lösung

Wenn man das mit ein paar Bäumen ausprobiert, merkt man, dass es ab 5 Knoten Schwierigkeiten gibt. Mit der obigen Formel können wir zeigen, welche Graphen überhaupt infrage kommen:

Wir wissen: $|V(T)|=|E(T)|+1$

Diese Eigenschaft soll für $T^K$ auch gelten, denn wir wollen, dass er auch ein Baum ist. $|V(T^K)|=|E(T^K)|+1$

Jetzt ersetzen wir mithilfe der Angabe $V(T^K)$ durch $V(T)$, da diese gleich sein sollen. Außerdem ist $E(T^K)$ definiert als (wörtlich aus der Angabe interpretiert): Die Menge aller Kanten, die überhaupt vorkommen könnten, ohne die Kanten aus T und ohne Schlingen (Kante von einem Knoten zu sich selbst). Das heißt wir können bestimmen wieviele das sind: $|E(T^K)|=\frac{|V(T)|(|V(T)|-1)}{2}-|E(T)|$

Also:

$|V(T^K)|=|E(T^K)|+1$

$|V(T)|=\frac{|V(T)|(|V(T)|-1)}{2}-|E(T)|+1$

Ich ersetze $|E(T)|$ durch $|V(T)|-1$ (laut Voraussetzung an unseren Baum, siehe oben). Außerdem substituiere ich $|V(T^K)|$ jetzt durch x, damit es leserlich bleibt.

$x=\frac{x(x-1)}{2}-(x-1)+1$

Ab jetzt nur noch rechnen:

$x=\frac{x(x-1)}{2}-x+2$

$2x=x^2-3x+4$

$0=x^2-5x+4$

$x_1=1$

$x_2=4$

Das heißt, es kommen nur Graphen mit einem oder vier Knoten infrage!

Der Graph mit einem Knoten ist eine Lösung. Die zweite Lösung kann nur ein Baum sein, der 4 Knoten hat. Es gibt nur zwei verschiedene Bäume, die 4 Knoten haben:

1.) $V=\{1,2,3,4,\},E=\{(1,2),(2,3),(3,4)\}$

2.) $V=\{1,2,3,4,\},E=\{(1,2),(1,3),(1,4)\}$

Der erste ist eine Lösung, der zweite nicht ("Beweis per Demonstration"). Unsere Rechnung hat auch gezeigt, dass es keine anderen Lösungen gibt.

edit: gibt es nicht eine dritte Lösung? $V=\{1,2,3,4,\},E=\{(1,2),(1,3),(3,4)\}$ ?

Antwort auf den edit: Nein, das ist das gleiche wie 1., nur dass die Variable 1 hier 2 heißt und umgekehrt. Zeichne es am besten auf, dann ist es ziemlich eindeutig.