Síkbarajzolható gráf
olyan gráf, amit le lehet rajzolni egy síkra anélkül, hogy az élei (a csúcsokon kívül) metszenék egymást / From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén egy síkbarajzolható gráf olyan gráf, melynek létezik a síkba való beágyazása, tehát lerajzolható úgy a síkon, hogy élei kizárólag a csúcspontokban találkoznak (metszési száma 0), vagy más megfogalmazásban, lerajzolható a síkban anélkül, hogy élei metszenék egymást.[1]
Példagráfok | |
---|---|
Síkbarajzolható | Síkba nem rajzolható |
Pillangógráf |
K5 Teljes gráf |
K4 Teljes gráf |
K3,3 Három ház–három kút-gráf |
A gráf ilyen lerajzolása a síkgráf (plane graph), avagy a gráf síkra rajzolása, síkba ágyazása (planar embedding of the graph). Egy síkgráf meghatározható úgy is, hogy egy síkbarajzolható gráf minden csúcsához hozzárendeljük a sík egy pontját, minden éléhez pedig olyan síkgörbét, melynek végpontjai az él két csúcsához rendelt síkbeli pontok, és a síkgráfhoz tartozó görbék a végpontjaiktól eltekintve diszjunktak. Néha síkbarajzolható gráf helyett is a síkgráf kifejezést használják.
Sztereografikus projekcióval igazolható, hogy egy gráf akkor és csak akkor síkbarajzolható, ha gömbre rajzolható. A Fáry–Wagner-tétel szerint egy síkba rajzolható egyszerű gráf úgy is síkba rajzolható, hogy élei egyenes szakaszok.
A síkgráfok kombinatorikus térképekkel is reprezentálhatóak.
A topologikusan ekvivalens gömbre rajzolások ekvivalenciaosztályát síktérképnek (planar map) nevezik. Bár egy síkgráf rendelkezik külső vagy nem korlátos tartománnyal, a síktérkép egyik tartományának sincs megkülönböztetett státusza.
A síkbarajzolható gráfok általánosítása az adott génuszú (nemszámú) felületre rajzolható gráfok. Ezen terminológia szerint a síkba rajzolható gráfok nemszáma 0, mivel a sík (és a gömb) 0 nemszámú felületek. Lásd még: gráf beágyazása.