Rovinný 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 . Veta zrejme platí v grafoch bez hrán. Predpokladajme teraz, že platí pre všetky rovinné grafy, ktoré majú menej ako  hrán (indukčný predpoklad). Nech  je rovinný graf s  hranami. Budeme rozlišovať dva prípady:
a) Nech  obsahuje most. Potom po vynechaní mostu sa rozpadne na dva rovinné grafy , . Nech počet vrcholov, hrán a oblastí grafu  je , ,  a grafu  je , , . Pre  a  už (podľa indukčného predpokladu) veta platí. Teda máme , . Ďalej  – počet vrcholov grafu , ,  (vynechaním mostu sa počet oblastí nemení, ale v súčte  sa vonkajšia oblasť započíta dvakrát). Z posledných rovností a z uvedených vzťahov vyššie dostaneme: .
b) Nech  neobsahuje most. Potom zoberme ľubovolnú hranu . Hrana  je obsiahnutá v nejakej kružnici. Zoberme najkratšiu kružnicu , v ktorej je hrana  obsiahnutá. Vnútri kružnice  sa pri vhodnom kreslení diagramu grafu nachádza nejaká oblasť, ktorá vynechaním hrany  zanikne. Teda, ak  má práve o jednu oblasť menej ako . Pritom má ten istý počet vrcholov. Pre  však veta platí, preto platí aj pre . Tým je dôkaz ukončený.

Dôsledok 1

Ak  je rovinný graf, v ktorom všetky oblasti sú ohraničené kružnicami , tak .

Dôsledok 2

Keď  je rovinný graf s  vrcholmi a s maximálnym počtom hrán, tak každá oblasť je  a platí .

Veta

Graf G je planárny práve vtedy, ak neobsahuje podgraf homeomorfný s niektorým z grafov  a .
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  a  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é.

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.

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 do vnú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  hrán.