Rovinný graf

Rovinný graf alebo planárny graf je taký graf G = (V, H), ktorého diagram v rovine možno zostrojiť tak, že dve rôzne hrany majú spoločné nanajvýš krajné vrcholy. Inými slovami: graf je rovinný, ak sa dá nakresliť v rovine tak, že vrcholy sú body roviny, hrany sú oblúky (krivky) a žiadne dve hrany sa nepretínajú.
Medzi rovinné grafy patria všetky stromy a grafy formula_1, teda všetky grafy s počtom vrcholov minimálne jedna a maximálne štyri. Ďalšou charakteristikou je fakt, že Eulerova veta je platná pre akýkoľvek planárny graf.
Eulerova veta.
Eulerova veta: v + s = h + 2; kde "v" – počet vrcholov, "s" – počet oblastí (štátov), "h" – počet hrán (hraníc).
Dôkaz.
Dôkaz Eulerovej vety urobíme indukciou vzhľadom na počet hrán formula_2. Veta zrejme platí v grafoch bez hrán. Predpokladajme teraz, že platí pre všetky rovinné grafy, ktoré majú menej ako formula_2 hrán (indukčný predpoklad). Nech formula_4 je rovinný graf s formula_2 hranami. Budeme rozlišovať dva prípady:
a) Nech formula_4 obsahuje most. Potom po vynechaní mostu sa rozpadne na dva rovinné grafy formula_7, formula_8. Nech počet vrcholov, hrán a oblastí grafu formula_7 je formula_10, formula_11, formula_12 a grafu formula_8 je formula_14, formula_15, formula_16. Pre formula_7 a formula_8 už (podľa indukčného predpokladu) veta platí. Teda máme 
formula_19, formula_20.
Ďalej formula_21 – počet vrcholov grafu formula_4, formula_23, formula_24 (vynechaním mostu sa počet oblastí nemení, ale v súčte formula_25 sa vonkajšia oblasť započíta dvakrát). Z posledných rovností a z uvedených vzťahov vyššie dostaneme: formula_26.
b) Nech formula_4 neobsahuje most. Potom zoberme ľubovolnú hranu formula_2. Hrana formula_2 je obsiahnutá v nejakej kružnici. Zoberme najkratšiu kružnicu formula_30, v ktorej je hrana formula_2 obsiahnutá. Vnútri kružnice formula_30 sa pri vhodnom kreslení diagramu grafu nachádza nejaká oblasť, ktorá vynechaním hrany formula_2 zanikne. Teda, ak formula_34 má práve o jednu oblasť menej ako formula_4. Pritom má ten istý počet vrcholov. Pre formula_34 však veta platí, preto platí aj pre formula_4. Tým je dôkaz ukončený.
Dôsledky Eulerovej vety.
Dôsledok 1.
Ak formula_4 je rovinný graf, v ktorom všetky oblasti sú ohraničené kružnicami formula_39, tak formula_40.
Dôsledok 2.
Keď formula_4 je rovinný graf s formula_42 vrcholmi a s maximálnym počtom hrán, tak každá oblasť je formula_43 a platí formula_44.
Dôsledok 3.
Ak v rovinnom grafe sú všetky oblasti ohraničené kružnicami formula_45, tak formula_46.
Predpokladajme, že máme diagram planárneho grafu, ktorý je nakreslený v zmysle definície, ktorá hovorí o zostrojení diagramu tak, že rôzne hrany majú spoločné nanajvýš krajné vrcholy. Takýto diagram rozdeľuje hranami rovinu na disjunktné oblasti (ak obsahuje aspoň jednu kružnicu) a tie budeme nazývať oblasťami planárneho grafu. Vonkajšia oblasť je tá z oblastí, ktorá je neohraničená.
Nech G = (V,H) je súvislý planárny graf a nech r je počet oblastí grafu G. Potom platí: 
Použitím cyklomatického čísla grafu môžeme Eulerov vzorec zapísať v tvare:
v ktorom má ľahko zrozumiteľnú interpretáciu – počet oblastí planárneho grafu je rovný počtu nezávislých kružníc grafu zväčšenému o 1 (za vonkajšiu oblasť). Cyklomatické číslo grafu G, ktoré nám vlastne udáva minimálny možný počet hrán, odobraním ktorých je možné z grafu odstrániť všetky kružnice, vieme matematicky vyjadriť nasledovne:
kde p je počet komponentov. Komponentom grafu G patriacim k vrcholu v grafu G nazývame súhrn všetkých prvkov grafu G, ktoré patria do niektorej cesty začínajúcej sa vo vrchole v. Každý graf sa skladá z komponentov. Graf s jedným komponentom sa nazýva súvislý. Ak sa v slede neopakuje ani jedna hrana a ani jeden vrchol, nazýva sa cesta. Sledom z vrcholu u do vrcholu v nazývame konečnú postupnosť formula_47, kde formula_48 sú vrcholy grafu formula_49 sú hrany grafu. Pritom predpokladáme, že každá hrana formula_50 spája vrcholy formula_51. Počet hrán v slede sa nazýva dĺžka sledu. Ak formula_52, sled nazývame uzavretý, v opačnom prípade otvorený.
Eulerova veta formuluje iba nutnú podmienku pre planaritu grafu, nie postačujúcu. Vyplýva z nej však viacero dôsledkov použiteľných na charakterizáciu planarity.
Veta.
Graf G je planárny práve vtedy, ak neobsahuje podgraf homeomorfný s niektorým z grafov formula_53 a formula_54.
Táto veta rieši problematiku planárnosti grafov s využitím výhradne kombinatorických prostriedkov (bez kreslenia diagramu grafu). V roku 1930 ju dokázal poľský matematik Kuratowski.
Grafy formula_7 a formula_8 sú homeoformné, ak sú izomorfné, alebo konečným počtom rozpoľovania hrán v týchto grafoch dostaneme také grafy, ktoré budú izomorfné.
Tvrdenie (Maximálny počet hrán rovinného grafu).
V tomto tvrdení nepripúšťame grafy s násobnými hranami.
Neplanárne grafy.
Graf, ktorý nie je planárny, sa nazýva neplanárny. Všeobecne pre neplanárne grafy je možné nakresliť diagram grafu len tak, že niektoré hrany sa krížia v nekoncových bodoch. Pre daný graf G môžeme určiť:
Tieto miery možno nazvať kombinatorickými mierami neplanárnosti grafov. Existuje ešte jedna miera, ktorá má čisto geometrickú interpretáciu: rod grafu – je to 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ú teda rod 0, rod 1 majú grafy, ktorých diagramy môžeme nakresliť na anuloid (“pneumatiku”).
Príklady pre neplanarne grafy.
Príkladom sú už uvedené grafy K5, K3, 3. Uvedené grafy predstavujú zároveň minimálne neplanárne grafy: K5 má najmenší počet vrcholov (5) a K 3,3 má najmenší počet hrán (9). Ukazuje sa, že tieto dva grafy hrajú veľmi významnú úlohu v súvislosti s planaritou grafov.
Kuratowského veta.
Graf G je rovinný práve vtedy, ak nie je žiadny jeho podgraf izomorfným delením grafu K5 ani K3,3. K5 označuje úplný graf na piatich vrcholoch; K3,3 je úplný bipartitný graf.
Mnohosteny (Platónske telesá).
Antická škola mysliteľov spájaná s Platónovým menom sa zaoberala pravidelnými geometrickými útvarmi, takzvané pravidelné mnohosteny, a hľadala ich v základoch stavby vesmíru. Pravidelný mnohosten je trojrozmerné teleso, ohraničené konečným počtom stien – rovnakých pravidelný mnohouholníkov, kde sa v každom vrchole spája rovnaký počet stien (strán) a hrán.
Konvexný mnohosten je planárnymi grafom ak: 
Každý planárny graf môže byť preto označený znakom {p,q} , kde:
Znak {p,q} sa nazýva Schälfiho znak, dáva kombinatoricky popis mnohostena. 
História planárnych (rovinných) grafov.
Planárne grafy sú známe už od antiky. Ich ornamentové modely môžu byť nájdené medzi ozdobnými kamennými guľami vyrobenými v neskorom neolite v Škótsku najmenej 1000 rokov pred Platónom. Antickí Gréci rozsiahlo študovali planárne grafy. Niektoré zdroje pripisujú objavenie Pytagorovi. Iné hovoria o tom, že bol iba oboznámený so štvorstenom, kockou a 12-stenom a že objavenie osemstena a 20-stena patri Theaetetovi, jednému z Platónových žiakov. Theaetetus dal matematický popis všetkým piatim útvarom a je zodpovedný za prvý známy dôkaz, že nie sú žiadne iné vypuklé pravidelné mnohosteny. Euklides dal kompletný matematický popis planárnych grafov v "Elementoch", poslednej knihe, ktorá bola zasvätená ich vlastnostiam. V knihe popisuje zostrojenie štvorstena, kocky, osemstena, dvanásťstena a dvadsať stena. Pre každý útvar Euklides našiel pomer priemeru opísanej guľe k dĺžke hrany. Taktiež tvrdil, že nie je viac vypuklých pravidelných mnohostenov.
V 16. storočí sa nemecký astronóm Johannes Kepler pokúsil nájsť závislosť medzi vtedy známymi planétami a piatimi planárnymi grafmi. V 1596 predložil model slnečnej sústavy, v ktorej týchto 5 grafov bolo posadených dovnútra ďalšieho a oddelených sériou vpísaných a ohraničených oblastí. 6 oblastí, pričom každá z nich súhlasila s jednou z planét (Merkúr, Venuša, Zem, Mars, Jupiter a Saturn). Grafy boli zoradené od najvnútornejšieho osemstena, nasledoval dvadsaťsten, dvanásťsten, štvorsten a nakoniec kocka. Týmto spôsobom štruktúra slnečnej sústavy a vzťah medzi vzdialenosťami planét boli určené planárnymi grafmi. Nakoniec od Keplerovho originálneho nápadu muselo byt upustené, ale jeho výskum dospel k tomu, že obežné dráhy planét sú elipsy, taktiež jeho dva zákony orbitálnej dynamiky ovplyvnili fyziku a astronómiu, plus objavil Keplerove grafy.
Silne rovinný graf.
Rovinný graf sa nazýva silne rovinný ak ho možno v rovine nakresliť tak, že všetky vrcholy ležia na hranici jednej oblasti.
Veta.
Silne rovinný v-vrcholový graf má maximálne formula_57 hrán.