Teilgraph

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

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

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

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

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

Ein Teilgraph ${\displaystyle G_{1}=(V,E_{1})}${\displaystyle G_{1}=(V,E_{1})} von ${\displaystyle G_{2}=(V,E_{2})}${\displaystyle 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 ^[1] werden die Begriffe Teilgraph und Untergraph so verwendet, wie hier beschrieben. Im Lehrbuch von Claude Berge ^[2] dagegen bedeutet Teilgraph zusätzlich, dass ${\displaystyle V_{1}=V_{2}}${\displaystyle V_{1}=V_{2}} ist (also ein aufspannender Teilgraph vorliegt), und Untergraph, dass ${\displaystyle V_{1}\subset V_{2}}${\displaystyle V_{1}\subset V_{2}} und jede Kante aus ${\displaystyle G_{2}}${\displaystyle G_{2}}, die zwei Knoten aus ${\displaystyle G_{1}}${\displaystyle G_{1}} verbindet, auch eine Kante in ${\displaystyle G_{1}}${\displaystyle G_{1}} ist (${\displaystyle G_{1}}${\displaystyle 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.

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

• Unterteilungsgraph
• Minor (Graphentheorie)
• Spannbaum

• 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)

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

• Grundbegriff (Graphentheorie)