LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> 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 15459×

Ú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ů

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

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

> Poslední diskuze

31.7.2023 14:13 / Linda Graham
iPhone Services

30.11.2022 9:32 / Kyle McDermott
Hosting download unavailable

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

Více ...

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