Teilgraphen und Minoren
Table of contents |
2 Definitionen |
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 im Folgenden näher definiert werden.
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
.
Bemerkungen:
Zum Beispiel ist in der folgenden Abbildung G1 ein Minor von G2.
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: Satz von Kuratowski, Satz von Robertson und SeymourEinleitung
Definitionen
Teilgraph
G1=(V1,E1) heißt Teilgraph, Subgraph oder Untergraph von G2=(V2,E2), falls V1 Teilmenge von V2, also und
Umgekehrt heißt G2 Supergraph oder Obergraph von G1.Induzierter Teilgraph
Gilt zusätzlich:
so bezeichnet man G1 auch als den durch V1 induzierten Teilgraph von G2 und notiert diesen auch mit G2[V1]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.Minor
Ein Graph G1 wird Minor des Graphen G2 genannt, falls G1 isomorph zu einem durch Knotenverschmelzung entstandenen Untergraph von G2 ist. Knotenverschmelzung bedeutet hier, dass zwei adjazente (benachbaarte) 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.