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

Definitionen

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

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

Diese Bezeichnungen sind nicht einheitlich. Im unten angegebenen Lehrbuch von Klaus Wagner wird in dieser Allgemeinheit nur der Begriff Teilgraph verwendet und ein Untergraph als Teilgraph definiert, der zusätzlich die Eigenschaft hat, dass jede Kante aus ${\displaystyle G_{2}}$, die zwei Knoten aus ${\displaystyle G_{1}}$ verbindet, auch eine Kante in ${\displaystyle G_{1}}$ ist. Im Lehrbuch von Claude Berge bedeutet Teilgraph zusätzlich, dass ${\displaystyle V_{1}=V_{2}}$ ist, und Untergraph, dass ${\displaystyle V_{1}\subset V_{2}}$ und jede Kante aus ${\displaystyle G_{2}}$, die zwei Knoten aus ${\displaystyle G_{1}}$ verbindet, auch eine Kante in ${\displaystyle G_{1}}$ ist, der allgemeine Fall heißt dann dort Teil-Untergraph. Es empfiehlt sich daher, bei jedem Autor, die verwendete Definition zu prüfen.

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

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

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

Beispiele

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

Siehe auch

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

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)

Einzelnachweise

1. ↑ Klaus Wagner: Graphentheorie, BI-Hochschultaschenbücher (1969), Band 248, Kap. I, §3, Definition 4
2. ↑ Claude Berge: Programme, Spiele, Transportnetze, Teubner-Verlag 1969, Zeiter Teil, Kap. I, Absatz 1, Seite 121