imported>Graf Alge: /* Siehe auch */

2024-09-12T14:42:25Z

Siehe auch

Neue Seite

Der Begriff '''Teilgraph''' beschreibt in der [[Graphentheorie]] eine Beziehung zwischen zwei [[Graph (Graphentheorie)|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 [[Nachbarschaft (Graphentheorie)|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 [[knotengewichteter Graph|knotengewichteten]] bzw. [[kantengewichteter Graph|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 (Mathematiker)|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|mini|800px|links|Beispiele für Teilgraphenbeziehungen]]
<div style="clear:both;"></div>

== 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, [https://diestel-graph-theory.com/ online])
* Lutz Volkmann: ''Fundamente der Graphentheorie'', Springer (Wien) 1996, ISBN 3-211-82774-9 ([https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf neuere Online-Version „Graphen an allen Ecken und Kanten“]; PDF; 3,51 MB)

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]

Teilgraph - Versionsgeschichte

imported>Graf Alge: /* Siehe auch */