DisMat UE 07

ex7-0.pdf

7.1

Show that all forests are bipartite.

Definitionen

Ein Graph ist Bipartite wenn es in dem Graph nur Verbindung in zwei Disjunkten Untermengen gibt.

$$G=(A\cup B,E)\forall (a,b)\in E:a\in A,b\in B$$

Ein Wald besteht aus verbundene Komponenten die Bäumen sind. Also reicht es zu zeigen das ein Baum bipartite ist.

Beweis: Alle Bäume sind bipartite

Ein Baum $G=(V,E)$

Wähle eine Knoten $v\in V$.
Ein Baum ist kreisfrei, somit gibt es nur einen Pfad von $v$ zu einem Knoten $v^{\prime }\in V$.
$d(v^{\prime })$ ist die Länge des Pfads.

$A:=\{v^{\prime }\in V:d(v^{\prime })\text{ ist gerade}\}$
$B:=\{v^{\prime }\in V:d(v^{\prime })\text{ ist ungerade}\}$

• $A$ und $B$ sind disjunkt, da es nur ein Pfad pro $v^{\prime }$ gibt.

• Es gibt nur Kanten von $A$ zu $B$ da es im Baum nur Verbindung von Knoten mit geraden zu Knoten mit ungeraden $d(v^{\prime })$ gibt.

7.4

Prove that a 3-path (a path with 3 edges) is the only tree whose complement is also a tree.

Transclude of Dis-Mathe-UE-7.4.excalidraw