Dualgraf

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 redigera

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 redigera

^ Här tar vi i beaktande att grafer kan ha loopar och multipla kanter för att slippa diverse hänsynstaganden.
^ Bondy, Adrian; Murty, U.S.R. (2008), ”Planar Graphs”, Graph Theory, Graduate Texts in Mathematics, "244", Springer, s. 267, doi:10.1007/978-1-84628-970-5, ISBN 9781846289699, http://books.google.com/books?id=HuDFMwZOwcsC&lpg=PA267, ”Theorem 10.28”

Externa länkar redigera

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

[1] Här tar vi i beaktande att grafer kan ha loopar och multipla kanter för att slippa diverse hänsynstaganden.

[2] Bondy, Adrian; Murty, U.S.R. (2008), ”Planar Graphs”, Graph Theory, Graduate Texts in Mathematics, "244", Springer, s. 267, doi:10.1007/978-1-84628-970-5, ISBN 9781846289699, http://books.google.com/books?id=HuDFMwZOwcsC&lpg=PA267, ”Theorem 10.28”

[1]

[2]