Teilgraph

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

Definitionen

Ein Graph <math>G_1=(V_1,E_1)</math> heißt Teilgraph oder Subgraph von <math>G_2=(V_2,E_2)</math>, wenn seine Knotenmenge <math>V_1</math> Teilmenge von <math>V_2</math> und seine Kantenmenge <math>E_1</math> Teilmenge von <math> E_2</math> ist, also <math>V_1\subseteq V_2</math> und <math>E_1\subseteq E_2</math> gilt.

Umgekehrt heißt <math>G_2</math> dann Supergraph oder Obergraph von <math>G_1</math>.

Bei einem knotengewichteten bzw. kantengewichteten Graphen <math>G_2</math> wird von einem Teilgraphen <math>G_1</math> zudem verlangt, dass die Gewichtsfunktion <math>g_1</math> von <math>G_1</math> kompatibel zu der Gewichtsfunktion <math>g_2</math> von <math>G_2</math> sein muss, d. h. für jeden Knoten <math>v \in V_1</math> gilt <math>g_1(v)=g_2(v)</math> bzw. für jede Kante <math>e \in E_1</math> gilt <math>g_1(e)=g_2(e)</math>.

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

Ein Teilgraph <math>G_1=(V,E_1)</math> von <math>G_2=(V,E_2)</math>, 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<ref>Klaus Wagner: Graphentheorie, BI-Hochschultaschenbücher (1969), Band 248, Kap. I, §3, Definition 4</ref> werden die Begriffe Teilgraph und Untergraph so verwendet, wie hier beschrieben. Im Lehrbuch von Claude Berge<ref>Claude Berge: Programme, Spiele, Transportnetze, Teubner-Verlag 1969, Zeiter Teil, Kap. I, Absatz 1, Seite 121</ref> dagegen bedeutet Teilgraph zusätzlich, dass <math>V_1=V_2</math> ist (also ein aufspannender Teilgraph vorliegt), und Untergraph, dass <math>V_1\subset V_2</math> und jede Kante aus <math>G_2</math>, die zwei Knoten aus <math>G_1</math> verbindet, auch eine Kante in <math>G_1</math> ist (<math>G_1</math> 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 <math>G_1</math>, <math>G_2</math> und <math>G_3</math> Teilgraphen von <math>G</math>, aber nur <math>G_2</math> und <math> G_3</math> sind induzierte Teilgraphen. <math>G_3</math> entsteht dabei aus <math>G</math> durch Weglassen der Knoten <math>1,3,7</math> und ihrer inzidenten Kanten, also ist <math>G_3=G \setminus \{1,3,7\}</math>. Gleichzeitig ist <math>G_3</math> auch ein induzierter Teilgraph von <math>G_2</math>.

Datei:Teilgraphenbeziehungen.svg

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)

Einzelnachweise

<references />