Petr Hliněný, FI MU Brno 1 FI: MA010: Kostry, Hladový algoritmus
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í: 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. 2
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 algo-
ritmus.
* Obecné pojetí hladového algoritmu.
* Matroidy ­ struktury, na nichž hladový algoritmus vždy funguje.
Petr Hliněný, FI MU Brno 2 FI: MA010: Kostry, Hladový algoritmus
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žné celkové ohodnocení. Formálně
MST = min
kostra T G


eE(T )
w(e)

 .
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ý, FI MU Brno 3 FI: MA010: Kostry, Hladový algoritmus
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.
s s s s
s s s s
1 4 2
343
12
1 2
1
3
2
s s s s
s s s s
1 4 2
343
12
1 2
1
3
2
2
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(e1)  w(e2)  . . .  w(em). 2
­ Začneme s prázdnou množinou hran T =  pro kostru.
­ Pro i = 1, 2, . . . , m vezmeme hranu ei a pokud T  {ei} nevytváří kružnici,
přidáme ei do T . Jinak ei "zahodíme". 2
­ Na konci množina T obsahuje hrany minimální kostry váženého grafu G, w.
Petr Hliněný, FI MU Brno 4 FI: MA010: Kostry, Hladový algoritmus
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. . .
s s s s
s s s s
1 4 2
343
12
1 2
1
3
2
s s s s
s s s s
1 4 2
343
12
1 2
1
3
2
s s s s
s s s s
1 4 2
343
12
1 2
1
3
2
s s s s
s s s s
1 4 2
343
12
1 2
1
3
2
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ý, FI MU Brno 5 FI: MA010: Kostry, Hladový algoritmus
Důkaz správnosti Algoritmu 5.2:
Nechť T je množina hran získaná v Algoritmu 5.2 a nechť hrany jsou již seřazené
w(e1)  w(e2)  . . .  w(em). Vezměme množinu hran T0 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 T0 = T , algoritmus pracoval správně. 2
Předpokládejme tedy, že T0 = T , a ukážeme spor, tj. že toto nemůže ve skutečnosti
nastat. Označme j > 0 takový index, že se množiny T0 a T shodují na prvních j - 1
hranách e1, . . . , ej-1, ale neshodují se na ej. To znamená, že ej  T , ale ej  T0.
(Jistě nemůže nastat ej  T , ale ej  T0.) 2
Podle Důsledku 4.5 obsahuje graf na hranách T0{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 ek v C, která
ek  T a zároveň k > j. Potom však je w(ek)  w(ej) podle našeho seřazení hran, a
tudíž kostra na hranách T0 \ {ek}  {ej} (vzniklá nahrazením hrany ek hranou ej)
není horší než T0 a měli jsme ji v naší úvaze zvolit místo T0. To je hledaný spor. 2 2
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 ek v (předpokládané) optimální kostře lze zaměnit hranou
ej, 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ý, FI MU Brno 6 FI: MA010: Kostry, Hladový algoritmus
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 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řidáme nejmenší z hran, které vedou z již vytvořeného podstromu do
zbytku grafu. 2
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:2
Algoritmus 5.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ý, FI MU Brno 7 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 úloh je
postupovat stylem beru vždy to nejlepší, co se zrovna nabízí. . .
2Tento 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í). 2
* To vyžaduje zvolit uspořádání na objektech, ze kterých vybíráme. 2
* 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ý, FI MU Brno 8 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é ú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. 2
Pro příklad zadání takové problému si vezměme následující intervaly úkolů:
s s
s s s s
s s s s
s s
1
2
1
3
4
2
Kolik je k jejich splnění potřeba nejméně pracovníků? 2Asi 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ý, FI MU Brno 9 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. Ú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. 2
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. 2 2
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.)
s s
s s s s
s s s s
s s
s s
2
3
1
2
5
4
3
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ý, FI MU Brno 10 FI: MA010: Kostry, Hladový algoritmus
5.3 Pojem matroidu
Definice 5.7. Matroid na množině X, značený M = (X, N),
je takový systém N podmnožin nosné množiny X, ve kterém platí následující:
1.   N
2. A  N a B  A  B  N
3. A, B  N a |A| < |B|  y  B \ A : A  {y}  N
Množinám ze systému N ří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. 2
Nejdůlež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. 2
Lema 5.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  {x} nezávislá. 2
Petr Hliněný, FI MU Brno 11 FI: MA010: Kostry, Hladový algoritmus
Nyní uvedeme několik poznatků o stromech, které jsou relevantní pro zavedení "grafových"
matroidů.
Lema 5.9. Les na n vrcholech s c komponentami souvislosti má přesně n - c hran. 2
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ů. 2
Definice: Řekneme, že podmnožina hran F  E(G) je acyklická, pokud podgraf s
vrcholy V (G) a hranami z F nemá kružnici.
Lema 5.10. Nechť F1, F2 jsou acyklické podmnožiny hran grafu G a |F1| < |F2|. Pak
existuje hrana f  F2 \ F1 taková, že F1  {f} je také acyklická podmnožina. 2
Důkaz: Jelikož |F1| < |F2| a platí Lema 5.9, má podgraf G1 tvořený hranami z F1 více
komponent než podgraf G2 tvořený hranami z F2. Potom však některá hrana f  F2
musí spojovat dvě různé komponenty podgrafu G1, a tudíž přidáním f do F1 nevznikne
kružnice. 2
Petr Hliněný, FI MU Brno 12 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ý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.
2
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. Čá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".
K4
a b
c
d
ef

a bc
d
e
f
1
0
0
0
1
0
1
1
0
1
1
1
0
0
1
1
0
1
Petr Hliněný, FI MU Brno 13 FI: MA010: Kostry, Hladový algoritmus
Abstraktní hladový algoritmus
V praxi se matroid obvykle nezadává výčtem všech nezávislých množin, protože těch
je příliš mnoho (až 2n
pro n-prvkovou množinu X).
Místo toho bývá dána externí funkce pro testování nezávislosti dané podmnožiny. 2
Algoritmus 5.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); 2
setřídit X=(x[1],x[2],...,x[n]) tak,
aby w[x[1]]<=...<=w[x[n]];
B = ;
for (i=1; i<=n; i++)
if (nezavisla(B{x[i]}))
B = B  {x[i]};
výstup: báze B daného matroidu s min. součtem ohodnocení vzhledem k w. 2
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 5.2
je přesně instancí Algoritmu 5.11.
Petr Hliněný, FI MU Brno 14 FI: MA010: Kostry, Hladový algoritmus
Věta 5.12. Algoritmus 5.11 (hladový algoritmus) pro danou nosnou množinu X s
váhovou funkcí w : X  R a pro daný matroid N na X správně najde bázi v N s
nejmenším součtem vah. 2
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[1])  . . .  w(x[n]). Nechť indexy i1, i2, . . . , ik určují vybranou kprvkovou
bázi B v algoritmu a nechť indexy j1, j2, . . . , jk vyznačují (třeba jinou?) bázi
{x[j1], . . . , x[jk]} s nejmenším možným součtem vah. 2
Vezměme nejmenší r  1 takové, že w(x[ir]) = w(x[jr]). Potom nutně w(x[ir]) <
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[j1], . . . , x[jk]} dávala menší součet vah, muselo
by existovat jiné s  1 takové, že w(x[is]) > w(x[js]). Nyní vezměme nezávislé
podmnožiny A1 = {x[i1], . . . , x[is-1]} a A2 = {x[j1], . . . , x[js]}, kde A2 má o jeden
prvek více než A1 a všechny prvky A2 mají dle předpokladu menší váhu než w(x[is]).
2
Podle definice matroidu existuje y  A2 \ A1 takové, že A1  {y} je nezávislá. Přitom
samozřejmě y = x[] pro nějaké . Ale to není možné, protože, jak je výše napsáno,
w(y) < w(x[is]), takže by náš hladový algoritmus musel y = x[],  < is 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. 2
Petr Hliněný, FI MU Brno 15 FI: MA010: Kostry, Hladový algoritmus
5.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 5.13. Nechť 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 váhovou funkci w : X  R
najde Algoritmus 5.11 optimální nezávislou množinu z N , tak N splňuje také podmínku
(3), a tudíž tvoří matroid na X. 2
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  B \ A není
A  {y} nezávislá. Nechť |A| = a, |B| = b, kde 2b > 2a + 1. Zvolíme následující
ohodnocení
* w(x) = -2b pro x  A,
* w(x) = -2a - 1 pro x  B \ A,
* w(x) = 0 jinak.2
Hladový algoritmus přirozeně najde bázi B1 obsahující A a disjunktní s B \ A podle
našeho předpokladu. Její ohodnocení je w(B1) = -2ab. Avšak optimální bází je v
tomto případě jiná B2 obsahující celé B a mající ohodnocení nejvýše w(B2)  (-2a-
1)b = -2ab - b < w(B1). 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. 2
Petr Hliněný, FI MU Brno 16 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. 2Problé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. 2
s s s sf f
1 2 3 1
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í. 2Problé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í s doposud nepokrytými hranami. Bohužel tento postup také obecně
nefunguje.
s s s s
s s s s
sf
f f
ff
s s s s
s s s s
s
f f
ff
2