Grafy

Pojmy

Grafická reprezentácia grafu

Graf môžeme znázorniť pomocou množiny bodov v rovine - znázornené ako kružnice - pospájaných úsečkami.

Orientovaný graf

Graf H nazveme neorientovaný práve vtedy keď, pre všetky [x,y] z H plati: [y,x] je tiež z R inak ho nazývame orientovaný. Orientovaný graf zakresľujeme pomocou orientovaných úsečiek.

Cesta z vrcholu a₁ do vrcholu b₁

Hovoríme, že v grafe H existuje cesta z a1 do b1 práve vtedy keď, existuje postupnosť hrán z H: h1=[a₁,a₂], h2=[a₂,a₃], h3=[a₃,a₄] , ...hn=[a_n,b₁]

Súvislý graf

Graf H nazveme súvislý práve vtedy keď, sa z každého vrcholu existuje cesta do každého vrcholu grafu.

Stupeň vrchola

Počet hrán vychádzajúcich z vrchola nazývame stupeň vrchola

Kružnica

Neorientovaný súvislý graf nazveme kružnicou práve vtedy, keď stupeň každého vrcholu grafu je 2.

Kostra

Súvislý graf, ktorý neobsahuje kružnicu nazývame kostra grafu.
Z každého súvislého grafu možno vybrať kostru - vynechaním niekoľkých hrán

Ohodnotený graf

Nech hrana grafu je trojica [a1,a2,r], kde a1,a2 patrí do A a r je kladné reálne číslo.

Takto určený graf nazývame ohodnotený graf a číslo r nazývame hodnota hrany.

Minimálna kostra

Minimálnou kostrou grafu bude kostra grafu s najmenším súčtom hodnôt hrán.

Reprezentácia grafu v počítači

Údaje na disku

Najčastejšie býva nasledovná štruktúra:

pu	pocet uzlov
x1 y1	súradnice prvého uzla	slúži len na vykreslenie grafu
x2 y2	súradnice druhého uzla
...	...
xpu ypu	súradnice posledného uzla
ph	počet hrán
a1 b1 r1	ČísloUzlaOdkade ČísloUzlaKam Hodnota	vrcholy sú určené poradovými číslami zo zoznamu vrcholou
a2 b2 r2
...
aph bph rph

Prvý stĺpec tabuľky určuje čísla v textovom súbore

Pr.
12
25 100
50 75
125 75
115 65
135 65
160 100
135 125
150 140
120 140
50 125
65 140
35 140
13
1 2 1
2 3 2
3 4 4
3 5 1
3 6 2
6 7 4
3 7 1
7 8 2
7 9 4
1 10 1
10 11 2
10 12 4
2 12 2

Načítajte a vykreslite tento graf.

Hľadanie minimálnej kostry

Je zrejmé, že ku každému grafu možno nájsť minimálne jeden podgraf, ktorý je kostrou. Dá sa pomerne ľahko dokázať, že na hľadanie minimálnej kostry možno použiť nasledovné intuitívne postupy:

1. Z grafu budeme vynechávať hrany s najväčším ohodnotením ale len tie, ktorých vynechaním sa neporuší súvislosť. Keď sa už žiadna hrana nedá vynechať je tvorba min. kostry ukončená.
2. Zoradíme si hrany grafu vzostupne. Prejdeme cyklom tento zoradený zoznam a pri každej hrane rozhodneme, či ju berieme do nového grafu - kostry. Hranu zoberieme ak nevytvára s už vybranými kružnicu.
3. Táto metóda je modifikáciou 2. metódy. Do kostry vyberieme minimálnu hranu grafu. Zo všetkých hrán grafu, ktoré majú vlastnosť, že jeden vrchol majú už vo vytváranej kostre a druhý nie, nájdem minimálnu a pridám do kostry. Postup opakujem pokiaľ nie sú všetky uzly už v kostre zahrnuté. Tento postup sa dá použiť len na súvislé grafy.

Ďalej sa budeme venovať len postupu 3.
Nech v pu je zapísaný počet uzlov
Majme vytvorenú maticu susednosti Graf[1..pu,1..pu] celých čísel
Kostru vytvárajme v matici susednosti Kostra[1..pu, 1..pu]
Či je vrchol už v kostre bude v poli Kuzly[1..pu] 0=uzol nie je v kostre, 1=uzol je v kostre
Celý algoritmus možno schématicky zapísať takto:

• Nájdi minimálnu hranu a zapíš ju do kostry
• Oba vrcholy označ 1 - sú v kostre
• Opakuj (pu-2) krát
  • nájdi minimálnu hranu s jedným vrcholom v kostre
  • pridaj ju do kostry
  • oba vrcholy oznac jednotkou - sú v kostre

Úloha

Pre graf daný textovým súborom vytvor kostru a vykresli ju inou farbou cez graf.

Test súvislosti grafu

V praxi sa často stretávame s úlohou zistiť, či graf je súvislý. Tu sa obmedzíme len na neorientované grafy, ale postup možno aplikovať aj na orientované. Pre neorientované grafy platí: Graf je súvislý <=> keď sa z uzla 1 dá dostať do všetkých ostatných grafov. Postup ako prešetríme, či existuje cesta z uzla 1 do všetkých ostatných.
Budeme k tomu potrebovať
maticu susednosti Graf[1..pu,1..pu]
pole Pom[1..pu], kde každá položka môže byť

0. na uzol so ešte nenarazil
1. do uzla vedie nejaká cesta, ale ešte treba vybaviť jeho susedov
2. do uzla vedie cesta a aj jeho susedov som už vybavil

Pole Zoznam[1..pu], kde budú za sebou napísané tie uzly, ktoré majú v Pom čislo 1.
Premenná pocet1, kde budem mať zapísaný počet uzlov, ktoré majú v Pom číslo 1.
Inicializačné hodnoty v poli Pom budú všade 0, len v položke 1 bude 1.
Inicializačné hodnoty v poli Zoznam budú v položke 1 bude zapísaná 1, iné nás nezaujíma
Inicializačná hodnota v premennej Pocet1 bude 1

Opakuj pokiaľ Pocet1>0

• Uzol Zoznam[Pocet1] vyhodíme zo zoznamu - tak, že Pocet1 zmenšíme o 1 a tomuto uzlu v Pom zapíšeme 2
• Namiesto vyhodeného uzla do zoznamu pripíšeme priamych susedov tohto uzla (z matice susednosti), ktorí v Pom majú zatiaľ 0. Všetkým došlým uzlom v Pom zapíšeme 1.

Nakoniec skontrolujeme pole Pom či v ňom ostali ešte nejaké nuly, ak nie je graf súvislý.
V prípade ak sme natenko s pamäťou môžme pole Zoznam vynechať, ale zaplatíme väčším časom výpočtu, musíme v poli Pom tých jednotkárov hľadať .

Zistenie minimálnej cesty v grafe

Táto úloha zo všetkých tých, ktoré sme doteraz spomínali, má v praxi najväčšie praktické využitie.
Máme dané:
maticu susednosti Graf[1..pu,1..pu]
štartový uzol cesty Uzol1 a konečný uzol cesty Uzol2
Existuje veľa metód na hľadanie minimálnej cesty ale ku najrýchlejším metódam patrí tkz. Dijkstrov algoritmus, ktorý si teraz povieme.
Budeme ešte potrebovať:
pole Pom[1..pu], kde každá položka môže byť

0. na uzol so ešte nenarazil
1. do uzla vedie nejaká cesta, ale ešte neviem, či je minimálna
2. údaj, ktorý je v poli dĺžka u tohto uzla je definitívny - minimálny

pole Dlzka[1..pu] kde bude pre každý uzol zapísaná zatiaľ nájdená minimálna cesta z uzla Uzol1
pole Odkade[1..pu], kde bude zapísané z ktorého uzla som sem prišiel pri tejto nájdenej dĺžke cesty.
Inicializačné hodnoty v poli Pom budú všade 0, len v položke Uzol1 bude 1.
Inicializačné hodnoty v poli Dĺžka budú všade "nekonečno" len v riadku Uzol1 bude 1
Opakuj pokiaľ v Pom v riadku Uzol2 je číslo rôzne od 2

• nájdi zo všetkých jednotkových uzlov ten ktorý má najmenšiu vzdialenosť od Uzol1 - U1. Tento zmeníme na d
• Tento zmeníme na dvojkový a všetkých jeho nedvojkových susedov označíme za jednotkových a upravíme im dĺžky - vzdialenosti - Dlzka[u]:=min(Dlzka[u],dlzka[U1]+vzd(u,U1)). Ak sa uzlu mení jeho dĺžka zapíšeme do poľa Odkade v riadku toho uzla uzol U1

Je jasné, že v každom behu cyklu pribúda jedna dvojka. Program môže skončiť tým, že v Pom[Uzol2] sa objaví 2 alebo sa "minú" jednotky v poli Pom, čo značí, že neexistuje cesta z Uzol1 do Uzol2. Týmto sme vytvorili vzdialenosti uzlov od UZOL1. Navyše v každom uzle vieme ako sme sa doňho dostali - pomocou poľa Odkade. Teraz môžme začať cestu "odzadu" vypisovať Uzol2,...Uzol1.
Pre neorientované grafy je teda výhodné hľadať radšej cestu opačnú - z Uzol2 do Uzol1 aby sme ju potom vypisovali pekne odpredu.

Kreslenie jedným ťahom

Tento problém sa tiež volá problém cestujúceho, ktorý chce prejsť všetky trasy grafu ale práve raz. Určite ste sa stretli s problémom, nakresliť nasledovný domček jedným ťahom.
Najprv niekoľko tvrdení:

• Každý graf má párny počet vrcholov s nepárnym stupňom
• Graf sa dá nakresliť jedným ťahom <=> počet vrcholov s nepárnym stupňom je maximálne 2
• Ak graf nemá vrcholy s nepárnym stupňom môžeme začať v ľubovoľnom vrchole a ľubovoľnou hranou
• Ak graf nemá vrcholy s nepárnym stupňom kreslenie skončí vždy v tom istom uzle z ktorého sme začali kreslenie
• Ak graf má vrcholy s nepárnym stupňom, musíme kreslenie začať vo vrchole s nepárnym stupňom
• Ak graf má vrcholy s nepárnym stupňom kreslenie skončí vždy v tom druhom uzle, ktorý má nepárny stupeň
• Po "prvom" pokuse nakresliť graf jedným ťahom, môžu nastať prípady
  • graf je komplet nakreslený
  • zvyšné hrany s uzlami tvoria grafy už len s párnymi vrcholmi

Čitateľ s matematickými záľubami si iste tieto tvrdenia ľahko dokáže, pre ostatných sú pokusy s kreslením "domčeka", ľahko sa presvedčíme, že k úspechu vedie len začiatok vo vrchole 4 resp. 5.
Hrubá schéma algoritmu:

1. Zistíme koľko vrcholov je nepárneho stupňa a ak isú dva zapamätáme si jeden z nich
2. Ak je nepárny vrchol začneme v ňom, inak začneme napr. v uzle 1
3. V každom vrchole si zvolíme náhodný smer a kreslíme pokiaľ nevojdeme do uzla z ktorého už cesta nevedie.
4. Opätovným prechodom po nájdenej ceste hľadáme vrcholy z ktorých ešte vychádzajú nejaké cesty, ktoré sme ešte neprešli - teda vrcholy kde sme mali odbočiť ale neurobili sme to.
5. Ak taký vrchol nájdeme (označme ho u1), vyrazíme z neho po tejto ceste. Po prejdení niekoľko vrcholov sa opäť musíme vrátiť do tohto uzla (porozmýšľajte prečo). Celú túto "novú" trasu popísanú postupnosťou vrcholov "vsunieme" do "starej" cesty za vrchol u1. Teraz môžeme pokračovať v kontrole našej cesty.
6. Po kontrole celej cesty je graf komplet prejdený.