Neplanárny graf

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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ť kód]

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ť kód]

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ť kód]

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ť kód]

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ť kód]

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”).