Unterteilungsgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Unterteilungsgraph des vollständigen Graphen K5, der durch Unterteilung aller Kanten entsteht

Ein Unterteilungsgraph ist in der Graphentheorie ein Graph, der durch Kantenunterteilung aus einem anderen Graph entstanden ist. Zwei Graphen heißen homöomorph, falls sie Unterteilungsgraphen besitzen, die isomorph sind. Unterteilungsgraphen spielen unter anderem im Satz von Kuratowski und in der Hajós-Vermutung eine wichtige Rolle.

Definitionen[Bearbeiten]

Unterteilungsgraph[Bearbeiten]

Graph subdivision step1.svg
Graph subdivision step2.svg
Kante vor und nach Unterteilung

Sei G=(V,E) ein ungerichteter Graph, dann versteht man unter einer Unterteilung einer Kante e=\{u, v\} \in E die Ersetzung dieser Kante durch zwei neue Kanten e_1 und e_2, die die beiden Knoten u und v der entfernten Kante mit einem neuen Knoten w \notin V verbinden. Auf diese Weise entsteht ein neuer Graph G' = (V', E') mit der neuen Knotenmenge

V'=V \cup \{ w \}

und der neuen Kantenmenge

E' = E \setminus \{ e \} \cup \{ e_1, e_2 \},

wobei e_1=\{ u, w \} und e_2=\{ w, v \} sind. Ein Unterteilungsgraph eines Graphen ist nun ein Graph, der aus diesem durch (null-, ein- oder mehrmalige) Kantenunterteilung entsteht.

Homöomorphie von Graphen[Bearbeiten]

Zwei Graphen heißen homöomorph, falls Unterteilungsgraphen dieser beiden Graphen existieren, die zueinander isomorph sind. Als den Homöomorphie-Ursprung eines Graphen bezeichnet man den kleinsten Graph, der zu diesem homöomorph ist. Man kann den Homöomorphie-Ursprung eines Graphen durch wiederholtes Entfernen von Knoten vom Grad zwei (Schleifen ausgenommen) und Einfügen einer Kante, die die beiden Nachbarknoten des entfernten Knoten verbindet, ermitteln. Zwei Graphen sind nun genau dann homöomorph, wenn ihre Homöomorphie-Ursprünge isomorph sind.

Beispiele[Bearbeiten]

Die folgenden beiden Graphen A und B sind homöomorph, da sie den gemeinsamen Unterteilungsgraphen C besitzen. Der Homöomorphie-Ursprung der beiden Graphen ist der Graph D.

Auch alle Kreisgraphen C_n sind für n \geq 2 zueinander homöomorph mit dem Graphen C_2 als Homöomorphie-Ursprung.

Verwendung[Bearbeiten]

Unterteilungsgraphen spielen eine wichtige Rolle im Satz von Kuratowski. Nach diesem Satz ist ein endlicher Graph genau dann planar, wenn er keinen Teilgraphen enthält, der durch Unterteilung des vollständigen Graphen K_5 oder des vollständig bipartiten Graphen K_{3,3} entstanden ist. Des Weiteren dienen sie auch zur Definition von topologischen Minoren.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]