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

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

15.1.2018 0:51 /František Kučera

První letošní pražský sraz se koná již tento čtvrtek 18. ledna od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Vítáni jsou všichni příznivci svobodného softwaru a hardwaru, ESP32, DIY, CNC, SDR nebo dobrého piva. Prvních deset účastníků srazu obdrží samolepku There Is No Cloud… just other people's computers. od Free Software Foundation.


Přidat komentář

14.11.2017 16:56 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tradičně první čtvrtek před třetím pátkem v měsíci: 16. listopadu od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.11.2017 11:06 /Redakce Linuxsoft.cz
PR: 4. ročník odborné IT konference na téma Datová centra pro business proběhne již ve čtvrtek 23. listopadu 2017 v konferenčním centru Vavruška, v paláci Charitas, Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00. Konference o návrhu, budování, správě a efektivním využívání datových center nabídne odpovědi na aktuální a často řešené otázky, např Jaké jsou aktuální trendy v oblasti datových center a jak je využít pro vlastní prospěch? Jak zajistit pro firmu či jinou organizaci odpovídající služby datových center? Podle jakých kritérií vybrat dodavatele služeb? Jak volit součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně spravovat datové centrum? Jak eliminovat možná rizika? apod.
Přidat komentář

13.9.2017 8:00 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

15.5.2017 23:50 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

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

> Poslední diskuze

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

31.8.2017 12:11 / Jaromir Obr
Re: ukůládání dat ze souboru

30.7.2017 11:12 / Jaromir Obr
Národní znaky

Více ...

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