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.