TEORIE GRAFÙ - ZÁKLADNÍ POJMY

TEORIE GRAFÙ

ZÁKLADNÍ POJMY

Def

Øíkáme, že je dán prostý graf, jestliže je dána:

Množina X (uzlù, vrcholù); X = . Nech P(X) je množina všech podmnožin množiny X.

Zobrazení : X P(X), tj. množina hran U = .

Oznaèení: G = (X, U), G = (X, ) - viz dále.

Orientovaná hrana - uspoøádaná dvojice uzlù (x₀, x₁), kde x₀ je poèáteèní uzel a x₁ (x₀) je koncový uzel. je množina orientovaných hran.

Neorientovaná hrana - neuspoøádaná dvojice uzlù (x₀, x₁). U je množina neorientovaných hran.

Funkce G tedy pøiøazuje každému uzlu z grafu G množinu uzlù z G, se kterými je tento uzel spojen hranami. Množina všech orientovaných hran grafu G je

napø. Obr. 1: x₀ X, (x₀) =

V prostém grafu je mezi dvìma uzly maximálnì 1 hrana (orientovaná nebo neorientovaná.)

Def

Multigraf - jedné dvojici uzlù je možno pøiøadit víc hran (orientovaných nebo neorientovaných) - narozdíl od prostého grafu.

Neorientovaný graf - G = (X, ) = (X,U).

Orientovaný graf - G = (X, ) = (X,). Hrany jsou orientované; každé je pøiøazena urèitá orientace (smìr).

Ohodnocený graf (orientovaný, pøíp. neorientovaný) - G = (X, ), kde je reálná funkce definovaná na U a pøiøazující každé hranì nìjakou hodnotu (napø. vzdálenost, doba jízdy, ).

Úplný graf -graf bez smyèek (tj. hran, jejichž oba koncové uzly jsou shodné), ve kterém jsou každé dva uzly spojeny hranou

Rovinný graf - uzly grafu jsou body roviny a hrany lze reprezentovat spojitými orientovanými  køivkami, ležícími v rovinì, pøièemž mají spoleèné body pouze v koncových bodech. Koncové body køivek jsou uzly grafu.

Graf, který není rovinný nazýváme prostorový graf .

Pozn. Na obr. 2 je tedy orientovaný ohodnocený rovinný úplný multigraf.

Def

Graf G₁=(X₁,U₁) je podgrafem grafu G = (X,U) tehdy, jestliže je to graf a obsahuje nìkteré jeho uzly a hrany.

X X U₁ U G₁ G tj. (X₁,U₁) (X,U)

Def

Orientovaný sled - z jednoho uzlu (a) do jiného (b) je taková posloupnost uzlù orientovaného grafu, kde u₀ = a, u_n = b a h₁ = (a, u₁), h_i = (u_i-1, u_i) pro i = 2, 3, , n-1,
h_n = (u_n-1, b) jsou orientované hrany grafu.

Dráha - orientovaný sled, ve kterém se žádný uzel nevyskytuje dvakrát.

Neorientovaný sled - z jednoho uzlu (a) do jiného (b) je taková posloupnost vrcholù neorientovaného grafu, kde u₀ = a, u_n = b a h₁ = (a, u₁), h_i = (u_i-1, u_i) pro i = 2, 3, , n-1, h_n = (u_n-1, b) jsou hrany grafu.

Cesta- neorientovaný sled, ve kterém se žádný uzel nevyskytuje dvakrát.

Tah orientovaný (neorientovaný) - orientovaný (neorientovaný) sled, ve kterém se žádná hrana dvakrát neopakuje.

Silná souvislost grafu - z každého uzlu orientovaného grafu se lze dostat po orientovaných drahách do jakéhokoliv jiného uzlu.

Slabá souvislost grafu - z každého uzlu neorientovaného grafu se lze dostat po cestách do jakéhokoliv jiného uzlu.

Komponenty grafu - nejvìtší slabì souvislé podgrafy tohoto grafu (napø. graf G na obr. 1 má dvì komponenty G' a G'': X' = a X'' = .)

GRAFY A MATICE

Øíkáme, že matice A je rozpadlá (reducibilní), jestliže lze pøeèíslovat rovnice a neznámé tak, že soustava rovnic má tvar:

kde M, P jsou ètvercové matice, O je nulová matice.

Potom platí P , M - N a tedy øešení pùvodní soustavy je pøevedeno na posloupnost øešení dvou soustav menšího øádu.

Jestliže takové pøerovnání rovnic a pøeèíslování neznámých není možné, øíkáme že matice je

nerozpadlá (irreducibilní)

Vìta

Nech A je typu (n,n). Pøiøadíme matici A graf G = (X,) takto:

G má n uzlù (u₁, u₂, , u_n) = X.

definujeme takto: (u_i, u_j) a_ij 0, kde a_ij je prvek matice A.

Matice je irreducibilní právì tehdy, jestliže graf G je silnì souvislý.

EULERÙV TAH

Def

Stupeò uzlu v orientovaném grafu: d(x⁺) poèet hran vystupujících z uzlu x; d(x^-) poèet hran vstupujících do uzlu x.

Stupeò uzlu v neorientovaném grafu: d(x) poèet hran vystupujících (= vstupujících) z uzlu x.

Pravidelný graf - všechny uzly grafu jsou stejného stupnì.

Def

Eulerùv tah -tah, který  prochází všemi hranami grafu (právì jednou).

- otevøený - konèí v jiném uzlu, než ve kterém zaèal.

- uzavøený - konèí v uzlu, ve kterém zaèal.

Lze-li provést Eulerùv tah, pak se jedná o Eulerùv graf.

3 vìty (platné pro souvislý graf)

V grafu jsou více než 2 uzly lichého stupnì Eulerùv tah neexistuje.

V grafu jsou právì 2 uzly lichého stupnì Eulerùv tah existuje, je otevøený. (Zaèíná v prvním (druhém) uzlu lichého stupnì a konèí v druhém (prvním) uzlu lichého stupnì.)

V grafu jsou všechny uzly sudého stupnì Eulerùv tah existuje, je uzavøený. (Zaèíná a konèí v libovolném uzlu grafu.)

Sedm mostù v mìstì Královci

Ve mìstì Královci jsou na øece Pregel dva ostrovy, které jsou se zbytkem mìsta spojeny sedmi mosty jako na obr. 3 vlevo. Lze si udìlat procházku, pøi které bychom prošli po každém mostì právì jednou?

Nelze. V grafu jsou všechny ètyøi uzly lichého stupnì (obr. 3 vpravo), takže podle vìty 1) Eulerùv tah neexistuje.

Domeèek

Lze nakreslit jedním tahem domeèek?

Ano, domeèek jedním tahem nakreslit lze (napø. obr. 4), protože obsahuje právì dva uzly lichého stupnì (a a f). Podle vìty 2) tedy existuje otevøený Eulerùv tah. Lze najít mnoho zpùsobù, jak domeèek nakreslit, ale pokaždé bude tah zaèínat a konèit v uzlech a a f.

STROM A KOSTRA GRAFU

Def

Nech

G = (X,U) neorientovaný multigraf,

X = n poèet uzlù,

U = m poèet hran,

k poèet komponent grafu G.

Potom èíslo (G) = m - n + k se nazývá cyklomatické èíslo grafu.

Èíslo (G) vyjadøuje poèet nezávislých kružnic v grafu a napø. v elektrotechnice  je to minimální poèet lineárnì nezávislých rovnic pøi použití 2. Kirchhoffova zákona.

Def

Vytvoøíme matici A tak, že v zadaném grafu G hledáme všechny uzavøené kružnice. V matici A má každá hrana svùj sloupec. Každé kružnici pøísluší jeden øádek matice A tak, že jednotlivé prvky tohoto øádku udávají, kolikrát daná kružnice prošla zvoleným smìrem dané hrany (pokud kružnice prochází opaèným smìrem než zvoleným, poèítáme tento prùchod zápornì.)

Hodnost takto vytvoøené matice A je cyklomatické èíslo grafu (G) a její lineárnì nezávislé vektory urèují nezávislé kružnice grafu G.

Strom - souvislý graf, který neobsahuje žádnou kružnici.

Vìta

Strom má tyto ekvivalentní vlastnosti:

G je souvislý, (G) = 0.

(G) = 0, m = n - 1

G je souvislý a má n - 1 hran.

(G) = 0 a je-li hrana h U, potom graf G₁ = (X, U₁), kde U₁ = U , má (G₁) = 1.

Nech G je souvislý a h U, potom graf G₁ = (X, U₁), kde U₁ = U - , je graf nesouvislý.

Def

Kostra grafu - podgraf, který je stromem.

Minimální kostra grafu - taková kostra G' ohodnoceného grafu G = (X,U,), že (h) je minimální ze všech existujících koster grafu G.

HLEDÁNÍ MINIMÁLNÍ KOSTRY GRAFU

Níže popsané metody vycházejí z pøedpokladu, že zkoumaný graf je prostý, ohodnocený a souvislý. Pokud prostý není, tak pro každé dva uzly nalezneme nejkratší hranu, která je spojuje, a ostatní hrany, které tyto dva uzly spojují, z grafu odstraníme.

Borùvkova metoda

algoritmus

1. V libovolné kružnici v grafu škrtnìte nejdelší hranu.

2. Opakujte krok 1. tak dlouho, dokud lze v grafu nìjakou kružnici najít.

Z grafu zbyla jeho minimální kostra.

Vìta

Nech K je kružnice v grafu U a nech h₁ je nejdelší hrana na kružnici K, tj. h  K: (h₁)  (h).

Potom existuje minimální kostra, která neobsahuje hranu h₁.

Pozn. Kdyby byla nerovnost ostrá, potom žádná minimální kostra neobsahuje hranu h₁. Neostrá nerovnost je zde pro pøípad, že by na kružnici bylo víc hran se stejným nejmenším . Potom by bylo více rùzných minimálních koster grafu.

Vìta

H je množina všech hran, které leží aspoò na jedné kružnici. Nech h  H₀ ‑ : (h₁)  (h).

Potom existuje minimální kostra, která obsahuje hranu h₁.

Pozn. Kdyby byla nerovnost ostrá, potom každá minimální kostra obsahuje hranu h₁.

Vìta

Nech G = (X,U,). Nech G_i = (X_i,U_i,_i), jsou disjunktní podgrafy grafu G (tj. žádné dva grafy G_i nemají spoleènou ani jednu hranu ani uzel.)

Nech A_i je množina takových hran, které jsou incidentní s X_i pouze jedním uzlem a jejich druhý uzel leží v jiné množinì než X_i.

Potom každá minimální hrana z A_i leží na minimální kostøe grafu G.

Pozn. Pro graf na obr. 5 jsou tedy v množinì A₁ právì èárkované hrany.

Jarníkova metoda

algoritmus

1. Vyberte libovolný uzel x₁ X a dejte ho do množiny F.

2. Vyberte nejkratší hranu vedoucí z uzlù v množinì F do ostatních uzlù (tj. X-F) a pøíslušný koncový bod dejte do F. Vybraná hrana je již hrana kostry.

3. Opakujte od kroku 2, dokud nejsou všechny uzly grafu v množinì F.

Hrany, které jsme vybrali v bodì 2 potom tvoøí minimální kostru grafu.

Dijkstrova metoda hledání minimální kostry

množiny hran

- Obsahuje hrany, které jsou již vybrány.

- Hrany, z nichž právì jedna bude v pøíštím kroku pøidána do mn. 1.

- Ostatní hrany.

množiny uzlù

A - Uzly pøíslušné k hranám z mn. 1.

B - Ostatní uzly.

algoritmus

1. krok: Libovolný uzel x₁ 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 (x_i) dejte do mn. A (první už tam je.)

3. krok: Nech x_i je uzel, který byl naposledy pøidán do mn. A. Nech H je množina hran, jejichž jeden uzel je x_i 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.

HLEDÁNÍ MINIMÁLNÍ DRÁHY V GRAFU

Def

Minimální dráha z uzlu a do uzlu b je taková dráha H, pro kterou (h) je minimální.

Dijkstrova metoda hledání minimální dráhy

Tato metoda je urèena pro orientovaný graf. Pro graf neorientovaný staèí každou jeho hranu pøevést na dvì opaènì orientované.

množiny hran

- Obsahuje hrany, které jsou již vybrány.

- Hrany, z nichž právì jedna bude v pøíštím kroku pøidána do mn. 1.

- Ostatní hrany.

množiny uzlù

A - Uzly pøíslušné k hranám z mn. 1. (Pro každý uzel z mn. A registrujeme jeho minimální doposud známou vzdálenost od startu a.)

B - Uzly pøíslušné k hranám z mn. 2.

C - Ostatní uzly.

algoritmus pro nalezení minimální dráhy ze startu do cíle

1. krok: Start dejte do mn. A. Všechny hrany vycházející ze startu dejte do mn. 2 a koncové uzly tìchto hran dejte do B.

- Proveï následují krok tolikrát, až v A bude cíl:

2. krok: Každý uzel z B je incidentní s právì jednou hranou z 2, jejíž poèáteèní uzel je v množinì A. Tím je definovaná jistá dráha ze startu do každého uzlu v B. Uzel x_i z B, do kterého jde nejkratší taková dráha ze startu odstraníme z B a pøidáme do A. Odpovídající hranu z 2 odstraníme a pøidáme ji do mn. 1.Všechny orientované hrany, které vycházejí z x_i a jejichž koncové uzly leží v C odstraníme z mn. 3 a pøidáme do množiny 2. Koncové uzly tìchto hran pøidáme k množinì B.Nyní uvažujme všechny orientované hrany h, které vycházejí z x_i  a jejichž koncové uzly leží v B, a zkoumáme, zda-li užitím nìkteré hrany h nezkrátíme již známou dráhu ze startu do uzlù v B. Je-li tomu tak, pak hranu h odstraníme z mn. 3 a pøidáme k množinì 2 a odpovídající hranu odstraníme z množiny dva a pøidáme do množiny 3.

Využití matic pøi hledání minimální dráhy v grafu

Def

Matice sousednosti a_ij = 1 (x_i,x_j) , a_ij = 0 (x_i,x_j)

Vìta

Nech G je orientovaný graf a A je jeho matice sousednosti. Nech = A^k.

Potom p_ij­ je poèet rùzných drah délky k jdoucích z i-tého do j-tého uzlu.

dùk. Indukcí podle k:

I. k = 1 platí z definice matice sousednosti

II. = A^k-1, p_ij = q_il p_lj C.B.D (= tím je to dokázáno)

Def

Matice ohodnocení A: = ((x_i,x_j)).

Vìta

Nech G je orientovaný graf a A je jeho matice ohodnocení. Nech = A^k.

Potom p_ij­ je délka miniální dráhy jdoucí z i-tého do j-tého uzlu.

dùk. Indukcí podle k.

TOKY V SÍTÍCH

Tok v síti je napø. proud v elektrickém obvodu, zboží v železnièní síti, voda v potrbní síti ap.

Def

Sí S = (G, z, s, c), kde G je orientovaný graf, z je zdroj, s je spotøebiè, c je kapacita (propustnost hrany) defiovaná na množinì hran h

Def

Tok t(h) je funkce defiovaná na množinì hran h . Platí:

t(h) c(h) ( Tok je nezáporný a menší nebo roven kapacitì hrany.)

t(u,v) = t(u,w); (u,v) U, (u,w) U ( Souèet tokù, které vcházejí do uzlu, z nìj také vychází - platí pro všechny uzly v síti, kromì zdroje a spotøebièe.)

Def

Velikost toku |t| = t(z,u), (z,u) U. ( Celková velikost toku je rovna souètu všech tokù na hranách vedoucích ze zdroje do uzlù, které se zdrojem sousedí.)

Vìta

|t| = t(w,s), (w,s) U. ( Celková velikost toku je rovna souètu všech tokù na hranách vedoucích do spotøebièe z uzlù, které se spotøebièem sousedí.)

Hledání maximálního toku v síti

Ford - Fulkersonùv algoritmus

1. krok (Inicializaèní): h G: t(h) = 0

2. krok (Nalezení zlepšující cesty): Hledejte posloupnost vrcholù v_i pro i = 1, 2, , k takovou, že  buï (v_i,v_i+1) , t(v_i,v_i+1) c(v_i,v_i+1), nebo (v_i,v_i-1) , t(v_i,v_i-1) 0 pro (v_i,v_i‑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 d_i = (c(v_i‑1,v_i) ‑ c(v_i,v_i‑1)) + t(v_i,v_i-1). Pøírùstek toku pro vybranou cestu je d = min (nejmenší pøírùstek pøidìlený v tomto kroku této cestì.)

4. krok: d'_i = min ; d''_i = d - d'_i. Je-li (v_i‑1, v_i) t(v_i‑1, v_i) = (v_i‑1, v_i) + d'_i. Je-li (v_i, v_i-1) t(v_i‑1, v_i) = (v_i‑1, v_i) - 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 ¹⁾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, ²⁾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.

Dinicùv algoritus

V kroku 2 bereme v úvahu jenom hrany na nejkratších drahách ze zdroje.