Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 15. Oktober 2019 

Teilgraphen und Minoren


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

Einleitung

Bei der Untersuchung von Grapheneigenschaften schließt häufiger von lokalen auf globale Eigenschaften von und umgekehrt. Um derartige Vorgänge besser beschreiben können definiert man geeignete Relationen zwischen Graphen lokalen Gebieten innerhalb dieser Graphen. Besonders wichtig dabei Teilgraphenbeziehungen die im folgenden näher definiert

Definitionen

Teilgraph

G 1 =( V 1 E 1 ) heißt Teilgraph Subgraph oder Untergraph von G 2 =( V 2 E 2 ) falls V 1 Teilmenge von V 2 also <math>V_1\subseteq V_2</math> 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 <math>g_1(v) = g_2(v) \mbox{ bzw. g_1(e) = g2(e)</math>.

Induzierter Teilgraph

Gilt zusätzlich:
  • in Graphen ohne Mehrfachkanten
    <math>E_1 = E_2 \cap {V_1 \choose 2}</math>
    d.h. G 1 enthält alle Kanten zwischen den Knoten V 1 die auch in G 2 vorhanden sind.
  • in ungerichteten Graphen mit Mehrfachkanten
    <math>E_1(v) = E_2(v) \cap {V_1 \choose 2}</math>
    für alle zweielementigen Teilmengen v von V 2
  • in gerichteten Graphen mit Mehrfachkanten
    <math>E_1(v) = E_2(v) \cap {V_1 \choose 2}</math>
    für alle v aus dem kartesischen Produkt V 2 x V 2
so bezeichnet man G 1 auch als den durch V 1 induzierten Teilgraph von G 2 und notiert diesen auch mit G 2 [ V 1 ]

Bemerkungen:

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

Beispiele

In der folgenden Abbildung sind die 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.

Minor

Ein Graph G 1 wird Minor des Graphen G 2 genannt falls G 1 isomorph zu einem durch Knotenverschmelzung enstandenen Untergraph von G 2 ist. Knotenverschmelzung bedeutet hier dass zwei adjazente (benachbaarte) V 1 und V 2 unter Entfernung einer zu diesen beiden inzidenten Kante zu einem Knoten V 12 „verschmolzen“ werden wobei alle restlichen Kanten werden.

Zum Beispiel ist in der folgenden G 1 ein Minor von G 2.

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

Robertson und Seymour haben gezeigt dass jede unendliche Folge G 1 G 2 ... von endlichen Graphen stets Indizes i und j mit i < j existieren so dass G i ein Minor von G j ist.

Siehe auch: Satz von Kuratowski Satz von Robertson und Seymour



Bücher zum Thema Teilgraphen und Minoren

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Teilgraphen_und_Minoren.html">Teilgraphen und Minoren </a>