Základní typy grafů
Eulerovský graf
Souvislý graf obsahující tah procházející všemi vrcholy a hranami (Eulerovksý tah)
(Prochází všemi hranami a vrcholy. Hranami nejvíce jednou vrcholy libovolněkrát.)
Hamiltonovský graf
Strom
O stromech
Aby libovolný konečný, souvislý graf byl stromem,
je nutné a postačující,
aby počet jeho hran byl o jednu menší než počet jeho vrcholů.
Souvislý graf obsahující tah procházející všemi vrcholy a hranami (Eulerovksý tah)
(Prochází všemi hranami a vrcholy.
Hranami nejvíce jednou vrcholy libovolněkrát.)
Bigraf
Co je bigraf
Bigraf je orientovaný graf G , jehož množinu uzlů lze rozložit na disjunktní neprázdné
podmnožiny U1, U2 2 tak, že pro každou hranu (u, v)
u patří do množiny U1 a v patří do množiny U2.
Jednoduše řečeno takový graf, který se dá rozdělit na dvě množiny uzlů
a který má hrany které vedou pouze mezi těmito skupinami nikoliv
mezi uzly jedné skupiny.
V grafu lze najít / určit
Vlastnosti grafů
Souvislý graf
Acyklické orientiované grafy
Orientovaný graf s konečnou množinou vrcholů
je acyklický právě když každý jeho neprázdný podgraf
obsahuje vstupní vrchol.
Orientovaný graf je acyklický právě když v každém
jeho neprázdném podgrafu existuje výstupní vrchol.
Orientovaný graf je acyklický právě když v jeho
vrcholy lze seřadit do posloupnosti (v1, ...vn)
tak že pro každou hranu vi,vj paltí, že i<j
Algoritmy
Dijkstrův algoritmus
12.2
Vstupem je ohodnocený orientovaný graf (G, w) a jeden vrchol v z množiny všech vrcholů V(G) a jeho výstupem je vážená vzdálenost mezi vrcholem v a libovolným vrcholem x
a minimální cesta z Px z vrcholu v do vrcholu x.
Postup pro graf G.
Příprava 1. Vytvoříme si nový graf T typu strom, do kterého budeme postupně přenášet zjištěné poznatky o grafu G. Z grafu G zvolíme jeden vrchol jako počáteční. To bude vrchol stromu T.
Příprava 2. jeho horní odhad vzdálenosti od něj samotného je 0
Příprava 3. horní odhad vzdálenosti všech ostatních uzlů je nekonečno
Příprava 4. přímým sousedům zvoleného vrcholu přiřadíme
Krok 1. Pokud je náš graf T kostrou grafu G nebo všechny ostatní vrcholy G jsou z našeho výchozího bodu nedostupné, přejdeme na Konec. Jinak pokračujeme dalšími kroky.
Krok 2. Z vrcholů grafu G si vybereme si vybereme ten, který jsme ještě do našeho stromu nepřevedli a který má minimální vzdálenost od našeho výchozího vrcholu. Pokud je jich více stejných, libovolně si jeden vrchol zvolíme.
Krok 3. přidáme jej do našeho stromu a přepočítáme odhad vzdálenosti pro všechny jeho sousedy. Pokud je jeho sousedem některý z vrcholů, které již v našem grafu T máme a jehož odhad vzdálenosti by měl být měnší než je dosud, změníme ho.
Krok 4. Přejdeme na Krok 1. a celý cyklus budeme opakovat
Konec 1. Pro každý vrchol grafu T je hledanou minimální cestou cesta z vrcholu T, která je jednoznačně určena. její váha určuje váženou vzdálenost. Pro ostatní vrcholy grafu G, které v našem grafu T nemáme cesta neexistuje a vážená vazdálenost je nekonečno.
Jiný popis téhož
dijkstrova metoda hledání minimální kostry
množiny hran:
1 - Obsahuje hrany, které jsou již vybrány.
2 - Hrany, z nichž právě jedna bude v příštím kroku přidána do mn. 1.
3 - Ostatní hrany.
množiny uzlů:
A - Uzly příslušné k hranám z mn. 1.
B - Ostatní uzly.
algoritmus:
1. krok: Libovolný uzel x1 dejte do mn. A. Všechny hrany s ním incidentní do mn. 2.
2. krok: Vyberte z mn. 2 nejkratší hranu a přidejte ji do 1. Její druhý uzel (xi) dejte do mn. A (první už tam je.)
3. krok: Nechť xi je uzel, který byl naposledy přidán do mn. A. Nechť H je množina hran, jejichž jeden uzel je xi a druhý je v mn. B. Do množiny 2 potom přidejte ty hrany z H, které buď nejsou incidentní s hranami z mn. 2, anebo s nimi incidentní jsou, ale jsou kratší. Pokud jsou kratší, přesuňte ty delší z mn. 2 do mn. 3. Opakujte od kroku 2, dokud nejsou všechny uzly v mn. A.
Hrany v mn. 1 tvoří potom kostru grafu.
Pozn. V mn. 1 2 se nevyskytuje kružnice.
Hladový algoritmus
Ford-Fulkersonův
Popis
Ford - Fulkersonův algoritmus:
1. krok (Inicializační): h G: t(h) = 0
2. krok (Nalezení zlepšující cesty): Hledejte posloupnost vrcholů vi pro i = 1, 2, ..., k takovou, že buď (vi,vi+1) , t(vi,vi+1) c(vi,vi+1), nebo (vi,vi-1) , t(vi,vi-1) 0 pro (vi,vi‑1) . Pokud žádnou takovou zlepšující cestu nelze najít, jděte na krok 5.
3. krok (Určení přírůstku toku): Pro i = 1, 2, ..., k je přírůstek toku di = (c(vi‑1,vi) ‑ c(vi,vi‑1)) + t(vi,vi-1). Přírůstek toku pro vybranou cestu je d = min {di} (nejmenší přírůstek přidělený v tomto kroku této cestě.)
4. krok: d'i = min {d, c(vi‑1, vi) - t(vi‑1, vi)}; d''i = d - d'i. Je-li (vi‑1, vi) t(vi‑1, vi) = (vi‑1, vi) + d'i. Je-li (vi, vi-1) t(vi‑1, vi) = (vi‑1, vi) - d''i. Opakuj krok 2.
5. krok: Konec. Výsledkem jsou toky přidělené jednotlivým hranám.
Komentář ke kroku 2: Zlepšující cesta tedy vede orientovanými hranami grafu tak, že 1)jde buď stejným směrem jako je orientace dané hrany a kapacita této hrany je menší než tok, který jí již byl přidělen, 2)anebo jde opačným směrem než je orientace dané hrany a tok, který této hraně již byl přidělen, je větší než 0.
Stejná zlepšující cesta může a zpravidla i musí být zvolena víckrát.
Výhoda algoritmu: Pro celá čísla vede konečný počet kroků k cíli. (Pro reálná po převodu na celá také.)
Nevýhoda: Velmi pomalé díky nedokonalosti kroku 2. Další algoritmy jsou takovými modifikacemi tohoto algoritmu že se liší jen krokem 2.
Operace prováděné s grafem
Značkování vrcholů
Má-li vrchol značku, znamená to, že do něj vede cesta z
daného výchozího vrcholu r.
Algoritmus
1. [Inicializace] Označkujeme vrchol r, ostatní vrcholy jsou bez značek.
2. [Výběr hrany] Vybereme libovolnou hranu e, jejíž počáteční vrchol má značku a koncový
vrchol nikoliv. Pokračujeme podle kroku 3. Jesliže taková hrana neexistuje, výpočet končí.
3. [Značkování] Označkujme vrchol Kv(e) a pokračujme ve výpočtu dle kroku 2.
Matice
Incidenční matice M(G) - Matice sousednosti
Orientovaného grafu
Incidenční matice orientovaného grafu G je reálná
matice o rozměrech n řádků (počet vrcholů) * m sloupců (počet hran).
Definovaná vztahem M(G)=(mij) kde
mij = +1 pokud hrana ej vychází z vrcholu vi
mij = -1 pokud hraba ej vchází do vrcholu vi
jinak 0. (řádky vrcholy, sloupce hrany)
V každém sloupci matice M(G) jsou právě dva
nenulové prvky z nichž jeden je +1 a druhý -1
Důvodem je, že každá hrana obsahuje dva vrcholy
v jednom končí a v jednom začíná.
Hodnost incidenční matice M(G) je:
Maximální velikost lineárně nezávislé množiny jejích řádků.
Množina všech řádků matice M(G) je lineárně závislá.
Neorientovaného grafu
Je naplněna hodnotami 1 a 0
Řádky odpovídají uzlům Sloupce hranám
V řádku je tolik jedniček, s kolika hranami je uzel spojen
Ve sloupci jsou vždy dvě jedničky.
Laplaceova matice
L= MR(orientovaného G) * (MR(orientovaného G) * )^T
Je to čtvercová matice, která se vytvoří tak
že na diagonálu [1,1] až [poslední řádek, poslední sloupec] se zapíšou čísla, které
vyjařují počet hran uzlu.
V [1,1] tedy bude počet hran uzlu 1 ve [2,2] počet hran uzlu 2 atd.
Další čísla se doplňují tak, že pokud spolu uzly nejsou spojeny hranou
bude číslo 0 pokud spolu mají hranu bude číslo -1
Nad diagonálou i pod ní jsou údaje stejné.
Pokud mezi sebou mají uzly 1 a 2 mají hranu, bude
na souřadnicích [1,2] i [2,1] číslo -1
Speciální matice
Speciální matice
Nulová matice O: aij = 0
Jednotková matice E: aii = 1; i≠j ⇒ aij = 0
Neutralita E: EX=X, uE=u, …
Diagonální matice: i≠j ⇒ aij = 0
Symetrická matice: aij = aji, tzn. A=AT
Dolní (resp. horní) trojúhelníková matice: i<j (resp. i>j) ⇒ aij = 0
Regulární matice: det A ≠ 0
Singulární matice: det A = 0
Distanční matice
Matice vyjadřující vzdálenost mezi jednotlivými uzly
Je sestavena tak že:
0 je na pozici, [1,1], [2,2], [n,n] protože délka cesty z uzlu do něj samého je 0
Nekonečno - je na pozici, kdy nevede cesta z jednoho uzlu do druhého
Číslo 1 až n-1 - udává počet hran mezi dvěma uzly. Na pozici [1,3], počet hran které je třeba projít abychom se dostali z uzlu 1 do uzlu 3. Nejmenší počet je 1 nejvyšší je asi n-1
w-distanční matice, Matice vážených vzdáleností
u ohodnoceného orientovaného grafu (G, w) s vrcholy v1, ... vn je matice D^w(G)
o rozměrech n x n, kde na jednotlivých souřadnicích jsou
uvedeny minimální vzdálenosti mezi jednotlivými vrcholy.
Sestavit lze například pomocí Dijkstrova algoritmu, provedeného pro každý z n vrcholů.
Celková výpočetní náročnost tak bude O(n^3)
Další možností je metoda s tzv. čtverečkovaným sčátáním a čtverečkovaným násobením - S Diskrétní matematika str. 136
Zjištění určité skutečnosti
Zjištění počtu sledů dané délky
Věta 11.2 Nechť G je orientovaný graf a číslo k >=0.
Potom hodnota prvku na souřadnicích [i, j]
umocněné matice sousednosti na k
je rovna počtu sledů délky k z vrcholu i do vrcholu j.
A polidštěně
Hodnoty v k-té mocnině matice sousednosti udávají počet
sledů délky k mezi jednotlivými vrcholy.
Postup:
0. Pokud je graf neorientovaný, provedeme jeho symetrizaci (rozdvojit a osměrovat hrany)
1. Vytvoříme matici sousednosti orientovaného grafu
2. Máme první mocninu matice sousednosti, která říká, kolik sledů délky 1 vede mezi vrcholy. Například číslo na souřadnicích [1,2] řáká, kolik sledů délky 1 vede mezi vrcholy v1 a v2. Číslo na souřadnicích [1,1] udává počet sledů délky jedna z vrcholu v1 zase do vrcholu v1, tedy, jestli má vrchol v1 smyčku.
3. Umocníme matici sousednosti (vynásobíme ji stejnou maticí). Nyní čísla udávají počet sledů délky 2 mezi jednotlivými vrcholy.
4. Dalším umocňováním zjišťujeme další počty sledů danné délky (podle umocnění) mezi danými vrcholy.
Určení vzdálenosti mezi vrcholy
Jednotlivé prvky distanční matice udávají délku nejkratší cesty
mezi jednotlivými body.
Na diagonále jsou 0 protože délka cesty z bodu do něj samotného je 0
Tam kde cesta není se udává nekonečno.
(délky dle mocniny distanční matice)
Postup:
U menších grafů se dá sestavit "od oka"
U větších je doporučen tento postup
1. vytvoření matic sousednosti
1a. pro 0 mocninu (jen jedničky na diagonále)
1b. první mocninu - uzly ve vzdálenosti 1
.
.
1n-1 pro nejvtší možnou vzdálenost cesty - což je n(počet vrcholů)-1
2. Začneme zapisovat do distanční matice - píšeme čísla mocnin
ve kterých se poprvé objevil sled mezi vrcholy
2a - dle 0 mocniny matice sousednosti tak zapíšeme do distanční matice na diagonálu 0
2b - Tam kde se objeví číslo zapíšeme do distanční matice 1 - jednou zapsaná čásla už nepřepisujeme
2n - Tam kde dosud nejsou zapsaná čísla, napíšeme nekonečno
Vyhledání maximálního toku
Ford-Fulkerson
Velikost maximálního toku je rovna propustnosti minimálního řezu
oddělujícího zdroj a stok
Postup:
1. Jako výchozí tok x zvolme nulový tok: xij := 0 pro každou hranu (i, j) z množiny všech hran grafu G
2. Jestliže v grafu existuje nějaká rezervní polocesta, upravíme tok podle ní.
2a - pokud je rezervní polocesta souhlasně orientovaná
2b - pokud je nesouhlasně orientovaná
2c - pokud je shodná
- opakuje bod 2. dokud existuje rezervni polocesta
3. je nalezen maximalni tok
Složitost řešení
Obecně
Polynomiální - maximální časovou náročnost je možné odhadnout polynomem
n, n log n, n^2, n^3, n^4 ....
Tyto algoritmy často pracují deterministicky = v každém kroku je znám krok další
Exponenciální u algoritmů snažících se problém vyřešit hrubou sílou (postupně vyzkoušet všechny možnosti)
2^n -probrat všechny podmnožiny dané n-prvkové množiny
2! -probrat všechny permutace n-prvkové množiny do sebe
n^n -probrat všechna zobrazení n-prvkové množiny do sebe
Třída P - Polynomiální - je znám algoritmus, jak danou úlohu vyřešit s polynomiální časovou náročností
Třída NP - Nedeterministicky Polynomiální - Není znám algoritmus, který by danou úlohu pomáhal řešit v polynomiálním čase.
Třída NPC (NP complet) NP-úplné - úlohy NP, u kterých, kdyby se podařilo nalézt efektivní řešení, vyrešila by se najednou celá skupina podobných problémů
Nalezení distanční matice
Vzdálenost libovolných dvou vrcholů je buď menší než n nebo nekonečná,
stačí pro zjištění distanční matice spočítat n-1 mocnin matice sousednosti.
Výpočet každé mocniny spočívá ve vynásobení dvou matic o rozměrech n x n,
které vyžaduje O(n^3) aritmetických operací.
Celková doba výpočtu tak bude O(n^4)