Teória grafov a terminológia

Začiatky teórie
grafov môžeme hľadať u L. Eulera (1707-1783). Roku 1736 sa zaoberalúlohou prejsť všetkých 7 mostov v Kaliningrade bez toho, aby išiel 1 mostomdvakrát. Euler túto úlohu previedol na úlohu nakresliť obrázok jedným ťahom apomocou toho dokázal jej neriešiteľnosť. Súčasne dal všeobecný návod, akoriešiť úlohu podobného typu. Vmatematike i mimo nej sa často stretávame s objektmi, ktoré sú istým spôsobompospájané pomocou iných objektov. Napríklad vrcholy mnohostena pospájané hranami,atómy prvkov pospájané väzbami, dopravné uzly pospájané cestami alebo ľudiapospájaní vzájomnými vzťahmi. Tieto príklady vedú k
nasledovným definíciam: Grafom nazývame množinu skladajúcu sa z prvkov dvojakého druhu: prvé z nich nazývamevrcholy, ktoré sú pospájané prvkami druhého druhu, ktoré nazývame hrany. Hrana,ktorá vychádza aj vchádza do jedného vrcholu, sa nazýva slučka. Ak hrana hspája vrcholy u a v, hovoríme, že je s týmito
vrcholmi incidentná. Ak mániekoľko hrán spoločné konce, nazývajú sa násobné. Grafy s konečným počtomvrcholov a hrán nazývame konečné. Tie sa dajú znázorniť do roviny napríkladkrúžkami a čiarami. Takétoznázornenie sa nazýva diagram grafu. Počet hrán incidujúcich s istým vrcholomnazývame stupňom toho vrcholu.

Vrcholy
0. stupňa sa nazývajú izolované. Ak majú všetky vrcholy grafurovnaký stupeň, graf sa nazýva pravidelným grafom n-tého stupňa. Graf sa nazývakompletný alebo úplny, ak neobsahuje slučky a každé dva vrcholy toho grafu súspojené práve jednou hranou. Grafy G a G´ sa nazývajú izomorfné, ak vrcholygrafu G môžeme bijektívne priradiť vrcholom grafu

G´ tak, aby dva prvky grafu Gboli incidentné práve vtedy, keď sú incidentné im zodpovedajúce prvky grafu G´.Izomorfné grafy spravidla nepokladáme za rôzne. Grafy G a G´ sa nazývajúhomeomorfné, keď sú buď izomorfné, alebo keď voľbou nových vrcholov 2.stupňa nahranách grafoch G a G´ môžeme z nich vytvoriť izomorfné grafy. Graf je rovinný,keď existuje jeho diagram, v ktorom sa nepretínajú nijaké dve úsečky (oblúky).Kuratowského veta(1930): Konečný graf je rovinný práve vtedy, keď neobsahujepodgrafy homeomorfné s grafmi, ktorých diagramy sú na obrázkoch 3 a 4(vstrede šesťuholníka nieje vrchol).Sledom zvrcholu u do
vrcholu v nazývame konečnú postupnosť [v­0,h­1,v1,h2,...vn-1,hn,vn­­­],n N, kde v0,..vn sú vrcholy grafu (v0=u,vn=v),h1,...hn sú hrany grafu. Pritom predpokladáme, že každáhrana hi (i=1,..,n) spája vrcholy vi-1 a vi.Počet hrán v slede sa nazýva dĺžka sledu. Ak u=v, sled nazývame uzavretý, vopačnom prípade otvorený. Ak sa v slede ani jedna hrana neopakuje, slednazývame ťah. Ak sa v ňom neopakujú ani vrcholy, nazýva sa cesta. Komponentomgrafu 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ý. Rez grafu sa nazývamnožina prvkov súvisleho grafu, po odstránení ktorých sa graf rozpadne na dvakomponenty a žiadna podmnožina rezu nemá túto vlastnosť. Odstránenie vrcholu zgrafu automaticky odstráni aj hrany s ním incidentné. Ak je rez vrchol, nazývasa artikulácia, ak je to hrana, nazýva sa most. Kružnica je uzavretý ťahnenulovej dĺžky, v ktorom sa neopakujú vrcholy s výnimkou začiatočného.Kružnica s n vrcholmi sa nazýva aj n-uholník.

Kružnica obsahujúca všetkyvrcholy grafu sa nazýva hamiltonovská. Ťah, ktorý obsahuje všetky hrany grafusa nazýva eulerovský. Uzavretý eulerovský ťah v grafe G existuje práve vtedy,keď G je súvislý a všetky jeho vrcholy sú párneho stupňa. Ak má G práve dvanepárne vrcholy, obsahuje otvorený eulerovský ťah. Graf neobsahujúci kružnicuje les, ak je súvislý – strom. Strom, ktorý obsahuje všetky vrcholy grafu sanazýva kostra grafu.