Teilgraph - de.LinkFang.org

Teilgraph

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

Inhaltsverzeichnis

Definitionen


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

Umgekehrt heißt G_{2} dann Supergraph oder Obergraph von 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 G_{2}, die zwei Knoten aus G_{1} verbindet, auch eine Kante in 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 G_{2}, die zwei Knoten aus G_{1} verbindet, auch eine Kante in 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 G_{2} wird von einem Teilgraphen G_{1} zudem verlangt, dass die Gewichtsfunktion g_{1} von G_{1} kompatibel zu der Gewichtsfunktion g_{2} von G_{2} sein muss, d. h. für jeden Knoten v \in V_1 gilt g_1(v)=g_2(v) bzw. für jede Kante e \in E_1 gilt g_1(e)=g_2(e).

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

Ein Teilgraph G_1=(V,E_1) von 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 G_{1}, G_{2} und G_{3} Teilgraphen von G, aber nur G_{2} und G_{3} sind induzierte Teilgraphen. G_{3} entsteht dabei aus G durch Weglassen der Knoten 1,3,7 und ihrer inzidenten Kanten, also ist G_3=G \setminus \{1,3,7\}. Gleichzeitig ist G_{3} auch ein induzierter Teilgraph von G_{2}.

Siehe auch


Literatur


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



Kategorien: Grundbegriff (Graphentheorie)



Quelle: Wikipedia - https://de.wikipedia.org/wiki/Teilgraph (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 19.10.2019 10:14:45 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.