Induzierter Teilgraph

Induzierter Teilgraph

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.

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.

Datei:Forbys_teilgraph_example.png

Minor

Ein Graph G1 wird Minor des Graphen G2 genannt, falls G1 isomorph zu einem durch Knotenverschmelzung entstandenen Untergraphen von G2 ist. Knotenverschmelzung bedeutet hier, dass zwei adjazente (benachbarte) Knoten V1 und V2 unter Entfernung einer zu diesen beiden Knoten inzidenten Kante zu einem Knoten V12 „verschmolzen“ werden, wobei alle restlichen Kanten beibehalten werden.

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

Datei:Forbys_graphs_minor-relation2.png

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

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

  • Lutz Volkmann: Graphen und Digraphen, Springer (Wien) 1991, ISBN 3-211-82267-4.
  • Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0 (elektronische Online-Version)

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • Teilgraph — 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… …   Deutsch Wikipedia

  • Glossar Graphentheorie — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel… …   Deutsch Wikipedia

  • 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

Share the article and excerpts

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