Teilgraph

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 Teilstruktur und Unterstruktur aus der Modelltheorie. Eine Unterstruktur 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 Teilstrukturen können also zusätzlich noch Beziehungen zwischen den Elementen wegfallen. Jede Unterstruktur ist eine Teilstruktur 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.

Teilgraph

Ein Graph $G_1=(V_1,E_1)$ heißt Teilgraph oder Subgraph von $G_2=(V_2,E_2)$, 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
  $\textstyle 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) \mbox{ bzw. } g_1(e) = g_2(e)$.

Untergraph bzw. induzierter Teilgraph

Gilt zusätzlich:

• in Graphen ohne Mehrfachkanten,
  $\textstyle 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,
  $\textstyle E_1(v) = E_2(v) \cap {|V_1| \choose 2}$
  für alle zweielementigen Teilmengen v von V₂,
• in gerichteten Graphen mit Mehrfachkanten,
  $\textstyle 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_2[V_1]$ 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 für Teilgraphen und induzierte Teilgraphen

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.

Beispiele für Teilgraphenbeziehungen

Siehe auch

• Minor (Graphentheorie)
• Satz von Kuratowski
• Krausz-Partition

Literatur

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

Weblinks

• Eric W. Weisstein: Subgraph. In: MathWorld. (englisch)