Teilgraph

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

Bei der Untersuchung von Grapheneigenschaften schließt man häufiger von lokalen auf globale Eigenschaften von Graphen und umgekehrt. Um derartige Vorgänge besser beschreiben zu können, definiert man geeignete Relationen zwischen Graphen und lokalen Gebieten innerhalb dieser Graphen. Besonders wichtig sind dabei Teilgraphenbeziehungen. Die Begriffe Teilgraph und Untergraph sind Spezialfälle der entsprechenden allgemeineren Begriffe Teilstruktur und Unterstruktur aus der Modelltheorie. Eine Unterstruktur ist anschaulich gesehen ein Ausschnitt aus einer Struktur, bei der alle Beziehungen zwischen den Elementen (bzw. Knoten) erhalten bleiben. Beispiel siehe unten: G2, G3 sind Untergraphen von G, aber G1 ist kein Untergraph, sondern nur ein Teilgraph von G. In Teilstrukturen können also zusätzlich noch Beziehungen zwischen den Elementen wegfallen. Jede Unterstruktur ist eine Teilstruktur aber nicht umgekehrt. Im folgenden werden beide Begriffe für Graphen näher definiert.

Anschaulich bedeutet es folgendes: Um aus einem Graphen G einen Teilgraph T zu erzeugen wählt man beliebige Knoten aus G und fügt sie T hinzu. Einen Teilgraph erhält man, indem man einige Kanten von T´s Knoten auch zu T hinzufügt. Einen Untergraphen erhält man, indem man alle Kanten zwischen T´s Knoten zu T hinzufügt.

Teilgraph[Bearbeiten]

Ein Graph G_1=(V_1,E_1) heißt Teilgraph oder Subgraph von G_2=(V_2,E_2), falls  V_1Teilmenge von  V_2, also V_1\subseteq V_2 und

Umgekehrt heißt  G_2 Supergraph oder Obergraph von  G_1.

Bei einem knotengewichteten bzw. kantengewichteten Graph   G_2 wird von einem Teilgraph  G_1 zudem verlangt, dass die Gewichtsfunktion  g_1 von  G_1 kompatibel zu der Gewichtsfunktion  g_2 von  G_2 ist, d.h. für jeden Knoten  v bzw. für jede Kante  e von  G_2 gilt g_1(v) = g_2(v) \mbox{ bzw. } g_1(e) = g_2(e).

Untergraph bzw. induzierter Teilgraph[Bearbeiten]

Gilt zusätzlich:

  • in Graphen ohne Mehrfachkanten,
    \textstyle E_1 = E_2 \cap {|V_1| \choose 2}
    , d.h. G1 enthält alle Kanten zwischen den Knoten in V1, die auch in G2 vorhanden sind.
  • in ungerichteten Graphen mit Mehrfachkanten,
    \textstyle E_1(v) = E_2(v) \cap {|V_1| \choose 2}
    für alle zweielementigen Teilmengen v von V2,
  • in gerichteten Graphen mit Mehrfachkanten,
    \textstyle E_1(v) = E_2(v) \cap {|V_1| \choose 2}
    für alle v aus dem kartesischen Produkt V2xV2,

so bezeichnet man G1 auch als den durch V1 induzierten Teilgraph von G2 und notiert diesen auch mit G_2[V_1] oder auch einfach G_A (G=G2, A=V1).

Bemerkungen:

  • Induzierte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt.
  • Besonders wichtige Teilgraphen entstehen durch das Weglassen von Knoten bzw. Kanten. Sei der Graph G(V,E) gegeben, dann bezeichnet
    G\setminus A, A \subseteq V
    den Graphen, der durch Weglassen der Knoten aus A und aller mit diesen Knoten inzidenten Kanten entsteht. Die so entstehenden Teilgraphen sind immer induzierte Teilgraphen.

Beispiele für Teilgraphen und induzierte Teilgraphen[Bearbeiten]

Subgraphexpl

In der obigen Abbildung ist links ein einfacher Graph  G_1 gegeben.  G_2 ist weder Teilgraph noch Untergraph, da eine Kante nur mit einem Knoten inzidiert. Streng genommen handelt es sich nicht einmal um einen Graphen, da Kanten nicht unabhängig von Knoten existieren können.  G_3 ist Teilgraph von  G_1, da  V_1=V_3 und  E_3 =E_1 \backslash \{(2,3), (4,1)\} \subset E_1 gilt. Es handelt sich aber nicht um eine Untergraphen von G_1 , da z.B. die Kante  (1,4) nicht in der Kantenmenge enthalten ist.  G_4 ist Untergraph von  G_1 und auch der induzierte Teilgraph der Knotenmenge  V_4=\{1,3,4\}, da alle Kanten, welche mit zwei dieser Knoten inzidieren auch im Graphen enthalten sind.

In der folgenden Abbildung sind die Graphen  G_1,  G_2,  G_3 Teilgraphen von  G, wobei aber nur  G_2 und  G_3 induzierte Teilgraphen sind.  G_3 entsteht dabei aus  G durch Weglassen der Knoten  1,3,7 und ihrer inzidenten Kanten.

Beispiele für Teilgraphenbeziehungen

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]