Teorie grafu zkouma struktury zvane grafy. Graf je tvoren vrcholy, ktere jsou vzajemne spojene hranami. Znazornuje se obvykle jako mnozina bodu spojenych carami. Formalne je graf usporadanou dvojici mnoziny vrcholu V a mnoziny hran E:
G = ( V, E )
Pomoci grafu lze reprezentovat struktury a ulohy z nejruznejsich oboru. Taktez mnoho problemu praktickeho zivota muze byt formulovano jako uloha teorie grafu. O tom vice, u jednotlivych ukolu
Hrana (spojnice mezi dvema vrcholy) muze byt orientovana a neorientovana Orientovana hrana ma dany smer, z A se dostaneme do B, ale nikol uz z B do A. (Napr. jednosmerna ulice) U neorientovane hrany na smeru nezalezi. Hrana muze byt take ohodnocena (vzdalenost mezi body, cena prepravy mezi body, apod.)
Tradicne se za zakladatele teorie grafu povazuje Leonhard Euler, ktery roku 1736 resil ulohu, jak projit pres sedm mostu v Kralovci (kazdy z nich prave jednou) a vratit se do vychoziho mista. To v moderni teorii odpovida pojmu eulerovsky graf.
castecne prevzato z wikipedie
Jednotlive ukoly budou zalozeny na tomto grafu:
Ukol 1:
Cisla A a B:
Hledani nejkratsi cesty
Realna aplikace:
Algoritmus pro hledani nejkratsi (nebo nejlevnejsi, apod.) cesty se vyuziva u hledani jizdnich radu, u sitoveho protokolu OSPF, ktery hleda nejlevnejsi spojeni mezi sitemi, apod.
J = delka nejkratsi cesty z bodu A do bodu F
K = delka nejkratsi cesty z bodu A do bodu D
A = J - K
L = delka nejkratsi cesty z bodu D do bodu C
M = delka nejkratsi cesty z bodu D do bodu H
B = L - M
Metode hledani hrubou silou Vam asi nezabranim, ale tato metoda je neprehledna a pravdepodobne udelate spoustu chyb. Lepsi metodu Vam prozradi pan Edsger Dijkstra.
Upozorneni:
Nezapomente, ze hrany jsou ohodnocene a orientovane!
V grafu jsou i 4 neorientovane hrany (maji sipky na obe strany) a to mezi body E a D, F a G, G a H, D a G. Hrany jsou oznaceni carkovane pouze kvuli zdurazneni neorientovanosti.
Ukol 2:
Cislo C zjistite takto:
Sestavte matici sousednosti (hrany opacne orientovane (do uzlu vchazejici) uvazujte jako 0 ne jako -1!) naseho grafu a tuto matici transponujte.
C = soucet hodnot na radku odpovidajici vrcholu E (5. radek) v matici M, ktera je vysledkem operace:
M = S * ST - kde S je matice sousednosti a ST je transponovana matice sousednosti
Ukol 3:
Cislo D:
Zjistete minimalni kostru grafu.
Kostra grafu je takovy podgraf, ktery obsahuje vsechny vrcholy a je stromem.
Realna aplikace:
Propojeni nekolika mest elektrickou siti s minimalni delkou vedeni
Natazeni elektrickeho vedeni v byte tak, aby se co nejme sekalo do zdi
S vypoctem Vam poradi jeden z panu: Otakar Boruvka, Joseph Kruskal, Vojtech Jarnik, ci Robert Prim.
Upozorneni: Hrany uvazujte jako neorietovane!
Q = soucet ohodnoceni hran minimalni kostry grafu
D = 23 - Q
Ukol 4:
Cislo E:
Zjistite jako maximalni tok siti z bodu S do bodu T v tomto grafu:
Maximalni tok z bodu x do bodu y urcuje, kolik je mozne danou siti prepravit nakladu/elektriny, apod.
Realne aplikace:
Pocitacova sit - torrenty
Vodovodni potrubi, kanalizace, apod
K vypoctu Vam opet doporucim radce a to pany: Delbert Ray Fulkerson a Lester Randolph Ford, kteri spolupracovali.
T = maximalni tok siti z bodu S do bodu T
E = 31 - T
Ukol 5:
Cislo F:
R = ciferujte rok narozeni Otakara Boruvky
F = R
Cache naleznete na souradnicich: / Cache is on thes coordinates:
N 50° 36.ABC E 015° 33.DEF
Rady k odlovu:
K finalce se da dojet jakomkoliv prostredkem, ale doporucujeme jit z vychozich souradnic pesky, nebo na kole.
Poslednich par metru bude nutne absolovovat pesky. K "Objektu" kde je finalka doporucuji pristup od zapadu, jinudy to pujde spatne.
A samozrejme budte ohleduplni k okoli!