Lexikon der Mathematik: dualer Graph
spezieller Graph der folgenden Art. Der duale Graph eines zusammenhängenden Graphen oder PseudographenG1 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 G2 − K″ 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 GraphenG 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.
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.
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.