Teilgraphen und Minoren

Bei der Untersuchung von Grapheneigenschaften schließt man häufiger von lokalen auf globale Eigenschaften von Graphen und umgekehrt. Um derartige Vorgänge besser beschreiben zu können, definiert man geeignete Relationen zwischen Graphen und lokalen Gebieten innerhalb dieser Graphen. Besonders wichtig sind dabei Teilgraphenbeziehungen, die im Folgenden näher definiert werden.

Inhaltsverzeichnis

1 Definitionen

1.1 Teilgraph
1.2 Induzierter Teilgraph
1.3 Beispiele
1.4 Minor

Definitionen

Teilgraph

G₁=(V₁,E₁) heißt Teilgraph, Subgraph oder Untergraph von G₂=(V₂,E₂), falls V₁ Teilmenge von V₂, also $V_1\subseteq V_2$ und

in Graphen ohne Mehrfachkanten E₁ Teilmenge von E₂ ist, $E_1\subseteq E_2$ ,
in ungerichteten Graphen mit Mehrfachkanten $E_1(v)\subseteq E_2(v)$ für alle zweielementigen Teilmengen v von V₂, also
$v:={V_2 \choose 2}$
, gilt, wobei $E 1 / 2 (v)$ die Menge der Kanten zwischen den Knoten aus v ist,
in gerichteten Graphen mit Mehrfachkanten $E_1(v)\subseteq E_2(v)$ für alle Teilmengen v aus dem kartesischen Produkt V₂xV₂ gilt.

Umgekehrt heißt G₂ Supergraph oder Obergraph von G₁.

Bei einem knotengewichteten bzw. kantengewichteten Graph G₂ wird von einem Teilgraph G₁ zudem verlangt, dass die Gewichtsfunktion g₁ von G₁ kompatibel zu der Gewichtsfunktion g₂ von G₂ ist, d.h. für jeden Knoten v bzw. für jede Kante e von G₂ gilt $g 1 (v) = g 2 (v) bzw. g 1 (e) = g 2(e)$ .

Induzierter Teilgraph

Gilt zusätzlich:

in Graphen ohne Mehrfachkanten,
$E_1 = E_2 \cap {V_1 \choose 2}$
, d.h. G₁ enthält alle Kanten zwischen den Knoten in V₁, die auch in G₂ vorhanden sind.
in ungerichteten Graphen mit Mehrfachkanten,
$E_1(v) = E_2(v) \cap {V_1 \choose 2}$
für alle zweielementigen Teilmengen v von V₂,
in gerichteten Graphen mit Mehrfachkanten,
$E_1(v) = E_2(v) \cap {V_1 \choose 2}$
für alle v aus dem kartesischen Produkt V₂xV₂,

so bezeichnet man G₁ auch als den durch V₁ induzierten Teilgraph von G₂ und notiert diesen auch mit G₂[V₁]

Bemerkungen:

Induzierte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt.
Besonders wichtige Teilgraphen entstehen durch das Weglassen von Knoten bzw. Kanten. Sei der Graph G(V,E) gegeben, dann bezeichnet
$G\setminus A, A \subseteq V$
den Graphen, der durch Weglassen der Knoten aus A und aller mit diesen Knoten inzidenten Kanten entsteht. Die so entstehenden Teilgraphen sind immer induzierte Teilgraphen!

Beispiele

In der folgenden Abbildung sind die Graphen G₁, G₂, G₃ Teilgraphen von G, wobei aber nur G₂ und G₃ induzierte Teilgraphen sind. G₃ entsteht dabei aus G durch Weglassen der Knoten 1,3,7 und ihrer inzidenten Kanten.

bild:Forbys_teilgraph_example.png

Minor

Ein Graph G₁ wird Minor des Graphen G₂ genannt, falls G₁ isomorph zu einem durch Knotenverschmelzung entstandenen Untergraph von G₂ ist. Knotenverschmelzung bedeutet hier, dass zwei adjazente (benachbarte) Knoten V₁ und V₂ unter Entfernung einer zu diesen beiden Knoten inzidenten Kante zu einem Knoten V₁₂ „verschmolzen“ werden, wobei alle restlichen Kanten beibehalten werden.

Zum Beispiel ist in der folgenden Abbildung G1 ein Minor von G2.

bild:Forbys_graphs_minor-relation2.png

Die Minor-Beziehung definiert eine partielle Ordnungsrelation auf den Isomorphie-Klassen von Graphen.

Robertson und Seymour haben gezeigt, dass für jede unendliche Folge G₁,G₂,... von endlichen Graphen stets Indizes i und j mit i < j existieren, so dass G_i ein Minor von G_j ist.

Siehe auch: Satz von Kuratowski, Satz von Robertson und Seymour