Teilgraph

Der Begriff Teilgraph beschreibt in der Graphentheorie eine Beziehung zwischen zwei Graphen. Ein Graph $H$ ist Teilgraph des Graphen $G$, wenn alle Knoten und Kanten von $H$ auch in $G$ enthalten sind. Anders gesagt: Ein Teilgraph $H$ entsteht aus einem Graphen $G$, indem einige Knoten und Kanten aus $G$ entfernt werden. Dabei müssen beim Entfernen eines Knotens auch alle inzidenten Kanten mit entfernt werden.

Definitionen

Ein Graph $G_{1}=(V_{1},E_{1})$ heißt Teilgraph oder Subgraph von $G_{2}=(V_{2},E_{2})$, wenn seine Knotenmenge $V_{1}$ Teilmenge von $V_{2}$ und seine Kantenmenge $E_{1}$ Teilmenge von $E_{2}$ ist, also $V_{1}\subseteq V_{2}$ und $E_{1}\subseteq E_{2}$ gilt.

Umgekehrt heißt $G_{2}$ dann Supergraph oder Obergraph von $G_{1}$.

Bei einem knotengewichteten bzw. kantengewichteten Graphen $G_{2}$ wird von einem Teilgraphen $G_{1}$ zudem verlangt, dass die Gewichtsfunktion $g_{1}$ von $G_{1}$ kompatibel zu der Gewichtsfunktion $g_{2}$ von $G_{2}$ sein muss, d. h. für jeden Knoten $v\in V_{1}$ gilt $g_{1}(v)=g_{2}(v)$ bzw. für jede Kante $e\in E_{1}$ gilt $g_{1}(e)=g_{2}(e)$.

Gilt für einen Teilgraphen $G_{1}$ zusätzlich, dass $E_{1}$ alle Kanten zwischen den Knoten in $V_{1}$ enthält, die auch in $E_{2}$ vorhanden sind, so bezeichnet man $G_{1}$ als den durch $V_{1}$ induzierten Teilgraph oder als Untergraph von $G_{2}$ und notiert diesen auch mit $G_{2}[V_{1}]$. Ein induzierter Teilgraph ist immer eindeutig durch den Obergraphen und die gewählte Knotenmenge bestimmt. Für eine Knotenmenge $W\subseteq V$ bezeichnet man mit $G\setminus W$ den induzierten Teilgraphen, der aus $G=(V,E)$ durch Weglassen der Knoten aus $W$ und aller mit diesen Knoten inzidenten Kanten entsteht, also $G\setminus W=G[V\setminus W]$.

Ein Teilgraph $G_{1}=(V,E_{1})$ von $G_{2}=(V,E_{2})$, der alle Knoten seines Obergraphen enthält, wird aufspannender Teilgraph oder Faktor genannt.

Diese Bezeichnungen sind in der Literatur nicht einheitlich. Im unten angegebenen Lehrbuch von Klaus Wagner werden die Begriffe Teilgraph und Untergraph so verwendet, wie hier beschrieben. Im Lehrbuch von Claude Berge dagegen bedeutet Teilgraph zusätzlich, dass $V_{1}=V_{2}$ ist (also ein aufspannender Teilgraph vorliegt), und Untergraph, dass $V_{1}\subset V_{2}$ und jede Kante aus $G_{2}$, die zwei Knoten aus $G_{1}$ verbindet, auch eine Kante in $G_{1}$ ist ($G_{1}$ also ein induzierter Teilgraph ist), der allgemeine Fall heißt dann dort Teil-Untergraph. Es empfiehlt sich daher, bei jedem Autor, die verwendete Definition zu prüfen.

Beispiele

In der folgenden Abbildung sind die Graphen $G_{1}$, $G_{2}$ und $G_{3}$ Teilgraphen von $G$, aber nur $G_{2}$ und $G_{3}$ sind induzierte Teilgraphen. $G_{3}$ entsteht dabei aus $G$ durch Weglassen der Knoten $1,3,7$ und ihrer inzidenten Kanten, also ist $G_{3}=G\setminus \{1,3,7\}$. Gleichzeitig ist $G_{3}$ auch ein induzierter Teilgraph von $G_{2}$.

Beispiele für Teilgraphenbeziehungen

Siehe auch

• Unterteilungsgraph
• Minor (Graphentheorie)
• Spannbaum

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5. (354 Seiten, online)
• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9 (neuere Online-Version „Graphen an allen Ecken und Kanten“; PDF; 3,51 MB)