LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Grafy a grafové algoritmy III.

Tento článek volně navazuje na článek Grafy a grafové algoritmy II, ve kterém byl řešen problém nalezení minimální kostry grafu. Tento článek se také zabývá minimální kostrou, tentokrát je ale minimální kostra hledána na orientovaném grafu, k čemuž slouží Edmondsův algoritmus.

22.4.2011 00:00 | Petr Sklenička | Články autora | přečteno 9856×

Úvod do orientovaných grafů

Z minulých článků už je nám znám pojem graf, vážený (ohodnocený graf), kostra grafu apod. Doposud jsme však neměli možnost setkat se s tzv. orientovanými grafy. Pojďme si tedy tento pojem neformálně přiblížit.

Doposud jsme se setkali s takovými grafy, že pokud mezi libovolnou dvojicí vrcholů a a b vedla hrana, znamenalo to, že bylo možné "jít" v grafu jak z vrcholu a do b, tak i opačně, tedy z b do a. U orientovaných grafů toto již není možné. U každé hrany je totiž uveden i její směr. Ohodnotíme-li navíc každou hranu (čili určíme její váhu) dostaneme ohodnocený orientovaný graf. Ještě jednou tedy podotýkám následující:

Hrana (u, v) v orientovaném grafu G začíná ve vrcholu u a končí (též směřuje) ve vrcholu v. Opačná hrana, tedy (v, u) je jiná než hrana (u, v).

Minimální kostra orientovaného grafu

Myslím, že nyní je pojem orientovaného grafu jasný, proto přejdeme dále. Náplní tohoto článku je algoritmus, který dokáže najít minimální kostru takového grafu. Jistě si vzpomenete, že v minulém článku jsme také hledali kostru, jednalo se však o neorientované grafy. Ukázali jsme si Kruskalův a Jarníkův algoritmus - ani jeden z nich na orientovaném grafu nefunguje. Obecně vzato, nalezení minimální kostry orientovaného grafu je úkol o poznání složitější a náročnější, než hledání minimální kostry neorientovaného grafu, což je pak samozřejmě vidět i na celé implementaci. Algoritmus, který řeší náš problém, se nazývá Edmondsův algoritmus. Než však přejdeme k samotnému algoritmu, podívejme se ještě na to, jak vypadá kostra orientovaného váženého grafu.

Všimněte si, že jeden z uzlů je označen červenou barvou. Tomuto uzlu se říká kořen. Je nutné mít na paměti, že kostra grafu je strom (pozn.: Pokud jste nečetli článek Grafy a grafové algoritmy II, doporučuji si jej přečíst, neboť tam je vysvětleno, co je to strom, kostra, minimální kostra apod). Otázkou tedy je, co je to kořen. Neformálně řečeno, je to uzel, ze kterého celý výsledný strom "vyrůstá". Lze jej také pokládat za začátek stromu. Kořen nemá žádného rodiče, má pouze potomky, kteří zase mají své potomky a tak dále. Způsob, jakým v nějakém stromu najít vhodný uzel, který by reprezentoval kořen, zde rozepisovat nebudu, pouze naznačím, že to souvisí s nalezením tzv. centra stromu. Nyní se vraťme k algoritmu.

Nejprve si ujasněme, jakým způsobem uložíme vážený orientovaný graf do počítače. Není to nikterak složité, postačí nám k tomu obyčejné, dvourozměrné pole. Nazvěme jej G[i][j], kde i odpovídá počtu hran a j bude rovno třem.

Počáteční vrcholKoncový vrcholVáha
022
015
041
134
153
232
3411
418
421
509

Uvedená tabulka zachycuje, jakým způsobem budou data uspořádána v dvourozměrném poli. V řádku je nejprve uveden vrchol, ve kterém hrana začíná, následuje koncový vrchol a poté váha hrany. Můžete si všimnout, že tabulka odpovídá grafu, který je na obrázku výše. Celý kód, který je mimořádně v jazyce Java, si můžete stáhnout zde. Podotýkám, že v kódu je použito několik datových struktur - u každé struktury je komentář, k čemu slouží. Celý algoritmus je poměrně komplikovaný, proto pokud mu chcete opravdu porozumět, nestačí si jen přečíst následující stručný popis, ale také je nutné projít si kód a snažit se ho pochopit, což nemusí být až tak snadné. Nakonec ale musím přiznat, že mě v tuto chvíli nenapadá přilíš reálných situací, kdy by bylo potřeba tento algoritmus použít, narozdíl třeba od algoritmů, které hledají kostru neorientovaného grafu, nebo slouží k nalezení nejkratší cesty v grafu.

Celý algoritmus lze rozdělit na dvě části. V první části se všechny uzly nachází v roots (obsahuje komponenty, do kterých zatím nevede hrana). Z roots se náhodně vybere nějaký uzel (x) a pro tento uzel se také vybere nejkratší hrana, která do něj vede (vrchol, ze kterého hrana vychází, označíme y). Jestliže taková hrana neexistuje, potom je jasné, že uzel bude kořen aktuálního stromu. Pokud taková hrana existuje, algoritmus tuto hranu buď zpracuje, nebo se vrátí na začátek a vybere jiný uzel. Rozhodujícím faktorem, který z těchto dvou případů nastane, je otázka, zda jsou uzly x a y ve stejné silné komponentě. Pokud ano, algoritmus se vrací a vybírá jiný uzel. Jestliže jsou ale uzly x a y v různých slabých komponentách, algoritmus tyto komponenty spojí a vrátí se na začátek. Pokud jsou uzly x a y ve stejné, slabé komponentě, pak vznikne nová silná komponenta. V tuto chvíli je nutné vstupním hranám snížit jejich prioritu o rozdíl aktuální váhy a maximální váhy, přičemž maximální váha je váha maximální hrany. Po přehodnocení hran se sloučí haldy hran uzlů v nové komponentě a algoritmus se vrátí opět na začátek.

Celá první část algoritmu defakto udělala to, že vyfiltrovala "zbytečné" hrany, čili ty, které v kostře zcela jistě nebudou. Máme tedy pouze seznam hran, které v kostře být mohou. Dále máme množinu kořenových uzlů minimálního lesa (les je jednoduchý graf, který neobsahuje kružnice). Dále zavedeme prázdnou množinu hran, např. A. Poté stačí opakovat následující kroky (1, 2, 3) do doby, dokud množina kořenových uzlů minimálního lesa a množina fRoots (kořenové uzly lesa) nebudou prázdné.

  1. Pokud je množina kořenových uzlů minimálního lesa neprázdná, odstraníme jeden z jejích prvků. Pokud je prázdná, pak odstraníme vrchol z množiny fRoots a přidáme jej do množiny A.
  2. Dále algoritmus identifikuje cestu mezi listem (vrchol, který nemá žádné potomky) lesa (tj. vrchol z množiny fRoots) a kořenem lesa (opět v fRoots).
  3. Nakonec odstraníme z fRoots ty uzly (a samozřejmě z nich vycházející hrany), které byly identifikovány v předchozím kroku. (2)

Několik slov závěrem

Jistě sami vidíte, že Edmondsův algoritmus je například v porovnání s Kruskalovým algoritmem mnohonásobně složitější. To je samozřejmě dáno tím, že Kruskalův algoritmus nebere v úvahu, že by hrany mohly být orientované. Oproti tomu ale nalezení kostry neorientovaného grafu je přece jen úkol, který se vyskytuje častěji, než úkol nalezení kostry orientovaného grafu. Proto si osobně myslím, že není nikterak nutné umět napsat Edmondsův algoritmus "z hlavy na jeden zátah". Na druhou stranu určitě není na škodu vědět, že takový algoritmus existuje, vědět k čemu slouží a alespoň trochu tušit, jak zhruba funguje.

Verze pro tisk

pridej.cz

 

DISKUZE

Nejsou žádné diskuzní příspěvky u dané položky.



Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

27.8.2016 8:55 /Delujek
Dnes po 4 letech komunitního vývoje vyšla diaspora 0.6.0.0
diaspora* je open-source, distribuovaná sociální síť s důrazem na soukromý
Více v oficiálním blog-postu
Přidat komentář

24.8.2016 6:44 /Ondřej Čečák
Poslední týden CFP LinuxDays 2016; pokud byste rádi přednášeli na LinuxDays 2016 8. a 9. října v Praze, můžete svůj příspěvek přihlásit, následovat bude veřejné hlasování.
Přidat komentář

9.8.2016 22:56 /Petr Ježek
Zařazení souborového systému reiser4 do jádra 4.7 znamená konečně konec patchování jádra jen kvůli možnosti použít reiser4.
Přidat komentář

12.7.2016 13:14 /František Kučera
Spolek OpenAlt zve na 130. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 21. července od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

11.7.2016 16:53 /Redakce Linuxsoft.cz
Konference LinuxDays hledá přednášející. Přihlášky poběží do konce prázdnin, v září bude hlasování a program. Více na https://www.linuxdays.cz/2016/cfp/.
Přidat komentář

8.5.2016 17:19 /Redakce Linuxsoft.cz
PR: Dne 26.5.2016 proběhne v Praze konference Cloud computing v praxi. Tématy bude např. nejnovější trendy v oblasti cloudu a cloudových řešení, cloudové služby, infrastruktura cloudu, efektivní využití cloudu, možné nástrahy cloudů a jak se jim vyhnout
Přidat komentář

21.4.2016 8:01 /František Kučera
Spolek OpenAlt zve na 127. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 28. dubna od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

2.3.2016 22:41 /Ondřej Čečák
Letošní ročník konference InstallFest již tento víkend!
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

12.8.2016 11:51 / Josef Zapletal
Jak udělat HTML/Javascript swiping gallery do mobilu?

8.8.2016 14:58 / Adams
fairies for hire

28.7.2016 15:51 / pepan
Re: NetBeans vs Eclipse

10.6.2016 21:10 / pavel riha
FreeBSD 10.3 a virtualizace

8.6.2016 21:56 / Milan Gallas
Nevalidní prefix m

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2016) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze