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

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

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

16.3.2018 22:01 /František Kučera
Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář

13.2.2018 0:41 /František Kučera
Únorový pražský sraz OpenAltu se koná 15. 2. 2018 a tentokrát se vydáme na návštěvu do jednoho pražského datacentra. Sejdeme se v 17:50 v severovýchodní části nástupiště tramvajové zastávky Koh-I-Noor. Po exkurzi se přesuneme do restaurace U Pštrosa (Moskevská 49), kde probereme tradiční témata (svobodný software a hardware, DIY, CNC, SDR, 3D tisk…) a tentokrát bude k vidění i IoT brána od The Things Network.
Přidat komentář

11.2.2018 23:11 /Petr Ježek
Hledáte lehký a rychlý prolížeč PDF souborů? Pokud vás již omrzelo čekat na načítání stránek či jiné nešvary, zkuste xreader.
Přidat komentář

11.2.2018 20:35 /Redakce Linuxsoft.cz
Třetí ročník odborné IT konference na téma Cloud computing v praxi proběhne ve čtvrtek 1. března 2018 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 hod. dopoledne do cca 16 hod. odpoledne. Konference o trendech v oblasti cloud computingu nabídne i informace o konkrétních možnostech využívání cloudů a řešení vybraných otázek souvisejících s provozem IT infrastruktury.
Přidat komentář

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

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

> Poslední diskuze

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

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

Více ...

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