TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 305

Aus VoWi
Zur Navigation springen Zur Suche springen

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)

Hilfreiches[Bearbeiten]

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 Knoten in einem vollständigen Graphen (bezieht sich auf V \times V) berechnet sich über \frac{n(n-1)}{2}.

Lösung[Bearbeiten]

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.