Zadání
název: kostra grafu - principy a algoritmy
forma zpracování: plus
obsah
-----
kostra grafu
hledání koster v souvislém grafu
hledání minimální kostry v ohodnoceném grafu
představa zpracování
--------------------
dokument obsahující:
užité pojmy
algoritmy v pseudokódu/přirozeném jazyce
algoritmy v jazyce C (minimálně 3) s okomentovaným zdrojovým kódem
zpracované algoritmy:
obecný alg. pro hledání koster
alg. pro hledání minimální kostry v souvislém i nesouvislém grafu
- Borůvkův-Kruskalův algoritmus
- Jarnikův-Primův algoritmus
Terminologie a definice
- Graf, který neobsahuje kružnici, se nazývá les.
- Souvislý les, se nazývá strom.
-
Faktor grafu G, který je stromem, nazýváme kostra grafu G (pro nesouvislý graf vznikne "minimální les").
pozn.: Kostra grafu není určena jednoznačně.
pozn.: V obvodářské praxi se někdy pro označení kostry používá také pojem "úplný strom" - Pro každý konečný souvislý graf existuje kostra tohoto grafu.
Teoretický rozbor
Problém nalezení kostry grafu spočívá v hledání vhodných hran, které kostru mohou tvořit. V případě grafu s neohodnocením hran se problém redukuje na nalezení minimální souvislé (ev. v rámci každé komponenty grafu) množiny hran, které incidují se všemi uzly grafu (komponenty). Takový požadavek se dá implementovat postupným např. přidáváním hran, pokud takto vložená hrana nezačne ve vznikajícím podgrafu tvořit kružnice. V každém kroku takovéhoto postupu bychom mohli vybírat postupně (rekurzivně) každou hranu, která je ještě k dispozici. Tímto postupem, který je však extrémně neefektivní, lze nalézt všechny kostry daného grafu.
Pokud nám stačí nalézt libovolnou kostru daného grafu, je možné začít od jednoho z uzlů (pro větší rozvětvenost kostry např. od uzlu s největším stupněm) a postupným prohledáváním do hloubky (či do šířky) budeme do vznikající kostry přidávat hrany, které vedou do ještě nepokrytých uzlů. Takový algoritmus, který díky svému pojetí nebere v potaz ev. ohodnocení hran, lze zapsat v pseudokódu nasledovně:
0. pokud existují neoznačené uzly, vyber z nich uzel u, jinak skonči (kostra jsou označené hrany) 1. pro všechny sousedy u 2. begin 3. pokud je soused v neoznačený, označ ho hranu vedoucí k němu přidej do kostry 4. end 5. pro všechny sousedy u 6. begin 7. pokud je hrana (u, v) neoznačená, označ ji a pro uzel v proveď predešlé 2 cykly (jako by to byl u) 8. end 9. jdi na 0.
V případě ohodnoceného grafu přestávají být jednotlivé kostry rovnocenné a můžeme je rozlišovat podle součtu vah hran, které do kostry patří. Za předpokladu znalosti takového operátoru, může existovat požadavek na nalezení takové kostry (nebo více v případě nejednoznačnosti), která má ze všech možných minimální součet vah hran. Je pak nazývána minimání kostra a algoritmus řešící problém na grafu neohodnoceném bude třeba jistým způsobem modifikovat. Test na přítomnost kružnic bude v obecném smyslu přetrvávat; rozhodující zde bude správná volba další hrany, která se stane adeptem na vložení do vznikající kostry. Existují 2 efektivní algoritmy, které tento problém řeší. Jedním z nich je algoritmus Borůvka-Kruskal pracující na bázi množinového rozkladu uzlů:
0. pro každý uzel vyplň jeho příslušnost k jiné množině 1. hrany grafu seřaď do neklesající posloupnosti podle jejich vah 2. pro každou hranu (v seřazeném pořadí dle 1.) 3. begin 4. pokud uzly, se kterými hrana inciduje patří do jiné množiny 5. begin 6. zkoumanou hranu přidej do vznikající kostry 7. sjednoť množiny incidujících uzlů 8. end 9. endAlgoritmus v této podobě funguje díky své povaze i pro nesouvislé grafy, ale počet komponent nezjišťuje. Toho lze docílit drobným rozšířením (v programu implementováno), spočívajícím v analýze diversity množin, které po provedení algoritmu zbydou. Kolik různých jich zbyde, tolik komponent původní graf obsahuje.
Na jiném principu funguje algoritmus nazvaný podle svých objevitelů Jarník-Prim. Zde se kostra formuje podobně jako při činnosti prohledávacích algoritmů (do šířky a do hloubky), přičemž informace o tom, kterou hranu v aktuálním kroku vybírat, se udržuje v prioritní frontě uspořádané podle minimální vzdálenosti uzlu od dílčího podstromu kostry. Časová složitost této implementace je o něco lepší než pro algoritmus Borůvka-Kruskal (O(|H|*log|U|) oproti O(|H|*log|H|)). Činnost algoritmu Jarník-Prim lze přiblížit takto:
0. do prioritní fronty ulož všechny uzly a nastav jim vzdálenost d na INF a předchůdce p na NIL 1. jednomu uzlu (od kterého algoritmus začne) nastav d = 0 (čím menší d tím větší priorita ve frontě) 2. dokud v prioritní frontě existují prvky 3. begin 4. proveď extrakci prvku u z fronty 5. pro všechny následníky v uzlu u 6. begin 7. pokud se v nachází ve frontě a jeho d je menší než váha hrany (u, v) 8. uzlu v nastav p = u a d = váha hrany (u, v) 9. end 10. endPo provedení uvedeného postupu máme kostru nalezenou "pouze" implicitně, a sice prostřednictvím předchůdců jednotlivých uzlů. Pokud bychom potřebovali transformovat tuto informaci na seznam hran obsažených v kostře, projdeme všechny uzly a hrany vedoucí k jejich předchůdcům prohlásíme za kostru. Tento algoritmus narozdíl od prvního zmíněného neřeší situaci, kdy vstupní graf má více než jednu komponentu. Drobnou modifikací (v programu implementováno) zajistíme i tuto funkcionalitu. Stačí si pamatovat, které uzly nebyly extrahovány z fronty (v důsledku toho, že nejsou dostupné) a v příštím průchodu algoritmem začít od libovolného z nich. Toto se musí provádět, dokud po ukončení algoritmu takové uzly ještě zůstávají. Tím je rovněž možné určit počet komponent vstupního grafu (je to počet nutných opakování + 1).
Překlad, spuštění
Program "kostry" je konzolová aplikace psaná v C/C++. Kód je plarformově nezávislý, lze ho kompilovat např. na OS Linux nebo Win32. Vlastní překlad realizujeme programem make a přiloženým Makefile (kompatibliní s GNU make). Pro kompilaci na Win32 lze použít Makefile pro Linux v případě, že kompilujeme pod Linuxovým prostředím (Cygwin, MSYS) nebo soubor Makefile.win určený ke kompilaci s překladači MinGW (+je třeba změnit cestu k nim v rámci adresářové struktury Windows). Po vybuildování binárního kódů ke možné program spustit příkazem ./kostry (ev. kostry.exe).
-
Zdrojové kódy
kostry-src.zip -
Zkompilovaný program
- Win32 - kostry.exe
- Cygwin - kostry.exe
- Linux - kostry
Manuál
Program "kostry" se ovládá z terminálu. Graf lze zadat buď z klávesnice nebo ze souboru. Použití je:
Usage : ./kostry [soubor_s_grafem] Example: ./kostry ../doc/grafy/graf-3Několik předdefinovaných grafů se nalézá v adresáři doc/grafy/. Jejich grafickou reprezentaci zachycují následující obrázky (červeně je ohodnocení hran):
| graf-1 |  |
| graf-2 |  |
| graf-3 |  |
Uvedené grafy obsahují i některé testovací singularity - multihrany, smyčky nebo izolovaný bod. Program umí nad zadaným
grafem realizovat zmíněné algoritmy hledání kostry nebo minimálí kostry. Výběr algoritmu je prováděn interaktivně uvedením
čísla volby, ev. doplňujících parametrů (výpis akcí). Navíc je možné nechat nalézt nezávislé smyčky (kružnice obsahující právě jednu hranu která není
obsažená v kostře) přes zadanou hranu a nezávislé řezy (množina hran procházejících uzavřenou čárou, která protíná
právě jednu hranu kostry). Obojí se děje nad grafem s nalezenou kostrou, která je vyhodnocena jedním z podporovaných
algoritmů a pro obě zmíněné funcionality platí, že berou kladnou orientaci hran od prvního incidujícího uzlu (při zadávání)
k druhému (výstup atributu orientace - pro smyčky se jedná o orientaci v kružnici, kde zadaná hrana má kladný smysl, u řezu
je kladný smysl dán stejnou orientaci vstupu/výstupu do/z plochy uzavřené řeznou čarou jako zadaná hrana).
Pro úplnost předkládám grafické znázornění výsledků nalezení kostry a
minimální kostry na testovacích grafech:
 |  | |
 |  | |
 |  |