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

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 \lbrace (x,x)\mid x\in V\rbrace )$

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: $\left|V(T)\right|=\left|E(T)\right|+1$

Diese Eigenschaft soll für $T^{K}$ auch gelten, denn wir wollen, dass er auch ein Baum ist. $\left|V(T^{K})\right|=\left|E(T^{K})\right|+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: $\left|E(T^{K})\right|={\frac {\left|V(T)\right|(\left|V(T)\right|-1)}{2}}-\left|E(T)\right|$

Also:

$\left|V(T^{K})\right|=\left|E(T^{K})\right|+1$

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

Ich ersetze $\left|E(T)\right|$ durch $\left|V(T)\right|-1$ (laut Voraussetzung an unseren Baum, siehe oben). Außerdem substituiere ich $\left|V(T^{K})\right|$ 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=\lbrace 1,2,3,4,\rbrace ,E=\lbrace (1,2),(2,3),(3,4)\rbrace$

2.) $V=\lbrace 1,2,3,4,\rbrace ,E=\lbrace (1,2),(1,3),(1,4)\rbrace$

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=\lbrace 1,2,3,4,\rbrace ,E=\lbrace (1,2),(1,3),(3,4)\rbrace$ ?

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.