Bäume
Alle Bäume sind Graphen – aber welche Graphen sind Bäume?
Merke: zyklisch
Ein Graph, der einen Zyklus enthält, heißt zyklisch. Enthält er keinen Zyklus, heißt er azyklisch.
Merke: Baum
Ein Baum ist ein gerichteter, azyklischer Graph mit diesen Eigenschaften: Genau ein Knoten hat Eingangsgrad 0 – die Wurzel. Alle anderen Knoten haben Eingangsgrad 1.
Knoten mit Ausgangsgrad 0 heißen Blätter, alle Knoten, die weder Wurzel noch Blatt sind, innere Knoten.
Die Tiefe eines Knotens ist sein Abstand zur Wurzel, seine Höhe der größte Abstand zu einem Blatt darunter. Die Höhe des Baums ist die größte Tiefe. Zeige auf einen Knoten, um seine Tiefe und Höhe zu sehen.
Führt eine Kante von B nach D, ist B der Eltern-Knoten und D ein Kind-Knoten; Kinder desselben Elternknotens sind Geschwister.
G = (V, E)
V = {A, B, C, D, E, F, G}
E = {(A,B), (A,C), (B,D), (B,E), (C,F), (E,G)}
Aufgabe 4: Die Knoten A bis G sind gezeichnet. Ergänze die Kanten E = {(C,E), (C,G), (D,F), (E,D), (E,A), (G,B)}.
Aufgabe 4: Die Knoten A bis G sind gezeichnet. Ergänze die Kanten E = {(C,E), (C,G), (D,F), (E,D), (E,A), (G,B)}.
Aufgabe 4: Ist dieser Graph ein Baum?