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
- 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
- ^ 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:, ISBN 9781846289699, http://books.google.com/books?id=HuDFMwZOwcsC&lpg=PA267, ”Theorem 10.28”
Externa länkar
- Weisstein, Eric W., "Dualgraf", MathWorld. (engelska)
- Weisstein, Eric W., "Självdual graf", MathWorld. (engelska)