Lexikon der Mathematik: Unterteilung eines Graphen
entsteht aus einem Graphen durch Unterteilung einiger seiner Kanten.
Dabei spricht man von der Unterteilung der Kante k = xy ∈ K(G) in einem Graphen G, falls man zum Teilgraphen G − k eine neue Ecke v und die beiden neuen Kanten xv und vy hinzufügt. Ein Graph H heißt Unterteilungsgraph von G, wenn man H aus G durch sukzessives Unterteilen von Kanten gewinnt. Einen Graphen H nennt man homöomorph zum Graphen G, wenn H isomorph zu G oder isomorph zu einem Unterteilungsgraphen von G ist. Zwei Graphen H1 und H2 heißen homöomorph, wenn es einen Graphen G gibt, zu dem sowohl H1 als auch H2 homöomorph sind. Homöomorphie von Graphen ist eine Äquivalenzrelation.
Schreiben Sie uns!