Lexikon der Mathematik: Einbettung eines Graphen
Zuordnung eines Graphen zu einem topologischen Raum.
Eine Einbettung des Graphen G in einen topologischen Raum X ordnet jeder Ecke v von G einen Punkt v′ in X und jeder Kante k von G einen Bogen k′ in X, d. h. das Bild einer stetigen injektiven Abbildung von [0, 1] in X, so zu, daß folgende Bedingungen erfüllt sind:
Die Elemente der Mengen E′ = {v′|v ∈ E(G)} und K′ = {k′| k ∈ K(G)} heißen Ecken und Kanten der Einbettung und definieren in natürlicher Weise einen zu G isomorphen Graphen G′ in X, der selbst oft als Einbettung von G bezeichnet wird.
Ein Schnittpunkt in X \ E′ zweier Kanten der Einbettung heißt eine Kreuzung (engl. crossing). Eine Einbettung heißt kreuzungsfrei, falls sie keine Kreuzung besitzt. In einer kreuzungsfreien Einbettung schneiden sich also Kanten höchstens in Ecken.
Eine Einbettung heißt normal, falls je zwei Kanten höchstens einen Schnittpunkt besitzen und keine drei Kanten sich in einer Kreuzung schneiden. In einer normalen Einbettung schneiden sich also zwei Kanten nur entweder in höchstens einer Ecke oder in höchstens einer Kreuzung.
Von den drei dargestellten Einbettungen des Graphen K4 in die Ebene ℝ2 ist die linke normal, die mittlere kreuzungsfrei und die rechte weder normal noch kreuzungsfrei.
Wählt man für X den ℝ3, für die Ecken Punkte der Form (t, t2, t3) für t ∈ ℝ und für die Kanten die geraden Strecken zwischen den jeweiligen Ecken, so sieht man leicht, daß jeder Graph eine kreuzungsfreie Einbettung in den ℝ3 besitzt. Üblicherweise werden daher vornehmlich kreuzungsfreie Einbettungen in zweidimensionale Mannigfaltigkeiten und insbesondere die Ebene ℝ2, oder orientierbare und nicht-orientierbare Flächen beliebigen Geschlechts betrachtet.
Man vergleiche auch das Stichwort Einbettungsalgorithmus.
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.