Dualgraf

Den röda grafen är den blå grafens dualgraf, och vice versa.

Inom grafteori är en dualgraf, eller en dual graf, till en planär graf G en graf som har en nod som motsvarar varje "sida" i G och en kant som förbinder dessa noder för varje kant i G. Beteckningen "dual" används eftersom egenskapen är symmetrisk, vilket innebär att om H är dual graf till G, så är G dual till H (om G är sammanhängande). Samma dualitetsbegrepp kan också användas för mer allmänna inbäddningar av grafer i mångfalder.

Det begrepp som beskrivs här är inte detsamma som kantgrafen (nod <-> kant i stället för nod <-> sida) till en graf, och skall inte förväxlas med denna.

Egenskaper

Två (röda) dualgrafer till den planära blå grafen. Notera att de inte är isomorfa eftersom den blå grafen bäddats in i planet på olika sätt. (så har den röda noden "mitt i den blå rektangeln" grad fyra i den översta inbäddningen, men grad fem i den nedersta - eftersom "rektangeln" här bäddats in som en yta med fem kanter).

• Dualgrafen till en plan graf är en plan multigraf - multipla kanter.^[1]
• Om G är en sammanhängande plan graf och G′ är dualgraf till G så är G isomorf med dualgrafen till G′.
• Eftersom dualgrafen beror av inbäddningen så är inte dualgrafen till en planär graf unik på samma sätt som dualgrafen till en plan graf, utan en planär graf kan ha olika icke-isomera dualgrafer. Detta kan ses i figuren där den blå grafen bäddats in i planet på två olika sätt och dualgraferna till dessa olika inbäddningar är icke-isomera (räkna nodernas grad). Dock har Hassler Whitney visat att om grafen är 3-sammanhängande så är inbäddningen, och därmed också dualgrafen, unik.^[2]

På grund av dualiteten kan varje resultat som innefattar räkning av ytor och hörn dualiseras genom att byta dem mot varandra.

Referenser

Externa länkar

• Weisstein, Eric W., "Dualgraf", MathWorld. (engelska)
• Weisstein, Eric W., "Självdual graf", MathWorld. (engelska)