Teilgraph

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^[1] 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^[2] 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

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

Literatur

• 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)
• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5. (354 Seiten, online)

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