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

Ú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.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ář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

27.2.2017 22:12 /František Kučera
Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
Přidat komentář

18.1.2017 0:49 /František Kučera
Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
Přidat komentář

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

> Poslední diskuze

1.8.2017 7:32 / Cassidy
structural consultants

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

27.7.2017 12:24 / Jaromir Obr
Cteni/zapis

26.7.2017 21:12 / Jaromir Obr
Podminka

15.6.2017 9:34 / Ondřej Havlas
php,

Více ...

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