6   Minimální kostry, Hladový algoritmus
Kromě teoretických "hrátek" mají kostry grafů (Oddíl 5.4) následující důležité praktické použití: Dříve jsme uvažovali spojení v grafech cestami jdoucími z jednoho místa do druhého, ale nyní se podíváme na jiný způsob "propojování" všech vrcholů grafu najednou.
Vezměme si třeba požadavky propojení domů elektrickým rozvodem, propojení škol internetem, atd. Zde nás ani tak nezajímají délky jednotlivých cest mezi propojenými body, ale hlavně celková délka či cena vedení/spojení, které musíme postavit. □
Našim cílem je tedy najít minimální souvislý podgraf daného grafu, tedy minimální způsob propojení (v daných podmínkách), ve kterém existují cesty mezi každou dvojicí vrcholů.
Stručný přehled lekce
• Řešení problému minimální kostry v grafu - hladový a Jarníkův algoritmus.
• Obecné pojetí hladového algoritmu.
• Matroidy - struktury, na nichž hladový algoritmus vždy funguje.
Petr Hliněný,  Fl MU Brno, 2013
1/16
Fl: MA010: Kostry, Hladový algoritmu:
6.1   Hledání minimální kostry
Problém 6.1. Problém minimální kostry (MST)
Je dán (souvislý) vážený graf G,w s nezáporným ohodnocením hran w. Otázkou je najít kostru T v G, která má nejmenší možné celkové ohodnocení. Formálně
MST =      min ^   w(e) .
kostra TcG \eeE(T) J
Kostra daného grafu je minimální podgraf, který zachovává souvislost každé komponenty původního grafu. Proto nám vlastně ukazuje "minimální propojení' daných vrcholů, ve kterém ještě existují cesty mezi všemi dvojicemi, které byly propojeny i původně.
Petr Hliněný,  Fl MU Brno, 2013
2/16
Fl: MA010: Kostry, Hladový algoritmu:
Praktickou formulací problému je třeba propojení domů elektrickým rozvodem, škol internetem, atd. Jedná se tady o zadání, ve kterých nás zajímá především celková délka či cena propojení, které je třeba vytvořit. Příklad je uveden na následujícím obrázku i s vyznačenou minimální kostrou vpravo.
3 4 3 3 4 3
14 2 14 2
Algoritmus 6.2. „Hladový" pro minimální kostru.
Je dán souvislý vážený graf G, w s nezáporným ohodnocením hran w.
- Seřadíme hrany grafu G vzestupně podle jejich ohodnocení, tj.
w(ei) < w(e2) < • • • < w(em).
- Začneme s prázdnou množinou hran T — 0 pro kostru.
- Pro i — 1,2,...,m vezmeme hranu     a pokud TU {e^} nevytváří kružnici, přidáme    do T. Jinak     "zahodíme". □
- Na konci množina T obsahuje hrany minimální kostry váženého grafu G,w.
Petr Hliněný,  Fl MU Brno, 2013
3/16
Fl: MA010: Kostry, Hladový algoritmu:
■r
Pro ilustraci si ukážeme postup hladového algoritmu pro vyhledání kostry výše zakresleného grafu. Hrany si nejprve seřadíme podle jejich vah 1,1,1,1, 2, 2, 2, 2, 3, 3, 3,4,4.
V obrázku průběhu algoritmu používáme tlusté čáry pro vybrané hrany kostry a tečkované čáry pro zahozené hrany. Hrany teď postupně přidáváme do kostry / zahazujeme. . .
Získáme tak minimální kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2 = 12, která je v tomto případě (náhodou) cestou, na posledním obrázku vpravo.
Poznamenáváme, že při jiném seřazení hran stejné váhy by kostra mohla vyjít jinak, ale vždy bude mít stejnou velikost 12.
Petr Hliněný,  Fl MU Brno, 2013
4/ 16
Fl: MA010: Kostry, Hladový algoritmu:
Důkaz správnosti Algoritmu 6.2:
Nechť T je množina hran získaná v Algoritmu 6.2 a nechť hrany jsou již seřazené w(ei) < w(e2) < • • • < w(em). Vezměme množinu hran To té minimální kostry (může jich být více se stejnou hodnotou), která se s T shoduje na co nejvíce prvních hranách. Pokud To — T, algoritmus pracoval správně. □
Předpokládejme tedy, že Td 7^ T, a ukážeme spor, tj. že toto nemůže ve skutečnosti nastat. Označme j > 0 takový index, že se množiny To a T shodují na prvních j — 1 hranách ei,...,ej_i, ale neshodují se na ej. To znamená, že ej G T, ale ej ^ T). (Jistě nemůže nastat ej ^ T, ale ej G T).) □
Podle Důsledku 5.5 obsahuje graf na hranách ToU{ej} právě jednu kružnici C. Kružnice C však nemůže být obsažena v nalezené kostře T, a proto existuje hrana efc v C, která efc ^ T a zároveň k > j. Potom však je w(efc) > w(ej) podle našeho seřazení hran, a tudíž kostra na hranách (Td \ {efc}) U {e^} (vzniklá nahrazením hrany efc hranou ej) není horší než Td a měli jsme ji v naší úvaze zvolit místo T). To je hledaný spor. □ C
Správný pohled na předchozí důkaz by měl být následovný: Předpokládali jsme, že nalezená kostra T se s některou optimální kostrou shoduje aspoň na prvních j — 1 hranách. Poté jsme ukázali, že některou další hranu eu v (předpokládané) optimální kostře lze zaměnit hranou e3, a tudíž dosáhnout shodu aspoň na prvních j hranách. Dalšími iteracemi záměn ukážeme úplnou shodu naší nalezené kostry T s některou optimální kostrou. V našem důkaze jsme se vlastně zaměřili na fakt, že ta poslední iterace záměn nemůže selhat. Nakreslete si tento důkaz obrázkem!
Petr Hliněný,  Fl MU Brno, 2013
5/16
Fl: MA010: Kostry, Hladový algoritmu:
Základní hladový algoritmus pro hledání minimální kostry grafu byl poprvé explicitně popsán Kruskalem, ale už dříve byly objeveny jeho podobné varianty, které zde jen stručně zmíníme.
Algoritmus 6.3. Jarníkův pro minimální kostru.
Hrany na začátku neseřazujeme, ale začneme kostru vytvářet z jednoho vrcholu a v každém kroku přidáme nejmenší z hran, které vedou z již vytvořeného podstromu do zbytku grafu. □
Poznámka: Tento algoritmus je velmi vhodný pro praktické výpočty a je dodnes široce používaný. Málokdo ve světě však ví, že pochází od Vojtěcha Jarníka, známého českého matematika — ve světové literatuře se obvykle připisuje Američanu Primovi, který jej objevil až skoro 30 let po Jarníkovi.
Avšak historicky vůbec první algoritmus pro problém minimální kostry (z roku 1928) byl nalezen jiným českým (brněnským) matematikem:n
Algoritmus 6.4. Borůvkův pro minimální kostru (náznak).
Toto je poněkud složitější algoritmus, chová se jako Jarníkův algoritmus spuštěný zároveň ze všech vrcholů grafu najednou.
Petr Hliněný,  Fl MU Brno, 2013
6/16
Fl: MA010: Kostry, Hladový algoritmu:
6.2   Hladový algoritmus v obecnosti
Asi nejprimitivnějším možným přístupem při řešení diskrétních optimalizačních úloh je postupovat stylem beru vždy to nejlepší, co se zrovna nabízí...
Tento postup obecně v češtině nazýváme hladovým algoritmem, i když lepší by bylo použít správnější překlad anglického "greedy" , tedy nenasystný algoritmus. A ještě hezčí české spojení by bylo "algoritmus hamouna". Jednoduše bychom jej nastínili takto:
• Postupně v krocích vyber vždy to nejlepší, co se dá (nabízí). □
• To vyžaduje zvolit uspořádání na objektech, ze kterých vybíráme. □
• Průběh a úspěch algoritmu silně závisí na tomto zvoleném uspořádání.
Jak asi každý ví, nenasystnost či hamounství nebývá v životě tím nejlepším postupem, ale kupodivu tento princip perfektně funguje v mnoha kombinatorických úlohách! Jedním známým příkladem je výše uvedené hledání minimální kostry. Jiným příkladem je třeba jednoduchý problém přidělování (uniformních) pracovních úkolů, na němž si obecné schéma hladového algoritmu ilustrujeme.
Petr Hliněný,  Fl MU Brno, 2013
7/16
Fl: MA010: Kostry, Hladový algoritmu:
Problém 6.5. Přidělení pracovních úkolů
Uvažujeme zadané pracovní úkoly, které mají přesně určený čas začátku i délku trvání. (Jednotlivé úkoly jsou tedy reprezentovány uzavřenými intervaly na časové ose.) Cílem je takové přidělení úkolů pracovníkům, aby jich celkově bylo potřeba co nejméně. Všichni pracovníci jsou si navzájem rovnocenní - uniformní, tj. každý zvládne všechno. □
Pro příklad zadání takové problému si vezměme následující intervaly úkolů:
4 •-•
1 •-•       3 •-•
2 •-•    •-• 2
1 •-•
Kolik je k jejich splnění potřeba nejméně pracovníků? nAsi sami snadno zjistíte, že 4 pracovníci stačí, viz zobrazené očíslování. Ale proč jich nemůže být méně?
Poznámka: Uvedené zadání může být kombinatoricky popsáno také jako problém optimálního obarvení daného intervalového grafu (vrcholy jsou intervaly úkolů a hrany znázorňují překrývání intervalů).
Petr Hliněný,  Fl MU Brno, 2013
8/16
Fl: MA010: Kostry, Hladový algoritmu:
Algoritmus 6.6. Hladový algoritmus rozdělení pracovních úkolů.
Problém 6.5 je vyřešen následující aplikací hladového postupu:
1. Úkoly nejprve seřadíme podle časů začátků.
2. Každému úkolu v pořadí přidělíme volného pracovníka s nejnižším číslem. □
Důkaz: Nechť náš algoritmus použije celkem k pracovníků. Dokážeme jednoduchou úvahou, že tento počet je optimální - nejlepší možný. V okamžiku, kdy začal pracovat pracovník číslo k, všichni 1, 2,..., k — 1 také pracovali (jinak bychom vzali některého z nich). V tom okamžiku tedy máme k překrývajících se úkolů a každý z nich vyžaduje vlastního pracovníka. □ C
Příklad neoptimálního přidělení pracovních úkolů dostaneme například tak, že na začátku úkoly seřadíme podle jejich časové délky. (Tj. čím delší úkol, tím dříve mu hladově přiřadíme pracovníka.)
5 •-•   •-• 3
2 •-•     2 •-•
3 •-•   •-• 4
1 •-•
Jak vidíme na obrázku, nalezené řešení není optimální - vyžaduje 5 místo 4 pracovníků. Je tedy velmi důležité, podle jakého prinicipu seřadíme objekty (úkoly) na vstupu.
Petr Hliněný,  Fl MU Brno, 2013
9/16
Fl: MA010: Kostry, Hladový algoritmu:
6.3   Pojem matroidu
Definice 6.7. Matroid na množině X, značený M — {X,M),
je takový systém M podmnožin nosné množiny X, ve kterém platí následující:
1. 0 e A/"
2. A e N a B c A => B e M
3. A, B e M a \A\ < \B\ => 3y e B \ A : A U {y} G N
Množinám ze systému M říkáme nezávislé množiny. Těm ostatním pak říkáme závislé. Nezávislým množinám, do kterých již nelze přidat žádný prvek tak, že zůstanou nezávislé, říkáme báze matroidu. □
Nejduležitější částí definice matroidu je zvýrazněný třetí bod. Přímo ukázkový příklad matroidu nám dává lineární algebra - všechny lineárně nezávislé podmnožiny vektorů tvoří matroid. Odtud také pocházejí pojmy nezávislosti a báze matroidu, které přímo odpovídají příslušným pojmům vektorového prostoru. □
Letna 6.8. Všechny báze matroidu obsahují stejné mnoho prvků.
Důkaz: Toto přímo vyplývá z třetí vlastnosti definice matroidu: Pokud nezávislá množina A má méně prvků než báze B, tak do A lze vždy přidat další prvek x tak, že zůstane A U {x} nezávislá. C
Nyní uvedeme několik poznatků o stromech, které jsou relevantní pro zavedení "grafových" matroidů.
Letna 6.9. Les na n vrcholech s c komponentami souvislosti má přesně n — c hran. □
Důkaz: Každý vrchol lesa L náleží právě jedné komponentě souvislosti z definice. Jak známo, každý strom, tj. komponenta lesa L, má o jednu hranu méně než vrcholů. Ve sjednocení c komponent tak bude právě o c méně hran než vrcholů. C
Definice: Řekneme, že podmnožina hran F C E (G) je acyklická, pokud podgraf s vrcholy V(G) a hranami z F nemá kružnici.
Lema 6.10. Nechi F\, F2 jsou acyklické podmnožiny hran grafu G a \Fi\ < \F2\. Pak existuje hrana f e F2 \ Fi taková, že Fi U {/} je také acyklická podmnožina. □
Důkaz: Jelikož |Fi| < I-F2I a platí Lema 6.9, má podgraf G\ tvořený hranami z Fi více komponent než podgraf G2 tvořený hranami z F2. Potom však některá hrana / e F2 musí spojovat dvě různé komponenty podgrafu G\, a tudíž přidáním / do Fi nevznikne kružnice. C
Definice: Podle Lematu 6.10 tvoří systém všech acyklických podmnožin hran v (libovolném) grafu G matroid. Tento matroid nazýváme matroidem kružnic grafu G. V analogií s grafy používáme název kružnice pro minimální závislé množiny matroidu.
□
Dva příklady matroidu jsou hezky ilustrovány v následujícím obrázku, který ukazuje, jak hrany grafu K4 vlevo odpovídají vektorům v matroidu kružnic vpravo. Cáry (zvané "přímky") v pravém schématu vyznačují lineární závislosti mezi vektory; tj. nezávislé jsou ty trojice bodů, které neleží na žádné společné "přímce".
Abstraktní hladový algoritmus
V praxi se matroid obvykle nezadáva výčtem všech nezávislých množin, protože těch je příliš mnoho (až 2™ pro n-prvkovou množinu X).
Místo toho bývá dána externí funkce pro testování nezávislosti dané podmnožiny. □
Algoritmus 6.11. Nalezení minim, báze matroidu — hladový algoritmus.
vstup: množina X s váhovou funkcí w : X —>• R,
matroid na X určený externí funkcí nezavisla(Y); c
setřídit X=(x[l] ,x[2] , . . . ,x[n] ) tak,
aby w [x [1] ] <=. . . <=w [x [n] ] ;
B = 0;
for (i=l; i<=n; i++)
if (nezavisla(BU{x[i]})) B = B U {x [i]};
výstup:   báze B daného matroidu s min. součtem ohodnocení vzhledem k w.
Poznámka: Pokud X v tomto algoritmu je množina hran grafu, w váhová funkce na hranách a nezávislost znamená acyklické podmnožiny hran (matroid kružnic grafu), pak Algoritmus 6.2 je přesně instancí Algoritmu 6.11.
Věta 6.12. Algoritmus 6.11 (hladový algoritmus) pro danou nosnou množinu X s váhovou funkcí w : X —>• R a pro daný matroid M na X správně najde bázi v M s nejmenším součtem vah. □
Důkaz: Z definice matroidu je jasné, že k výsledné množině B již nelze přidat další prvek, aby zůstala nezávislá, proto je B báze. Seřaďme si prvky X podle vah jako v algoritmu w(x[l]) < ••• < w(x[n]). Nechť indexy íi,Í2, ■ ■ ■ ,ík určují vybranou k-prvkovou bázi B v algoritmu a nechť indexy j\,J2, ■ ■ ■ ,jk vyznačují (třeba jinou?) bázi ... ,2ľ[jfc]} s nejmenším možným součtem vah. □
Vezměme nejmenší r > 1 takové, že w(x[zr]) ^ w(x[jr]). Potom nutně w(x[zr]) < w(x[jr]), protože náš algoritmus je "hladový" a bral by menší w(x[jr]) již dříve. Na druhou stranu, pokud by druhá báze ... , x[7fc]} dávala menší součet vah, muselo
by existovat jiné s > 1 takové, že w(x[zs]) > w(x[js]). Nyní vezměme nezávislé podmnožiny Ai — {x[íi\,..., x[ís-i]} a — {^[ji],..., aľ[js]}, kde A^ má o jeden prvek více než A\ a všechny prvky A^ mají dle předpokladu menší váhu než w(x[ís]).
Podle definice matroidu existuje y e A^ \ A\ takové, že A\ U {y} je nezávislá. Přitom samozřejmě y — x[£] pro nějaké l. Ale to není možné, protože, jak je výše napsáno, w(y) < w(x[ís]), takže by náš hladový algoritmus musel y — x[£], l < ís vzít dříve do vytvářené báze B než vzal x[is]. Proto jiná báze s menším součtem vah než nalezená B neexistuje. C
6.4   Kdy hladový algoritmus (ne)pracuje správně
Jak ukážeme, funkčnost hladového algoritmu je přímo svázána s matroidy.
Věta 6.13. Nechí X je nosná množina se systémem "nezávislých" podmnožin JV splňující podmínky (1,2) Definice 6.7. Pokud pro jakoukoliv váhovou funkci w : X —>• R najde Algoritmus 6.11 optimální nezávislou množinu z N, tak M splňuje také podmínku (3), a tudíž tvořímatroid na X. □
Důkaz: Tvrzení dokazujeme sporem. Předpokládejme, že vlastnost (3) neplatí pro dvojici nezávislých množin A, B, tj. že \A\ < \B\, ale pro žádný prvek y e B \ A není A U {y} nezávislá. Necht \A\ — a, \B\ — b, kde 2b > 2a + 1. Zvolíme následující ohodnocení
• w(x) — —2b pro x E A,
• w(x) — —2a — 1 pro x e B \ A,
• w(x) — 0 jinak.□
Hladový algoritmus přirozeně najde bázi B\ obsahující A a disjunktní s B \ A podle našeho předpokladu. Její ohodnocení je vj{B\) — —2ab. Avšak optimální bází je v tomto případě jiná B^ obsahující celé B a mající ohodnocení nejvýše wiB^) < (—2a — 1)6 — —2ab — b < w(Bi). To je ve sporu s dalším předpokladem, že i při námi zvoleném ohodnocení w nalezne hladový algoritmus optimální bázi. Proto je sporný náš předpoklad o množinách A, B a podmínka (3) je splněna. C
Příklad 6.14. Při následujících dvou použitích paradigmatu hladového algoritmu dojde k situacím, kdy získaný výsledek může být zcela jiný než optimální odpověď.
Obarvení grafu. Problém obarvení grafu žádá přiřazení co nejméně barev vrcholům tak, aby sousední dvojice dostaly různé barvy. Obecně hladově barvíme graf tak, že ve zvoleném pořadí vrcholů každému následujícímu přidělíme první volnou barvu. □
Třeba v nakreslené cestě délky 3 můžeme barvit hladově v pořadí od vyznačených krajních vrcholů, a pak musíme použít 3 barvy místo optimálních dvou.
Vrcholové pokrytí. Problém vrcholového pokrytí se ptá na co nejmenší podmnožinu C vrcholů daného grafu takovou, že každá hrana má alespoň jeden konec v C. Přirozeným hladovým postupem by bylo vybírat od vrcholů nejvyšších stupňů ty, které sousedíš doposud nepokrytými hranami. Bohužel tento postup také obecně nefunguje.
Z