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

> Grafy a grafové algoritmy II

Tento článek je zaměřen na hledání minimální kostry v grafu. V první části článku je teorie, která s minimální kostrou souvisí, v části druhé jsou vysvětleny dva algoritmy, které slouží k nalezení minimální kostry. Nechybí ani jejich implementace v jazyku C++.

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

Úvod

Základní teorie, která se týká grafů, byla popsána v článku Grafy a grafové algoritmy I, proto se jí zde nebudu dále zabývat. Pojmů a algoritmů, které souvisí s grafy, je však mnohem více než ve výše uvedeném článku. Pojem, který bude v tomto článku stěžejní, je tzv. minimální kostra grafu. Dříve, než budeme formálně definovat pojem kostry, musíme definovat pojem strom, neboť ten se právě objevuje v definici kostry.

Strom je souvislý jednoduchý graf, který neobsahuje kružnice.

O grafu, který neobsahuje kružnice, se říká, že je acyklický. To neznamená nic jiného, než že neobsahuje žádnou smyčku (velmi jednoduše řečeno, nelze v něm chodit „pořád dokola“). Na následujícím obrázku je ukázka, jak například může vypadat strom.

V souvislosti se stromy platí různé věty, pár jich uvádím.

  • Strom, který má n vrcholů, má n – 1 hran (platí pro n > 0)
  • Přidáme-li do stromu jednu novou hranu, tak vznikne graf s jednou kružnicí.
  • Každý strom, který má více než jeden vrchol, má nějaký vrchol stupně jedna.
  • Mezi každými dvěma vrcholy stromu lze nalézt právě jednu cestu.
To, že tyto věty opravdu platí, si můžete ověřit například na obrázku výše. Stromy však nejsou předmětem tohoto článku, proto se jimi nebudeme dále zabývat a přejdeme na kostru grafu.

Kostra grafu a minimální kostra grafu

Kostra souvislého grafu G je podgraf v G, přičemž je sám stromem a obsahuje všechny vrcholy grafu G.

Jinými slovy, kostra grafu obsahuje všechny vrcholy grafu, jehož kostru hledáme, ale pouze ty hrany, které poté ve výsledku tvoří strom. Pro dokonalé pochopení uvádím obrázek grafu, společně s vyznačenou kostrou.


Kostra, která je na obrázku vyznačena, není jediná, kterou graf obsahuje, protože graf může mít mnohem více koster než jednu. Důkaz, že se opravdu jedná o kostru, je snadný. Podgraf, který jsem vybral, obsahuje všechny vrcholy a zároveň se jedná o strom. To, že je to opravdu strom, možná nemusí být někomu na první pohled patrné, ale je to tak. Podgraf je souvislý, neobsahuje žádné kružnice, a věty, které jsem o stromech uváděl, pro něj také platí. Nyní se konečně dostáváme k poslední definici, kterou je definice minimální kostry grafu.

Minimální kostra grafu je kostra, která má nejmenší ohodnocení.

Touto definicí jsme se dostali k váženým grafům, o kterých jsem psal v minulém článku. Na dalším obrázku uvádím ohodnocený graf, společně s vyznačenou minimální kostrou.

Na tomto obrázku si můžete všimnout, že graf je úplně stejný jako na předchozí ukázce, jen s tím rozdílem, že má ohodnocené své hrany. Minimální kostra je vyznačena červenou barvou. Snad nemusím říkat, že minimální kostra je jiná, než kostra, kterou jsem vyznačil na předchozím obrázku. Váha této kostry je 24 (součet vah jednotlivých hran kostry). Skutečně se jedná o kostru minimální, neboť není možné najít kostru, která by měla menší váhu než 24. Nyní se tedy nabízí hlavní otázka - jak minimální kostru najít? První způsob, jak to udělat, je využití Kruskalova algoritmu.

Kruskalův algoritmus

Na pochopení je tento algoritmus poměrně jednoduchý. První krok tohoto algoritmu je seřazení všech hran grafu, dle jejich vah (od nejmenší po největší). Celý postup si ukážeme na předchozím grafu. Náš graf má tedy 10 hran, přičemž seřadíme-li jejich váhy od nejmenší po největší, dostaneme tuto posloupnost čísel:
1, 3, 4, 4, 5, 7, 9, 11, 13, 15
Poté budeme brát postupně jednotlivé hrany, a buď je přidáme do kostry, nebo ne. Kritérium pro rozhodování je snadné – pokud právě přidávaná hrana nevytváří kružnici (neboli smyčku), přidáme ji. V opačném případě ji nepřidáme a pokračujeme dále.
Nejprve tedy přidáme hranu s ohodnocením 1. Následuje hrana s ohodnocením 3. Tato hrana nám nemůže vytvořit kružnici, proto ji můžeme také přidat do výsledné minimální kostry. Obdobným způsobem přidáváme hrany až do hrany s ohodnocením 7. Následuje hrana s ohodnocením 9. Tu již ale nepřidáme – vytvořili bychom cyklus, což je v rozporu s definicí kostry (cyklus by byl mezi vrcholy 1 – 2 – 3 – 4). Dále už nepřidáme žádnou hranu, neboť bychom opět vytvořili nějaký cyklus. Prozkoumali jsme tedy všechny hrany, přičemž některé jsme přidali, jiné ne. Tím algoritmus končí, neboť jsme získali minimální kostru grafu.

Implementace Kruskalova algoritmu

Při samotné implementaci je nejprve nutné zvolit vhodný způsob reprezentace grafu v počítači. V minulém článku jsme používali matici sousednosti, která se ale pro Kruskalův algoritmus nehodí. Místo toho budeme graf reprezentovat objekty tříd vrchol (Node) a hrana (Edge). Nebudu zde uvádět zdrojové kódy jednotlivých tříd, neboť celý zdrojový kód je trochu delší a je možné si jej stáhnout níže. Každý vrchol má nějaké své ID, podle kterého jednoznačně určíme, o jaký vrchol se jedná. Každá hrana obsahuje informace o tom, mezi kterými vrcholy vede a jaká je její váha. To stačí k tomu, abychom věděli, o jaký graf se jedná.
Máme-li graf v počítači, není již těžké dát se do psaní samotného algoritmu. Problém může nastat snad jen při zjišťování, zda hrana, kterou chceme přidat, bude nebo nebude tvořit cyklus. Tento problém lze poměrně snadno vyřešit s pomocí tzv. Disjoint-setu. Jde o datovou strukturu a celé řešení problému je postaveno na základě udržování reprezentantů komponent. V případě, že dva vrcholy mají stejného reprezentanta, patří tyto dva vrcholy do stejné komponenty. Datová struktura Disjoint-set má dvě hlavní metody – Union a Find. První z uvedených metod má na starost spojení dvou komponent, druhá slouží k nalezení reprezentanta. Nejčastěji se využívá n-ární strom a kořen tohoto stromu je reprezentant. Metoda Find je tedy poměrně jednoduchá – z vrcholu, jehož reprezentanta hledáme, stačí „stoupat nahoru“ tak dlouho, dokud nedojdeme ke kořeni. Pokud spojujeme dvě komponenty v jednu (metoda Union), stačí menší podstrom zavěsit pod reprezentanta většího podstromu.
Celou ukázku implementace Kruskalova algoritmu v jazyce C++ je možné stáhnout zde. Myslím, že po přečtení si způsobu, jak algoritmus funguje, a po prohlednutí kódu by měl být princip tohoto algoritmu poměrně jasný a proto můžeme přejít na další algoritmus.

Jarníkův algoritmus

Tento algoritmus, stejně jako předchozí, slouží také k nalezení minimální kostry grafu. Jeho princip je však jiný, proto si jej opět vysvětlíme na našem grafu.
Hned první změna oproti minulému algoritmu je v tom, že hrany nijak neseřazujeme. Místo toho si vybereme libovolný vrchol, ve kterém začneme. Je úplně jedno, který vrchol zvolíme, neboť v kostře budou nakonec všechny vrcholy. Poté se podíváme na všechny hrany, jež z tohoto vrcholu vedou, a vybereme tu s nejmenším ohodnocením. Ta bude součástí výsledné kostry. Nyní máme tedy spojené dva vrcholy a opět hledáme hranu, která má nejmenší ohodnocení a vychází z některého ze dvou vrcholů. Tuto hranu opět přidáme do kostry, čímž se dostaneme k dalšímu uzlu a celý postup opakujeme. Zbývá jediná otázka – kdy skončit? Samozřejmě tehdy, až bude kostra úplná. To poznáme velmi jednoduše. Stačí si uvědomit, že kostra grafu je strom a obsahuje všechny vrcholy grafu. My víme, že každý strom, který má n vrcholů, má n – 1 hran. Čili například bude-li mít graf 20 vrcholů, jeho kostra bude mít 19 hran.
Abychom si celý tento postup ujasnili, najdeme minimální kostru grafu z ukázky. Vybereme tedy libovolný vrchol, například vrchol 1. Z tohoto vrcholu vedou hrany, jejichž váhy jsou 7, 3 a 4. Nejmenší z nich je samozřejmě s váhou 3, proto tuto hranu přidáme do kostry. Díky tomu jsme se dostali do vrcholu 4 a nyní vybíráme jednu z celkem pěti hran – dvě vedou ještě z vrcholu 1 a 3 z vrcholu 4. Je jasné, že vybereme hranu s ohodnocením 1. Díky ní se dostáváme do vrcholu 3. Opět najdeme hranu s minimálním ohodnocením – to je hrana z vrcholu 1 do vrcholu 5, a její váha je 4. Tímto způsobem postupujeme tak dlouho, dokud nevybereme 6 hran (graf má 7 vrcholů, kostra má tedy 7 – 1 hran).

Implementace Jarníkova algoritmu

V porovnání s implementací Kruskalova algoritmu je tato o něco snadnější. Graf nám bude stačit reprezentovat již známou maticí sousednosti, čímž nám tedy odpadají třídy Node a Edge. Také nám odpadá využití Disjoint-setu, který v minulém algoritmu sloužil jako kontrola, zda nevytváříme smyčku. Zde to bude jednodušší. Stačí si uvědomit, že tvoříme-li kostru tímto algoritmem, vždy v průběhu kreslení kostry máme souvislý graf, jinak řečeno, mezi všemi zatím přidanými uzly vede cesta. Díky tomuto postupu je možné cyklus vytvořit jedině tak, že bychom vedli hranu do vrcholu, který již je součástí kostry. A to je velmi snadné na ohlídání. Ukázka v jazyce C++ je k dispozici zde.

Závěr

Na závěr ještě zmíním, k čemu se vlastně nalezení minimální kostry grafu může hodit. Zkuste si například představit nějaké obce, vesnice, či města. Celé toto území chceme elektrifikovat. Můžeme tedy města převést na vrcholy, hrany nám budou reprezentovat elektrické spojení, přičemž ohodnocení hran bude znamenat cenu za natažení vedení. Minimální kostra tohoto grafu nám pak přesně určí, kudy vést vedení, abychom celý problém vyřešili nejlevněji.

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

8.1.2017 17:51 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 19. ledna od 18:30 v pražském hackerspacu Brmlab. Tentokrát je tématem srazu ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. K vidění bude mechanická klávesnice dasKeyboard, trackball Logitech nebo grafický tablet (a velký touchpad) Wacom. Přineste i vy ukázat svoje zajímavé klávesnice a další HW. V 18:20 je sraz před budovou, v 18:30 jdeme společně dovnitř, je tedy dobré přijít včas. Podle zájmu se později přesuneme do nějaké restaurace v okolí.
Přidat komentář

1.12.2016 22:13 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.
Komentářů: 1

4.9.2016 20:13 /Pavel `Goldenfish' Kysilka
PR: Dne 22.9.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í, provozování ERP v cloudu, o hostování různých typů softwaru, ale třeba i o zálohování dat nabízeném podnikům formou služby.
Přidat komentář

1.9.2016 11:27 /Honza Javorek
Česká konference o Pythonu, PyCon CZ, stále hledá přednášející skrz dobrovolné přihlášky. Máte-li zajímavé téma, neváhejte a zkuste jej přihlásit, uzávěrka je již 12. září. Konference letos přijímá i přednášky v češtině a nabízí pomoc s přípravou začínajícím speakerům. Řečníci mají navíc vstup zadarmo! Více na webu.
Přidat komentář

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

> Poslední diskuze

17.4.2017 19:15 / Jakub shoop
chyba

7.4.2017 15:43 / Som
foreign car repair

31.3.2017 18:33 / David Ostrovsky
Dotazník na obeznámenost s hummusem.

24.3.2017 11:54 / Hui
country cottages

16.3.2017 16:33 / BezvaDesign.cz
Re: Hledám grafika do teamu

Více ...

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