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 Begriffe Teilgraph und Untergraph sind Spezialfälle der entsprechenden allgemeineren Begriffe Teil-Struktur und Unter-Struktur aus der Modelltheorie. Eine Unter-Struktur ist anschaulich gesehen ein Ausschnitt aus einer Struktur, bei der alle Beziehungen zwischen den Elementen (bzw. Knoten) erhalten bleiben. Beispiel siehe unten: G2, G3 sind Untergraphen von G, aber G1 ist kein Untergraph, sondern nur ein Teilgraph von G. In Teil-Strukturen können also zusätzlich noch Beziehungen zwischen den Elementen wegfallen. Jede Unter-Struktur ist eine Teil-Struktur aber nicht umgekehrt. Im folgenden werden beide Begriffe für Graphen näher definiert.

Anschaulich bedeutet es folgendes: Um aus einem Graphen G einen Teilgraph T zu erzeugen wählt man beliebige Knoten aus G und fügt sie T hinzu. Einen Teilgraph erhält man, indem man einige Kanten von T´s Knoten auch zu T hinzufügt. Einen Untergraphen erhält man, indem man alle Kanten zwischen T´s Knoten zu T hinzufügt.

Definitionen

Teilgraph

Ein Graph G₁ = (V₁,E₁) heißt Teilgraph oder Subgraph 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₁(v) = g₂(v) bzw. g₁(e) = g₂(e).

Untergraph bzw. 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₁] oder auch einfach G_A (G=G₂, A=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.

Minor

Ein Graph G₁ wird Minor des Graphen G₂ genannt, falls G₁ isomorph aus einem Teilgraphen von G₂ durch Kantenkontraktion entsteht. Mit anderen Worten: G₁ muss aus G₂ durch Löschen von Knoten und/oder Kanten und/oder Kantenkontraktion gewonnen werden können. Kantenkontraktion bedeutet, dass zwei adjazente (benachbarte) Knoten V₁ und V₂ unter Entfernung einer zu diesen beiden Knoten inzidenten Kante zu einem Knoten V₁₂ verschmolzen werden. Dieser Knoten V₁₂ hat zu allen Knoten Kanten, zu denen zuvor V₁ oder V₂ eine Kante hatte.

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

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

Neil Robertson und Paul Seymour (Satz von 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

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9 (neuere, elektronische Online-Version "Graphen an allen Ecken und Kanten")
• Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0 (elektronische Online-Version)

Weblinks

• Eric W. Weisstein: Graph Minor. In: MathWorld. (englisch)
• Eric W. Weisstein: Subgraph. In: MathWorld. (englisch)
• Minor eines Graphen in der Encyclopaedia of Mathematics