Direkt zum Inhalt

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 Gk 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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte