Teilgraph - LinkFang.de





Teilgraph


Der Begriff Teilgraph beschreibt in der Graphentheorie eine Beziehung zwischen zwei Graphen. Ein anderes Wort für Teilgraph ist Untergraph. 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 Untergraph 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 Teilgraphen von [math]G_2[/math] und notiert diesen auch mit [math]G_2[V_1][/math]. Ein induzierter Teilgraph ist also 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.

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].

Siehe auch

Literatur

ca:Glossari de teoria de grafs eo:Glosaro de grafeteorio es:Anexo:Glosario de teoría de grafos fr:Lexique de la théorie des graphes hu:Gráfelméleti fogalomtár it:Glossario di teoria dei grafi ko:그래프 이론 용어사전 ro:Glosar de teoria grafurilor ru:Глоссарий теории графов sl:Slovar izrazov teorije grafov

uk:Словник термінів теорії графів vi:Thuật ngữ lý thuyết đồ thị zh:图论术语


Kategorien: Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Teilgraph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.