Teilgraph

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

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

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

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

Gilt für einen Teilgraphen G 1 {\displaystyle G_{1}} zusätzlich, dass E 1 {\displaystyle E_{1}} alle Kanten zwischen den Knoten in V 1 {\displaystyle V_{1}} enthält, die auch in E 2 {\displaystyle E_{2}} vorhanden sind, so bezeichnet man G 1 {\displaystyle G_{1}} als den durch V 1 {\displaystyle V_{1}} induzierten Teilgraph oder als Untergraph von G 2 {\displaystyle G_{2}} und notiert diesen auch mit 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 W ⊆ V {\displaystyle W\subseteq V} bezeichnet man mit G ∖ W {\displaystyle G\setminus W} den induzierten Teilgraphen, der aus G = ( V , E ) {\displaystyle G=(V,E)} durch Weglassen der Knoten aus W {\displaystyle W} und aller mit diesen Knoten inzidenten Kanten entsteht, also G ∖ W = G [ V ∖ W ] {\displaystyle G\setminus W=G[V\setminus W]} .

Ein Teilgraph G 1 = ( V , E 1 ) {\displaystyle G_{1}=(V,E_{1})} von 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 V 1 = V 2 {\displaystyle V_{1}=V_{2}} ist (also ein aufspannender Teilgraph vorliegt), und Untergraph, dass V 1 ⊂ V 2 {\displaystyle V_{1}\subset V_{2}} und jede Kante aus G 2 {\displaystyle G_{2}} , die zwei Knoten aus G 1 {\displaystyle G_{1}} verbindet, auch eine Kante in G 1 {\displaystyle G_{1}} ist ( 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 G 1 {\displaystyle G_{1}} , G 2 {\displaystyle G_{2}} und G 3 {\displaystyle G_{3}} Teilgraphen von G {\displaystyle G} , aber nur G 2 {\displaystyle G_{2}} und G 3 {\displaystyle G_{3}} sind induzierte Teilgraphen. G 3 {\displaystyle G_{3}} entsteht dabei aus G {\displaystyle G} durch Weglassen der Knoten 1 , 3 , 7 {\displaystyle 1,3,7} und ihrer inzidenten Kanten, also ist G 3 = G ∖ { 1 , 3 , 7 } {\displaystyle G_{3}=G\setminus \{1,3,7\}} . Gleichzeitig ist G 3 {\displaystyle G_{3}} auch ein induzierter Teilgraph von 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