Neplanárny graf
Neplanárny graf alebo nerovinný graf je graf, ktorý nie je rovinný graf.
Pre neplanárny graf možno nakresliť diagram grafu len tak, že niektoré hrany sa krížia v nekoncových bodoch.
Miery neplanárnosti grafu
[upraviť | upraviť zdroj]Pre každý graf G možno určiť nesledujúce miery neplanárnosti grafu
- priesečníkové číslo grafu
- hrúbku grafu
- jemnosť grafu
- rod grafu
Priesečníkové číslo grafu
[upraviť | upraviť zdroj]Priesečníkové číslo grafu G je minimálny počet dvojíc hrán, ktoré sa krížia (pretínajú) pri ľubovoľnom nakreslení diagramu grafu G.
Hrúbka grafu
[upraviť | upraviť zdroj]Hrúbka grafu G je minimálny počet jeho planárnych podgrafov zjednotením ktorých dostávame graf G.
Jemnosť grafu
[upraviť | upraviť zdroj]Jemnosť grafu G je maximálny počet hranovo disjunktných neplanárnych podgrafov grafu G
Tieto miery sú kombinatorické miery neplanárnosti grafov. Existuje ešte jedna miera, ktorá má čisto geometrickú interpretáciu.
Rod grafu
[upraviť | upraviť zdroj]Rod grafu je minimálny počet premostení, ktoré treba pridať ku guli, aby sa na jej povrchu dal nakresliť diagram príslušného grafu bez pretínania sa hrán. Planárne grafy majú rod 0, rod 1 majú grafy, ktorých diagramy môžeme nakresliť na anuloid (“pneumatiku”).