Zobrazenie zdroja stránky Rovinný graf

{{Substovaný infobox}}
{|class="wikitable" align="right"
!colspan="2"|Príklady grafov
|-
! Rovinné
! Nerovinné
|-
| align="center" | [[Súbor:6n-graf.svg|100px]]
| align="center" | [[Súbor:Complete graph K5.svg|100px]] <br /> ''K''<sub>5</sub>
|-
| align="center" | [[Súbor:CGK4PLN.svg|100px]] <br /> [[Kompletný graf]] ''K''<sub>4</sub> 
| align="center" | [[Súbor:Complete bipartite graph K3,3.svg|100px]] <br /> ''K''<sub>3,3</sub>
|}

'''Rovinný graf''' alebo '''planárny graf''' je taký [[Graf (matematika)|graf]] G = (V, H), ktorého [[diagram]] v [[Rovina (geometria)|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 [[Strom (teória grafov)|stromy]] a grafy <math>K_1, K_2, K_3, K_4</math>, 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 <math>h</math>. Veta zrejme platí v grafoch bez hrán. Predpokladajme teraz, že platí pre všetky rovinné grafy, ktoré majú menej ako <math>h</math> hrán (indukčný predpoklad). Nech <math>G</math> je rovinný graf s <math>h</math> hranami. Budeme rozlišovať dva prípady:

a) Nech <math>G</math> obsahuje most. Potom po vynechaní mostu sa rozpadne na dva rovinné grafy <math>G_1</math>, <math>G_2</math>. Nech počet vrcholov, hrán a oblastí grafu <math>G_1</math> je <math>v_1</math>, <math>h_1</math>, <math>s_1</math> a grafu <math>G_2</math> je <math>v_2</math>, <math>h_2</math>, <math>s_2</math>. Pre <math>G_1</math> a <math>G_2</math> už (podľa indukčného predpokladu) veta platí. Teda máme 
<math>h_1 = v_1 + s_1 - 2</math>, <math>h_2 = v_2 + s_2 - 2</math>.
Ďalej <math>v_1 + v_2 = v</math> – počet vrcholov grafu <math>G</math>, <math>h_1 + h_2 = h - 1</math>, <math>s_1 + s_2 = s + 1</math> (vynechaním mostu sa počet oblastí nemení, ale v súčte <math>s_1 + s_2</math> sa vonkajšia oblasť započíta dvakrát). Z posledných rovností a z uvedených vzťahov vyššie dostaneme: <math>h = h_1 + h_2 + 1 = ( v_1 + s_1 - 2 ) + ( v_2 + s_2 - 2) + 1 = (v_1 + v_2) + (s_1 + s_2) - 3 = v + (s + 1) - 3 = v + s - 2</math>.

b) Nech <math>G</math> neobsahuje most. Potom zoberme ľubovolnú hranu <math>h</math>. Hrana <math>h</math> je obsiahnutá v nejakej kružnici. Zoberme najkratšiu kružnicu <math>C</math>, v ktorej je hrana <math>h</math> obsiahnutá. Vnútri kružnice <math>C</math> sa pri vhodnom kreslení diagramu grafu nachádza nejaká oblasť, ktorá vynechaním hrany <math>h</math> zanikne. Teda, ak <math>G'</math> má práve o jednu oblasť menej ako <math>G</math>. Pritom má ten istý počet vrcholov. Pre <math>G'</math> však veta platí, preto platí aj pre <math>G</math>. Tým je dôkaz ukončený.

== Dôsledky Eulerovej vety ==
=== Dôsledok 1 ===
Ak <math>G</math> je rovinný graf, v ktorom všetky oblasti sú ohraničené kružnicami <math>C_n</math>, tak <math>h = \frac{n (v-2)}{n-2}</math>.

=== Dôsledok 2 ===
Keď <math>G</math> je rovinný graf s <math>v \ge 3</math> vrcholmi a s maximálnym počtom hrán, tak každá oblasť je <math>C_3</math> a platí <math>h = 3v - 6</math>.

=== Dôsledok 3 ===
Ak v rovinnom grafe sú všetky oblasti ohraničené kružnicami <math>C_4</math>, tak <math>h = 2v - 4</math>.

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í: 

:|H| − |V| + 2 = r. (Eulerova formula)

Použitím [[cyklomatické číslo|cyklomatického čísla grafu]] môžeme Eulerov vzorec zapísať v tvare:

:r = μ(G) + 1,

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:

:μ(G) = |H| − |V| + p,

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ť <math>[v_0, h_1, v_1, h_2,... v_(n-1), n, v_n], n\in N</math>, kde <math>v_0,.. v_n</math> sú vrcholy grafu <math>(v_0=u, v_n=v), h_1,... h_n</math> sú hrany grafu. Pritom predpokladáme, že každá hrana <math>h_i (i=1,..,n)</math> spája vrcholy <math>v_(i-1) a v_i</math>. Počet hrán v slede sa nazýva dĺžka sledu. Ak <math>u = v</math>, sled nazývame uzavretý, v opačnom prípade otvorený.

Eulerova veta formuluje iba [[nutná podmienka|nutnú podmienku]] pre planaritu grafu, nie [[postačujúca podmienka|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ý graf|homeomorfný]] s niektorým z grafov <math>K_5</math> a <math>K_{3,3}</math>.

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 [[Kazimierz Kuratowski|Kuratowski]].

Grafy <math>G_1</math> a <math>G_2</math> sú homeoformné, ak sú [[izomorfný graf|izomorfné]], alebo konečným počtom [[rozpoľovanie hrán|rozpoľovania hrán]] v týchto grafoch dostaneme také grafy, ktoré budú izomorfné.

=== Tvrdenie (Maximálny počet hrán rovinného grafu) ===
* Nech G = (V, E) je rovinný graf s aspoň 3 vrcholmi. Potom |E|≤ 3|V|-6. Navyše rovnosť nastáva pre každý maximálne rovinný graf; t. j. rovinný graf, ku ktorému nejde pridať žiadnu hranu (pri zachovaní množiny vrcholov) tak, aby zostal rovinným.
* Ak neobsahuje najviac uvažovaný rovinný graf trojuholník (t. j. K3 ako podgraf) a má aspoň 3 vrcholy, potom |E|≤2|V|−4.

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árny graf|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ť:

* '''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 G''' je minimálny počet jeho planárnych podgrafov zjednotením ktorých dostávame graf G
* '''jemnosť grafu G''' je maximálny počet hranovo disjunktných neplanárnych podgrafov grafu G

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ón]]ový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: 
# Všetky jeho strany sú zhodné konvexné mnohouholníky,
# Žiadne jeho steny sa nepretínajú inde ako na hrane,
# Rovnaký počet strán sa dotýka v každom vrchole.

Každý planárny graf môže byť preto označený znakom {p,q} , kde:
* p = počet hrán každej strany (alebo počet vrcholov každej strany),
* q = počet strán stretávajúcich sa v každom vrchole (alebo počet hrán stretávajúcich sa vo vrchole)

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 [[antika|antiky]]. Ich ornamentové modely môžu byť nájdené medzi ozdobnými kamennými guľami vyrobenými v neskorom neolite v [[Škótsko|Škótsku]] najmenej 1000 rokov pred [[Platón]]om. Antickí Gréci rozsiahlo študovali planárne grafy. Niektoré zdroje pripisujú objavenie [[Pytagoras|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čie|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čná sústava|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ú [[elipsa|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 [[Vrchol (teória grafov)|vrcholy]] ležia na hranici jednej oblasti.

=== Veta ===
Silne rovinný v-vrcholový [[Graf (matematika)|graf]] má maximálne <math>2v - 3 </math> hrán.

== Literatúra ==
* Znám, Š: ''Kombinatorika a teória grafov''. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 60 – 61

[[Kategória:Teória grafov]]