Supergraph

Supergraph

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:

  • Supergraph — In mathematics and physics, the word supergraph has two main meanings:* If A is a subgraph of B , then B is said to be a supergraph of A * In the context of particle physics, a supergraph is a Feynman diagram that calculates scattering amplitudes …   Wikipedia

  • supergraph — noun a) The parent graph that includes a subgraph. b) A Feynman diagram that calculates scattering amplitudes in a supersymmetric theory using the advantages of the superspace formalism …   Wiktionary

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Triangulation (disambiguation) — Triangulation refers to measurement by using triangles. The term triangulation may also refer to:Mathematics and computer science*Subdivisions of spaces into triangles or higher dimensional simplices: **triangulation (advanced geometry), division …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   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

Share the article and excerpts

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