zurück zu Grundbegriffe I
4 Spannender und gesättigter Teilgraph
4.1 Teilgraph
Ein Teilgraph ist ein Ausschnitt aus einem Graphen, mit einer Teilmenge an Knoten dieses Graphen, wobei maximal die Kanten vertreten sein dürfen, die auch im Graphen diese Knoten verbinden. Es kann auch ein od. mehrere isolierte Knoten vorkommen.
Def.: Ein Graph X1 = (V1,E1) heißt Teilgraph von X = (V,E), wenn V1 ⊆ V und E1 ⊆ E ist.
4.2 Spannender Teilgraph
Besitzt alle Knoten des Graphen, aber nicht alle der Kanten, die diese Knoten verbinden, wie im Graphen.
Ein Teilgraph X1 von X ist ein spannender Teilgraph von X, wenn V1 = V ist.
4.3 Gesättigter Teilgraph
Teilgraph herausgeschnitten aus Graph, Knoten und alle seine Kanten, mit denen sie untereinander verbunden sind.
Äußere Knoten und deren inzidente Kanten fallen weg.
Def.: Enthält E1 alle Kanten aus E, deren Endpunkte in V1 liegen, so sagt man, dass X1 von V1 ⊆ V in X aufgespannt wird, oder dass X1 ein gesättigter Teilgraph von X ist.
4.3.1 Spannender, gesättigter Teilgraph
Ein Teilgraph ist der Graph selbst, da eine Menge seine Teilmenge sein kann.
V1 = V2
V1 = V
gesättigt + spannend = derselbe Graph ≠ der gleiche Graph