Direkt zum Inhalt

Lexikon der Mathematik: dualer Graph

spezieller Graph der folgenden Art. Der duale Graph eines zusammenhängenden Graphen oder Pseudographen G1 ist ein zusammenhängender Graph oder Pseudograph G2, für den eine Bijektion φ : K(G1) → K(G2) zwischen den beiden Kantenmengen existiert so, daß K′ ⊆ K(G1) genau dann die Kantenmenge eines Kreises von G1 ist, wenn G2φ(K′) nicht mehr zusammenhängend ist, wohl aber G2K″ für alle echten Teilmengen K″ von φ(K′).

Ein Graph besitzt genau dann einen dualen (Pseudo-) Graphen, wenn er ein planarer Graph ist. Für einen ebenen Graphen G läßt sich ein dualer (Pseudo-) Graph G′ leicht folgendermaßen konstruieren:

Zunächst plaziert man in jedem Land (ebener Graph) von G genau eine der Ecken von G′. Sind zwei Länder von G benachbart und ihre Ränder enthalten l gemeinsame Kanten, dann verbindet man die beiden in ihnen liegenden Ecken in G′ mit l Kanten, die jeweils eine der Kanten zwischen den beiden Ländern, aber keine weitere Kante von G schneiden. Der so definierte duale (Pseudo-) Graph ist ebenfalls eben.

Bei der Untersuchung von Färbungen von Landkarten ist die Betrachtung dualer Graphen oft nützlich, denn die Landkarte eines ebenen Graphen besitzt genau dann eine Färbung mit k Farben, wenn ihr dualer Graph eine Eckenfärbung mit k Farben besitzt.

Abbildung 1 zum Lexikonartikel dualer Graph
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

G′ ist ein zu G dualer Graph.

Es gilt folgende Aussage: Der duale (Pseudo-) Graph eines dreifach zusammenhängenden Graphen ist eindeutig bestimmt, enthält weder Schlingen noch parallele Kanten, und ist selbst wieder dreifach zusammenhängend.

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

Partnervideos