Kapitola 1
Reprezentace grafu V kapitole ?? jsme se dozvěděli, co to jsou grafy a k čemu jsou dobré. Brzo budeme chtít napsat nějaký program, který s grafy pracuje. Ale jak si takový graf uložit do počítače? To si teď vysvětlíme. Všechny možné reprezentace si budeme vysvětlovat na následujícím grafu G = (V, E) a orientovaném grafu H = (W, F ). V každé sekci budou jejich reprezentace uvedeny jako příklad. A
B
C
D
graf G
E
a
b
c
graf H
d
V této knize označujeme vrcholy grafu písmeny abecedy. Je to tak lepší pro výklad a diskuse nad grafy v příkladech. V počítači označujeme vrcholy pomocí čísel 1, 2 až n.1 Výhody a nevýhody jednotlivých reprezentací jsou shrnuty na konci kapitoly.
1.1
Seznam hran
Uložíme si počet vrcholů a seznam všech hran. Hrana je dvojice vrcholů. V neorientovaných grafech je jedno, jestli si hranu uv ∈ E pamatujeme jako dvojici uv nebo vu. Ale v případě orientovaných grafů už musíme dodržet správné pořadí vrcholů. Většinou za správné pořadí považujeme to po směru šipky. Orientovaný graf může kromě šipky uv obsahovat i opačnou šipku vu. Příklad: Neorientovaný graf na obrázku má 5 vrcholů A až E a seznam hran AB, AC, AD, BD, CD, DE. Orientovaný graf má 4 vrcholy a až d a seznam hran ab, ac, ba, cb a dc. Tato reprezentace je vhodná spíše pro zadávání grafu na vstupu nebo pro skladování grafu na pevném disku. 1 Často
ale začínáme od 0 a končíme vrcholem n − 1.
1
2
KAPITOLA 1. REPREZENTACE GRAFU
1.2
Matice sousednosti
Matice sousednosti zachycuje, které vrcholy spolu sousedí. V matici si pro každou dvojici vrcholů (u, v) pamatujeme, jestli z vrcholu u vede hrana do vrcholu v. Z toho je vidět, že matice reprezentuje orientované grafy. Neorientovaný graf G si můžeme reprezentovat tak, že ho nejprve převedeme na ~ a ten teprve reprezentujeme pomocí matice sousednosti. Orientoorientovaný graf G ~ vaný graf G dostaneme z G tak, že každou neorientovanou hranu uv ∈ E nahradíme dvojicí šipek uv a vu, jdoucích proti sobě. Matice sousednosti A má velikost n × n a je definována jako A = (au,v ), kde 0 ⇐⇒ uv 6∈ E au,v = 1 ⇐⇒ uv ∈ E Protože graf neobsahuje smyčky (hrany z v do v), tak je av,v = 0 pro každý vrchol v ∈ V . Podobně je vidět, že pro neorientované grafy dostaneme symetrickou matici. Příklad: A(G) =
A
B
C
D
E
0 1 1 1 0
1 0 0 1 0
1 0 0 1 0
1 1 1 0 1
0 0 0 1 0
A B C D E
a 0 A(H) = 1 0 0
b 1 0 1 0
c d 1 0 0 0 0 0 1 0
a b c d
Matici sousednosti budeme celkem často používat, protože se s ní jednoduše pracuje. Hlavně velmi rychle zjistíme, jestli je uv hranou grafu. Matice sousednosti obsahuje jen nuly nebo jedničky. Často si ale boolovskou matici rozšíříme na matici integerů, protože pak si v aij můžeme pamatovat ohodnocení hrany ij. Pokud graf není úplný, tak musíme určit jednu hodnotu, která znamená, že hrana neexistuje (běžně se bere „počítačové ∞ÿ, které pro integery je MAXINT; podobně pokud jsou všechna ohodnocení hran nezáporná, tak můžeme použít −1). Pokud si do aij uložíme vzdálenost vrcholu i od vrcholu j, tak dostaneme matici vzdáleností.
1.3
Seznam sousedů
Reprezentaci si vysvětlíme pro orientované grafy. Neorientovaný graf G bychom si ~ který už budeme reprezentovali tak, že ho nejprve převedeme na orientovaný graf G, umět reprezentovat (viz jak to bylo popsáno u matice sousednosti). Teď se podívejme, jak reprezentovat orientovaný graf G = (V, E). Pro každý vrchol v ∈ V si budeme pamatovat seznam jeho sousedů. To je vrcholy, do kterých z v vede hrana. Příklad: A
B C D
B
A D
C
A D
D
A B C
E
D
E
1.4. VÝHODY A NEVÝHODY JEDNOTLIVÝCH REPREZENTACÍ
3
Abychom se vyhnuli spojovým seznamům a přitom neplýtvali pamětí, tak jednotlivé seznamy poskládáme za sebe do jednoho pole. Abychom neztratili přehled o tom, kde který seznam sousedů začíná, tak si stále ponecháme pole V[ · ] obsahující ukazatele na začátky seznamů. Políčko V[i] bude obsahovat index do pole Sousedi[·], na kterém začíná seznam sousedů vrcholu i. Seznam sousedů vrcholu i bude končit o jednu pozici dříve než začíná seznam sousedů vrcholu i + 1. Abychom věděli kde končí seznam sousedů posledního vrcholu, tak rozšíříme obě pole o jedna (odpovídá to přidání fiktivního vrcholu s prázdným seznamem sousedů). Příklad: V: A 1 B 4 C 6 D 8 E 12 13
Sousedi: B C D A D A D A B C E D 1 2 3 4 5 6 7 8 9 10 11 12 13
1.4
Výhody a nevýhody jednotlivých reprezentací
Nejprve si musíme rozmyslet, co chceme v grafu dělat. Mezi nejčastější operace patří testování, jestli jsou dva vrcholy u ∈ V a v ∈ V spojeny hranou. Jinými slovy potřebujeme zjistit, zda je uv hrana. Druhou častou operací je průchod všech sousedů vrcholu v. Následujíc tabulka shrnuje, jak dlouho tyto dotazy trvají v jednotlivých reprezentacích. Zároveň udává i prostorovou složitost každé reprezentace. Reprezentace seznam hran matice sousednosti seznam sousedů
Je uv hrana? O(m) O(1) O(n)
Projít sousedy v O(m) O(n) O(#sousedů)
Prostorová složitost O(m) O(n2 ) O(n + m)
Matice sousednosti nám jako jediná reprezentace umožňuje v konstantním čase určit, jestli je uv hrana grafu (však je tomu šitá na míru). Pro řídké grafy (grafy, které mají málo hran) za to zaplatíme vyšší paměťovou náročností. Příkladem řídkých grafů jsou rovinné grafy, které mají nejvýše 3n − 6 = O(n) hran. Na druhou stranu pro husté grafy (grafy, které mají alespoň c · n2 hran pro nějaké c > 0) je to ideální reprezentace. Zabere lineárně mnoho prostoru ve velikosti grafu, testování, jestli je uv hrana, proběhne v čase O(1) a dokonce i průměrný počet sousedů je Ω(n). V některých algoritmech hodně často procházíme všechny sousedy některých vrcholů a testy, zda je uv hrana, ani nepotřebujeme. V takových případech je nejlepší použít reprezentaci grafu seznamem sousedů. Z předchozích odstavců je vidět, že je každá reprezentace někdy výhodná, každá jindy. Záleží na tom, co s grafem chceme provádět. Pro každý algoritmus si musíme vybrat individuálně. Poznámka: Někdy si spolu s grafem chceme reprezentovat i jeho další vlastnosti. Například pro rovinné grafy chceme znát seznam všech stěn. Pro každou
4
KAPITOLA 1. REPREZENTACE GRAFU
stěnu chceme rychle zjistit seznam hran a vrcholů, které obsahuje. Naopak pro každou hranu chceme vědět, ve kterých stěnách je obsažena. Návrh takové datové struktury už není složitý a proto necháváme na čtenáři, aby si rozmyslel, jak takové věci efektivně reprezentovat.
1.5
Příklady
1. (Převody mezi reprezentacemi) Pro každé dvě reprezentace grafu navrhněte nejefektivnější způsob převodu z první reprezentace do druhé. Určete časovou složitost převodu. 2. (Obrácení hran v orientovaném grafu) Dostanete orientovaný graf reprezentovaný maticí sousednosti A. Obrátit všechny šipky na druhou stranu je jednoduché, stačí vzít matici transponovanou AT . Matice transponovaná k matici A = (ai,j ) je matice AT = (aj,i ) (prohodíme řádky za sloupce a naopak). Ale co když dostaneme graf reprezentovaný seznamem sousedů? Jak rychle obrátíte hrany v této reprezentaci? 3. (Mocnina orientovaného grafu) Mocnina orientovaného grafu G = (V, E) je graf G2 = (V, E 2 ), kde uv ∈ E 2 právě tehdy když z u vede orientovaná cesta délky 2 do v (neboli existuje vrchol w ∈ V takový, že uw ∈ E a wv ∈ E). Navrhněte efektivní algoritmus, který dostane graf G reprezentovaný buď maticí sousednosti nebo seznamem sousedů, a vytvoří graf G2 reprezentovaný stejným způsobem. Jaká je časová složitost vašeho algoritmu? 4. (Hledání stoku) Dostanete orientovaný graf reprezentovaný maticí sousednosti. Většina algoritmů pracujících s maticí sousednosti má časovou složitost alespoň Ω(n2 ). Ale jsou i výjimky. (a) Zkuste co nejrychleji najít univerzální stok grafu. Univerzální stok je takový vrchol, do kterého vede n − 1 hran ze všech ostatních vrcholů, ale ze kterého nevedou žádné hrany ven. Zvládnete to v čase O(n)? (b) Zkuste co nejrychleji najít stok grafu. Stok je takový vrchol, ze kterého nevedou žádné hrany ven. Jaká bude časová složitost vašeho algoritmu? 5. (a) (Matice incidence) Česky bychom mohli říci matice náležení. Tato matice zachycuje, kdy platí v ∈ e pro v ∈ V a e ∈ E. Matice incidence I má velikost n × m a je definována jako I = (iv,e )v∈V,e∈E , kde 0 ⇐⇒ v 6∈ e iv,e = 1 ⇐⇒ v ∈ e Pro graf G ze začátku kapitoly dostáváme následující matici.
I(G) =
eAB 1 1 0 0 0
eAC
eAD
eBD
eCD
1 0 1 0 0
1 0 0 1 0
0 1 0 1 0
0 0 1 1 0
eDE 0 0 0 1 1
A B C D E
V každém sloupci jsou právě dvě jedničky, protože každá hrana má právě dva konce. Pokud bychom chtěli takto reprezentovat orientovaný graf, tak musíme jedničku u výchozího vrcholu šipky změnit na mínus jedničku.
1.5. PŘÍKLADY
5
(b) Matice incidence orientovaného grafu G = V, E) je matice tvaru n × m B = (bv,e ), kde −1 pokud hrana e vychází z vrcholu v 1 pokud hrana e přichází do vrcholu v bv,e = 0 jinak. Zjistěte, jaký význam mají položky matice B · B T , kde B T značí matici transponovanou k matici B.
