Teilgraphen und Minoren

Stichpunkte

Allgemein
	definiert man geeignete Relationen zwischen Graphen und lokalen Gebieten innerhalb dieser Graphen
	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
	die im Folgenden näher definiert werden. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Definitionen 1.1 Teilgraph 1.2 Induzierter Teilgraph 1.3 Beispiele 1.4 Minor [Bearbeiten]
	Besonders wichtig sind dabei Teilgraphenbeziehungen
Definitionen
	[Bearbeiten]
Teilgraph
	also <math>V_1subseteq V_2<math> und in Graphen ohne Mehrfachkanten E1 Teilmenge von E2 ist
	Subgraph oder Untergraph von G2=(V2
	in gerichteten Graphen mit Mehrfachkanten <math>E_1(v)subseteq E_2(v)<math> für alle Teilmengen v aus dem kartesischen Produkt V2xV2 gilt. Umgekehrt heißt G2 Supergraph oder Obergraph von G1
	E1) heißt Teilgraph
	in ungerichteten Graphen mit Mehrfachkanten <math>E_1(v)subseteq E_2(v)<math> für alle zweielementigen Teilmengen v von V2
	<math>E_1subseteq E_2<math>
	gilt
	wobei <math>E_{1/2}(v)<math> die Menge der Kanten zwischen den Knoten aus v ist
	falls V1 Teilmenge von V2
	G1=(V1
	E2)
	also <math>v:={V_2 choose 2}<math>
	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 <math>g_1(v) = g_2(v) mbox{ bzw. } g_1(e) = g2(e)<math>. [Bearbeiten]
Induzierter Teilgraph
	d.h
	Gilt zusätzlich: in Graphen ohne Mehrfachkanten
	<math>E_1 = E_2 cap {V_1 choose 2}<math>
	in gerichteten Graphen mit Mehrfachkanten
	die auch in G2 vorhanden sind. in ungerichteten Graphen mit Mehrfachkanten
	so bezeichnet man G1 auch als den durch V1 induzierten Teilgraph von G2 und notiert diesen auch mit G2[V1] Bemerkungen: Induzierte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt
	G1 enthält alle Kanten zwischen den Knoten in V1
	<math>E_1(v) = E_2(v) cap {V_1 choose 2}<math> für alle zweielementigen Teilmengen v von V2
	<math>E_1(v) = E_2(v) cap {V_1 choose 2}<math> für alle v aus dem kartesischen Produkt V2xV2
	Besonders wichtige Teilgraphen entstehen durch das Weglassen von Knoten bzw
	Kanten
	Sei der Graph G(V
	A subseteq V<math> den Graphen
	der durch Weglassen der Knoten aus A und aller mit diesen Knoten inzidenten Kanten entsteht
	dann bezeichnet <math>Gsetminus A
	E) gegeben
	Die so entstehenden Teilgraphen sind immer induzierte Teilgraphen! [Bearbeiten]
Beispiele
	In der folgenden Abbildung sind die Graphen G1
	G3 Teilgraphen von G
	G2
	wobei aber nur G2 und G3 induzierte Teilgraphen sind
	G3 entsteht dabei aus G durch Weglassen der Knoten 1
	7 und ihrer inzidenten Kanten. [Bearbeiten]
	3
Minor
	falls G1 isomorph zu einem durch Knotenverschmelzung entstandenen Untergraph von G2 ist
	Ein Graph G1 wird Minor des Graphen G2 genannt
	dass zwei adjazente (benachbaarte) Knoten V1 und V2 unter Entfernung einer zu diesen beiden Knoten inzidenten Kante zu einem Knoten V12 „verschmolzen“ werden
	Knotenverschmelzung bedeutet hier
	wobei alle restlichen Kanten beibehalten werden
	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
	dass für jede unendliche Folge G1
	Robertson und Seymour haben gezeigt
	so dass Gi ein Minor von Gj ist
	... von endlichen Graphen stets Indizes i und j mit i < j existieren
	G2
	Satz von Robertson und Seymour
	Siehe auch: Satz von Kuratowski

Dieser Artikel basiert auf dem Artikel Teilgraphen und Minoren aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.