Teilgraph

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Untergraph)
Wechseln zu: Navigation, Suche

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

Definitionen[Bearbeiten | Quelltext bearbeiten]

Ein Graph heißt Teilgraph oder Untergraph oder Subgraph von , wenn seine Knotenmenge Teilmenge von und seine Kantenmenge Teilmenge von ist, also und gilt.

Umgekehrt heißt dann Supergraph oder Obergraph von .

Bei einem knotengewichteten bzw. kantengewichteten Graphen wird von einem Teilgraphen zudem verlangt, dass die Gewichtsfunktion von kompatibel zu der Gewichtsfunktion von sein muss, d.h. für jeden Knoten gilt bzw. für jede Kante gilt .

Gilt für einen Teilgraphen zusätzlich, dass alle Kanten zwischen den Knoten in enthält, die auch in vorhanden sind, so bezeichnet man als den durch induzierten Teilgraphen von und notiert diesen auch mit . Ein induzierter Teilgraph ist also immer eindeutig durch den Obergraphen und die gewählte Knotenmenge bestimmt. Für eine Knotenmenge bezeichnet man mit den induzierten Teilgraphen, der aus durch Weglassen der Knoten aus und aller mit diesen Knoten inzidenten Kanten entsteht, also .

Ein Teilgraph von , der alle Knoten seines Obergraphen enthält, wird aufspannender Teilgraph oder Faktor genannt.

Beispiele[Bearbeiten | Quelltext bearbeiten]

In der folgenden Abbildung sind die Graphen , und Teilgraphen von , aber nur und sind induzierte Teilgraphen. entsteht dabei aus durch Weglassen der Knoten und ihrer inzidenten Kanten, also ist . Gleichzeitig ist auch ein induzierter Teilgraph von .

Beispiele für Teilgraphenbeziehungen

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]