Teilgraphen und Minoren

Teilgraphen und Minoren

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 Teil-Struktur und Unter-Struktur aus der Modelltheorie. Eine Unter-Struktur 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 Teil-Strukturen können also zusätzlich noch Beziehungen zwischen den Elementen wegfallen. Jede Unter-Struktur ist eine Teil-Struktur 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.

Inhaltsverzeichnis

Definitionen

Teilgraph

Ein Graph G1 = (V1,E1) heißt Teilgraph oder Subgraph von G2 = (V2,E2), falls V1 Teilmenge von V2, also V_1\subseteq V_2 und

Umgekehrt heißt G2 Supergraph oder Obergraph von G1.

Bei einem knotengewichteten bzw. kantengewichteten Graph G2 wird von einem Teilgraph G1 zudem verlangt, dass die Gewichtsfunktion g1 von G1 kompatibel zu der Gewichtsfunktion g2 von G2 ist, d.h. für jeden Knoten v bzw. für jede Kante e von G2 gilt g1(v) = g2(v) bzw. g1(e) = g2(e).

Untergraph bzw. Induzierter Teilgraph

Gilt zusätzlich:

  • in Graphen ohne Mehrfachkanten,
    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,
    E_1(v) = E_2(v) \cap {|V_1| \choose 2}
    für alle zweielementigen Teilmengen v von V2,
  • in gerichteten Graphen mit Mehrfachkanten,
    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 G2[V1] oder auch einfach GA (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

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

Teilgraphenbeziehungen

Minor

Ein Graph G1 wird Minor des Graphen G2 genannt, falls G1 isomorph aus einem Teilgraphen von G2 durch Kantenkontraktion entsteht. Mit anderen Worten: G1 muss aus G2 durch Löschen von Knoten und/oder Kanten und/oder Kantenkontraktion gewonnen werden können. Kantenkontraktion bedeutet, dass zwei adjazente (benachbarte) Knoten V1 und V2 unter Entfernung einer zu diesen beiden Knoten inzidenten Kante zu einem Knoten V12 verschmolzen werden. Dieser Knoten V12 hat zu allen Knoten Kanten, zu denen zuvor V1 oder V2 eine Kante hatte.

Zum Beispiel ist in der folgenden Abbildung G1 ein Minor von G2.

Forbys graphs minor-relation2.png

Die Minor-Beziehung definiert eine partielle Ordnungsrelation auf den Isomorphie-Klassen von Graphen.

Neil Robertson und Paul Seymour (Satz von Robertson und Seymour) haben gezeigt, dass für jede unendliche Folge G1, G2,... von endlichen Graphen stets Indizes i und j mit i < j existieren, so dass Gi ein Minor von Gj ist.

Siehe auch

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazent — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Ausgangsgrad — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Chromatische Zahl — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Chromatischer Index — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Eingangsgrad — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”