Unterteilungsgraph

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

${\displaystyle V'=V\cup \{w\}}$

und der neuen Kantenmenge

${\displaystyle E'=E\setminus \{e\}\cup \{e_{1},e_{2}\}}$,

wobei ${\displaystyle e_{1}=\{u,w\}}$ und ${\displaystyle 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

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.