5   Minimální kostry, Hladový algoritmus
Kromě teoretických "hrátek" maj í kostry grafů (Odd íl 4.4) následuj íc í důležité praktické použit í: Dríve jsme uvažovali spojen í v grafech cestami jdouc ími ž jednoho m ísta do druheho, ale nyn í se pod ívame na jiný žpůsob "propojovan í" vsech vrcholů grafu najednou.
Vežmeme si treba požadavky propojen í domu elektrickým rožvodem, propojen í skol internetem, atd. Zde nas ani tak nežaj ímaj í delky jednotlivých cest meži propojenými body, ale hlavne celkova delka ci cena veden í/spojen í, ktere musíme postavit. c
Nasim cílem je tedy naj ít minimaln í souvislý podgraf daneho grafu, tedy minimaln í žpusob propojen í (v daných podm ínkach), ve kterem existuj í cesty meži každou dvojic í vrcholu.
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 nichz hladový algoritmus vzdy funguje.
V
Petr Hliněný,  FI MU Brno
FI:MA010: Kostry, Hladový algoritmus
r
5.1   Hledání minimální kostry
Problém 5.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žne celkove ohodnocení. Formálne
MST =      min     j   ^ w(e) \eeE(T) )
kostra T CG  \e£E(T)
Kostra daného grafu je minimální podgraf, který zachovává souvislost každé komponenty původního grafu. Proto nam vlastné ukazuje "minimaln í propojen í" daných vrcholu, ve kterém jesté existuj í cesty mezi vsemi dvojicemi, ktere byly propojeny i puvodne.
Petr Hliněný,  FI MU Brno_2_FI: MA010: Kostry, Hladový algoritmus
Praktickou formulací problému je třeba propojení domů elektrickým rozvodem, škol internetem, atd. Jedna še tadý o zadaní, ve kterých naš zajíma predevším celková delka Ci cena propojen í, ktere je treba výtvorit. Príklad je uveden na nasleduj íc ím obrazku i š význacenou minimaln í koštrou vpravo.
3
4
3
3
4
3
Algoritmus 5.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). c
- ZaCneme s prázdnou mnoZinou hran T = 0 pro kostru.
- Pro i = 1, 2,..., m vezmeme hranu ej a pokud T U {ej} nevytvarí kruZnici, přidame ej do T. Jinak ej "zahodíme". c
- Na konci mnozina T obsahuje hrany minimainí kostry vazeneho grafu G, w.
_Petr Hliněný,  FI MU Brno_3_FI: MA010: Kostry, Hladový algoritmus
1
2
1
2
1
4
2
1
4
2
Pro ilustraci si ukazeme postup hladoveho algoritmu pro vyhledan í kostry vyse zakresleneho grafu. Hrany si nejprve serad íme podle jejich vah 1,1,1,1, 2, 2, 2, 2, 3, 3, 3,4,4.
V obrazku pmbehu algoritmu pouz ívame tluste cary pro vybrane hrany kostry a teckovane cary pro zahozene hrany. Hrany ted' postupne pridavame do kostry / zahazujeme. . .
3 4 3
*.............44 2
Z ískame tak minimaln í kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2 = 12, ktera je v tomto pr ípade (nahodou) cestou, na posledn ím obrazku vpravo.
Poznamenavame, ze pri jinem serazen í hran stejne vahy by kostra mohla vyj ít jinak, ale vzdy bude m ít stejnou velikost 12.
Petr Hlín
ny.
FI MU Brno
FI:MA010: Kostry, Hladový algoritmus
3
4
3
3
4
3
1
2
1
2
1
4
2
1
3
1
2
1
2
1
1
4
2
Důkaz správnosti Algoritmu 5.2:
Nechť T je množina hrán získaná v Algoritmu 5.2 á necht hrány jsou již seřazené
w(ei) < w(e2) < • • • < w(em). Vezmeme množinu hrán T0 te minimální kostry (mUže
jich byt více se stejnou hodnotou), která se s T shoduje ná co nejvíce prvních hránách. Pokud To = T, álgoritmus prácovál správne. □
Předpokládejme tedy, že T0 = T, á ukážeme spor, tj. že toto nemaže ve skutečnosti nástát. Ožnácme j > 0 tákovy index, že se množiny T0 á T shodují ná prvních j — 1 hránách e1,...,ej-1, ále neshodují se ná ej. To žnámená, že ej G T, ále ej G T0. (Jiste nemuže nástát ej G T, ále ej G T0.) □
Podle Dusledku 4.5 obsáhuje gráf ná hránách T0U{ej} práve jednu kružnici C. Kružnice C vsák nemuže byt obsážená v náležene kostře T, á proto existuje hráná ek v C, která ek G T á žároven k > j. Potom vsák je w(ek) > w(ej) podle náseho seřážení hrán, á tudíž kostrá ná hránách (T0 \ {ek}) U {ej} (vžniklá náhrážením hrány ek hránou ej) není horsí než T0 á meli jsme ji v násí uváže žvolit místo T0. To je hledány spor. □ □
Správný pohled na předchozí důkaz by mel být následovný: Předpokládali jsme, ze nalezená kostra T se s nekteroů optimalní kostrou shoduje aspoň na prvních j — 1 hranach. Pote jsme ůkazali, ze nekteroů dalsí hranů ek v (predpokladane) optimalní kostre lze zamenit hranoů ej, a tůd íz dosahnoůt shodů aspon na prvn ích j hranach. Dalsími iteracemi zamen ůkazeme ůplnoů shodů nasí nalezene kostry T s nekteroů optimaln í kostroů. V nasem důkaze jsme se vlastne zamerili na fakt, ze ta posledn í iterace zamňn nemůze selhat. Nakreslete si tento důkaz obrazkem!
V
Petr Hliněný,  FI MU Brno
FI:MA010: Kostry, Hladový algoritmus
Základní hladový algoritmus pro hledání minimální kostry grafu byl poprvé explicitně popsán Kruskalem, ale uz dříve byly objevený jeho podobné varianty, které zde jen struCné zmíníme.
Algoritmus 5.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řidame nejmenší z hran, které vedou z jiz vytvořeného podstromu do zbytku grafu. c
Poznámka: Tento algoritmus je velmi vhodný pro praktické výpočty a je dodnes široce používaný. Málokdo ve svete však ví, ze pochází od Vojtecha Jarníka, známeho českeho matematika — ve svetove literatuře se obvykle připisuje Americanu Primovi, který jej objevil až skoro 30 let po Jarníkovi.
Avsak historicky vubec první algoritmus pro problem minimalní kostry (z roku 1928) byl nalezen jinym Ceskym (brnenskym) matematikem:c
Algoritmus 5.4. Borůvkův pro minimální kostru (naznak).
Toto je ponřkud sloZitZjZÍ algoritmus, chova se jako Jarníkuv algoritmus spuštěný zaroveZ ze všech vrcholu grafu najednou.
Petr Hliněný,  FI MU Brno_6_FI: MA010: Kostry, Hladový algoritmus
5.2   Hladový algoritmus v obecnosti
Asi nejprimitivnějším možným přístupem při řešení diskrétních optimalizačních uloh je postupovat stýlem beru vždý to nejlepSí, co se zrovna nabízí...
□ Tento postup obecne v čestine nazývame hladovým algoritmem, i kdýž lepsí bý býlo použít spravnejsí překlad anglickeho "greedý", tedý nenasýstný algoritmus. A jeste hezčí Ceske spojení bý býlo "algoritmus hamouna". Jednoduse býchom jej nastínili takto:
• Postupne v krocích výber vždý to nejlepsí, co se da (nabízí). □
• To výzaduje zvolit uspořádání na objektech, ze kterých výbírame. □
• Prubeh a uspech algoritmu silne zavisí na tomto zvolenem uspořadaní.
Jak asi každý ví, nenasystnost ci hamounství nebývá v životě tím nejlepším postupem, ale kupodivu tento princip perfektne funguje v mnoha kombinatorických ulohach! Jedn ím žnamým příkladem je výse uvedene hledan í minimaln í kostry. Jiným příkladem je třeba jednoduchý problem pridelovan í (uniformn ích) pracovn ích ukolu, na nemž si obecne schema hladoveho algoritmu ilustrujeme.
Petr Hliněný,  FI MU Brno_7_FI: MA010: Kostry, Hladový algoritmus
Problém 5.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é úkolý jsou tedý reprezentovaný uzavřenými intervaly na časove ose.) Cílem je takove pěideleníukolu pracovníkum, abýjich celkove býlo potřeba co nejmene. Všichni pracovníci jsou si navzajem rovnocenní - uniformní, tj. kaědý zvladne všechno. c
Pro příklad zadán í takove problému si vezmeme nasleduj íc í intervaly úkolů:
4 •-•
1 •-•       3 •-•
2 •-•    •-• 2
1 •-•
Kolik je k jejich splnen í potřeba nejmene pracovn íků? nAsi sami snadno zjist íte, Ze 4 pracovn íci staC í, viz zobrazene oc íslovan í. Ale proc jich nemůZe byt mene?
Poznámka: Uvedene zadan í múze byt kombinatoricky popsano takejako problem optimaln ího obarven ídaneho intervaloveho grafu (vrcholy jsou intervaly úkolů a hrany znazorňuj í prekryvan í intervalů).
Petr Hliněný,  FI MU Brno_8_FI: MA010: Kostry, Hladový algoritmus
Algoritmus 5.6. Hladový algoritmus rozdělení pracovních úkolů.
Problém 5.5 je vyřešen následující aplikací hladového postupu:
1. U koly nejprve seřadíme podle CasU zaCátkU.
2. KaZdemu úkolu v pořadí přidělíme volního pracovníka s nejniZsím Cí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 žacal pracovat pracovník císlo k, všichni 1, 2,..., k — 1 take pracovali (jinak bychom vžali nektereho ž nich). V tom okamžiku tedy mame k prekrývaj íc ích se ukolu a každý ž nich vyžaduje vlastn ího pracovn íka. □ □
Příklad neoptimaln ího přidělen í pracovn ích úkolů dostaneme například tak, ze na začátku úkoly seřad íme podle jejich časove delky. (Tj. č ím delS í úkol, t ím dříve mu hladove přiřad íme pracovn íka.)
5 •-•   •-• 3
2 •
• 4
Jak vid íme na obřazku, nalezene řeSen í nen í optimaln í - vyZaduje 5 m ísto 4 přacovn íků. Je tedy velmi důlezite, podle jakeho přinicipu seřad íme objekty (úkoly) na vstupu.
Petr Hlín
ny.
FI MU Brno
FI:MA010: Kostry, Hladový algoritmus
5.3   Pojem mátroidu
Definice 5.7. Mátroid na množině X, značený M = (X,N),
je takový sýstěm N podmnožin nosně množiny X, ve kterěm platí následující:
1. 0GN
2. A G N a B c A == B G N
3. A, B G N a |A| < |B| == 3y G B \ A : A U {y} G N
Množinam ze sýstemu N ríkame nezávislé množiny. Tem ostatním pak ríkame závisle. Nezavislým množinám, do kterých již nelze přidat Zadný prvek tak, že zUstanou nezávisle, ríkame báze matroidu. c
Nejduležitéjsí castí definice matroidu je zvyraznény tretí bod. Prímo ukazkovy příklad matroidu nám dává lineární algebra - vsechny lineárne nezávislé podmnoziny vektoru tvorí matroid. Odtud také pochazejí pojmy nezavislosti a baze matroidu, které prímo odpovídají príslusnym pojmum vektorového prostoru. c
Lemá 5.8. Všechny báze matroidu obsahujístejne mnoho prvku.
Dukáz: Toto prímo výplýva z tretí vlastnosti definice matroidu: Pokud nezavisla množina A ma mene prvku než baze B, tak do A lze vždý přidat dalsí prvek x tak, že
zustane A U {x} nezavisla.
□
V
Petr Hliněný,  FI MU Brr
FI: MA010: Kostry, Hladový algoritmus
Nyn í uvedeme nekolik požnatku o stromech, ktere jsou relevantn í pro žaveden í "grafových" matroidu.
Lema 5.9. Les na n vrcholech s c komponentami souvislosti má presne n — c hran. c
DUkaz: Každý vrchol lesa L nalež í prave jedne komponente souvislosti ž definice. Jak žnamo, každý strom, tj. komponenta lesa L, ma o jednu hranu mene než vrcholu. Ve sjednocen í c komponent tak bude prave o c mene hran než vrcholu. □
Definice: Řekneme, že podmnožina hran F C E (G) je acyklická, pokud podgraf s vrcholy V (G) a hranami ž F nema kružnici.
Lema 5.10. Necht Fi,F2 jsou acyklické podmnožiny hran grafu G a \Fi\ < \F2\. Pak existuje hrana f G F2 \ F\ taková, že F\ U {/} je take acyklická podmnožina.
DUkaz: Jelikož \Fi\ < \F2\ a plat í Lema 5.9, ma podgraf Gi tvořený hranami ž Fi více
komponent než podgraf G2 tvořený hranami ž F2. Potom vsak nektera hrana / G F2 mus í spojovat dve ružne komponenty podgrafu Gi, a tud íž pri dan ím / do Fi nevžnikne
kružnice.
□
V
Petr Hliněný,  FI MU Brr
FI: MA010: Kostry, Hladový algoritmus
Definice: Podle Lematu 5.10 tvoří systém všech acyklických podmnožin hran v (libovolném) grafu G matroid. Tento matroid nazývame matroidem kružnic grafu G. V analogií s grafy používame nažev kružnice pro minimainí žavisle 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 í vektomm v matroidu kruZnic vpravo. Čary (zvane "prímky") v pravem schematu vyznaCuj í linearn í zavislosti mezi vektory; tj. nezavisle jsou ty trojice bodu, ktere nelez í na zadne spolecne "prímce".
Abstraktn í hladový algoritmus
V praxi se matroid obvykle nezadává výčtem všech nezávislých množin, protože tech je příliš mnoho (až 2n pro n-prvkovou množinu X).
M ísto toho býva dana extern í funkce pro testovan í nezavislosti dane podmnožiny. c
Algoritmus 5.11. Nalezen í minim. baze matroidů - hladový algoritmus.
vstup: mnoěina X s vahovou funkcíw : X — R,
matroid na X urcený externí funkcí nezavisla(Y); c
setřídit X=(x[1],x[2],...,x[n]) tak,
abý w[x[1]]<=. . . <=w [x [n] ] ;
B = 0;
for (i=1; i<=n;
if (nezavisla(BU{x[i]|)) B = B U{x[i]};
vystup:   baze B daneho matroidu s min. souětem ohodnocení vzhledem k w. c
Poznamka: Pokud X v tomto algoritmu je mnozina hran grafu, w vahova funkce na hranach a nezavislost znamena acyklicke podmnoziny hran (matroid kruznic grafu), pak Algoritmus 5.2 je presne instanc í Algoritmu 5.11.
Petr Hliněný,  FI MU Brno_13_FI: MA010: Kostry, Hladový algoritmus
Věta 5.12. Algoritmus 5.11 (hladový algoritmus) pro danou nosnou mnoZinu X s váhovou funkcí w : X — R a pro daný matroid N na X správne najde bízi v N s nejmensím součtem vah. □
Důkaz: Z definice matroidu je jasne, že k vysledne množine B již nelže přidat dalsí prvek, aby žustala nežavisla, proto je B baže. Serad'me si prvky X podle vah jako v algoritmu w(x[1]) < ••• < w(x[n]). Necht indexy «i, *2,..., *fc urcují vybranou k-prvkovou baži B v algoritmu a nechť indexy j1, j2,..., jk vyžnacují (třeba jinou?) baži ..., x[jk]} s nejmensím možnym souctem vah. □
Vežmeme nejmensí r > 1 takove, že w(x[ir]) = w(x[jr]). Potom nutne w(x[ir]) < w(x[jr]), protože nas algoritmus je "hladovy" a bral by mensí w(x[jr]) již dříve. Na druhou stranu, pokud by druha baže {x ji],..., x[jk]} davala mensí soucet vah, muselo by existovat jine s > 1 takove, že w(x[is]) > w(x[js]). Nyní vežmeme nežavisle podmnožiny A1 = {x[i1],..., x[is-1]} a A2 = {x[j1 ],..., x[js]}, kde A2 ma o jeden prvek více než A1 a vsechny prvky A2 mají dle předpokladu mensí vahu než w(x[is]).
Podle definice matroidu existuje y G A2 \ A1 takove, že A1 U {y} je nežavisla. Přitom samožřejme y = x[l] pro nejake l. Ale to není možne, protože, jak je vyse napsano, w(y) < w(x[is]), takže by nas hladovy algoritmus musel y = x[l], l < is vžít dříve do vytvarene baže B než vžal x[is]. Proto jina baže s mensím souctem vah než naležena B neexistuje. □
Petr Hlinený,  FI MU Brno_14_FI: MA010: Kostry, Hladový algoritmus
5.4   Kdý hladový algoritmus (ne)pracuje spravne
Jak ukazeme, funkcnost hladoveho algoritmu je přímo svazana s matroidý.
Veta 5.13. Necht X je nosná množina se systémem "nezávislých" podmnožin N splňující podmínky (1,2) Definice 5.7. Pokud pro jakoukoliv vahovou funkci w : X — R najde Algoritmus 5.11 optimalné nezavislou množinu z N, tak N splňuje také podmínku (3), a tudíž tvořé matroid na X. □
DUkaz: Tvrzen í dokazujeme sporem. Predpokladejme, ze vlastnost (3) neplat í pro dvojici nezavislých mnozin A, B, tj. ze |A| < |B|, ale pro zadný prvek y G B \ A nen í A U {y} nezavisla. Nechť |A| = a, |B| = b, kde 2b > 2a + 1. Zvol íme nasleduj ící ohodnocen í
• w(x) = —2b pro x G A,
• w(x) = —2a — 1 pro x G B \ A,
• w(x) = 0 jinak.□
Hladový algoritmus prirozene najde bazi Bi obsahuj íc í A a disjunktn í s B \ A podle naseho předpokladu. Jej í ohodnocen í je w(B1) = —2ab. Avsak optimaln í baz í je v tomto případe jina B2 obsahuj íc í cele B a maj íc í ohodnocen í nejvýse w(B2) < (—2a — 1)b = —2ab — b < w(B1). To je ve sporu s dalsím predpokladem, ze i při nami zvolenem ohodnocen í w nalezne hladový algoritmus optimaln í bazi. Proto je sporný nas předpoklad o mnozinach A, B a podm ínka (3) je splnena. □
Petr Hliněný,  FI MU Brno_15_FI: MA010: Kostry, Hladový algoritmus
Příklad 5.14. Nakonec uvádíme dvě ukázky, ve kterých hladový algoritmus selže:
Obarvení grafu. □Problém obarvení grafu žádá přiřazení co nejméně barev vrcholům tak, aby sousední dvojice dostaly různe barvy. Obecne hladove barvíme graf tak, že ve zvolenem pořadí vrcholů každemu nasledujícímu pridelíme první volnou barvu. □
®-•-•-®
12 3 1
Třeba v nakreslene ceste delky 3 mužeme barvit hladove v pořadí od vyznacenych krajn ích vrcholu, a pak mus íme pouz ít 3 barvy m ísto optimaln ích dvou.
Vrcholové pokrytí. □Problem vrcholoveho pokrytí se pta na co nejmensí podmnozinu C vrcholu daneho grafu takovou, ze kazda hrana ma alespon jeden konec v C. Přirozeným hladovým postupem by bylo vybírat od vrcholu nejvyssích stupnu ty, ktere sousedí s doposud nepokrytymi hranami. Bohuzel tento postup take obecne nefunguje.
•-®    ®-» »-® ®-«
•
□
Petr Hliněný,  FI MU Brn
FI: MA010: Kostry, Hladový algoritmus