Teilgraphen und Minoren

Table of contents

1 Einleitung
2 Definitionen
3 Beispiele

Einleitung

Bei der Untersuchung von Grapheneigenschaften schließt man häufiger von lokalen auf globale Eigenschaften von Graphen und umgekehrt. Um deartige 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.

Definitionen

G₁=(V₁,E₁) heißt Teilgraph, Subgraph oder Untergraph von G₂=(V₂,E₂), falls V₁ Teilmenge von V₂ und

in Graphen ohne Mehrfachkanten E₁ Teilmenge von E₂ ist,
in ungerichteten Graphen mit Mehrfachkanten E₁(e)≤E₂(e) für alle zweielementigen Teilmengen e von V₂ gilt,
in gerichteten Graphen mit Mehrfachkanten E₁(e)≤E₂(e) für alle e 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 H zudem verlangt, dass die Gewichtsfunktion g von H kompatibel zu der Gewichtsfunktion f von G ist, d.h. für jeden Knoten v bzw. für jede Kante e von H gilt g(v)=f(v) bzw. g(e)=f(e).

Gilt zusätzlich:

in Graphen ohne Mehrfachkanten, e ist Element von E₂ für alle e aus E₁,
in ungerichteten Graphen mit Mehrfachkanten, E₁(e)=E₂(e) für alle zweielementigen Teilmengen e von V₂,
in gerichteten Graphen mit Mehrfachkanten, E₁(e)=E₂(e) für alle e 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₁]

Bemerkung: Induzierte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt.

Beispiele

kommen noch.