Teilgraphen und Minoren

Inhaltsverzeichnis

1 Einleitung 2 Definitionen 2.1 Teilgraph 2.2 Induzierter Teilgraph 2.3 Beispiele 2.4 Minor

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

• in Graphen ohne Mehrfachkanten E ₁ Teilmenge von E ₂ ist <math>E_1\subseteq E_2</math>
• in ungerichteten Graphen mit Mehrfachkanten <math>E_1(v)\subseteq E_2(v)</math> für alle zweielementigen Teilmengen v von V ₂ also
  <math>v:={V_2 \choose 2}</math>
  gilt wobei <math>E_{1/2}(v)</math> die Menge der zwischen den Knoten aus v ist
• in gerichteten Graphen mit Mehrfachkanten <math>E_1(v)\subseteq E_2(v)</math> für alle Teilmengen v aus dem kartesischen Produkt V ₂ x V ₂ gilt.

Umgekehrt heißt G ₂ Supergraph oder Obergraph von G ₁ .

Bei einem knotengewichteten bzw. kantengewichteten Graph G ₂ wird von einem Teilgraph G ₁ zudem verlangt dass die Gewichtsfunktion g ₁ von G ₁ kompatibel zu der Gewichtsfunktion g ₂ von G ₂ ist d.h. für jeden Knoten v bzw. für jede Kante e von G ₂ gilt <math>g_1(v) = g_2(v) \mbox{ bzw. g_1(e) = g2(e)</math>.

Induzierter Teilgraph

• in Graphen ohne Mehrfachkanten
  <math>E_1 = E_2 \cap {V_1 \choose 2}</math>
  d.h. G ₁ enthält alle Kanten zwischen den Knoten V ₁ die auch in G ₂ 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 ₂
• 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 ₂ x V ₂

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

Minor

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 ₁ G ₂ ... 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.