Planär graf
From Wikipedia, the free encyclopedia
Inom grafteori är en planär graf en graf som kan bäddas in i planet, det vill säga ritas på planet på ett sådant sätt att kanterna inte skär varandra, utan bara möts i noderna.[1] En sådan avbildning kallas en plan graf eller planär inbäddning av grafen. En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en plan kurva i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna.
Exempel | |
---|---|
Planär | Icke planär |
Fjärilsgraf |
Den kompletta grafen K5 |
Den kompletta grafen K4 |
Den bipartita grafen K3,3 |
Varje graf som kan avbildas på ett plan kan avbildas på en sfär och vice versa.
En generalisering av planära grafer är grafer som kan ritas på en yta av ett givet genus. Med denna terminologi har planära grafer grafgenus 0, eftersom planet (och sfären) har genus 0.