Adaptace Matematických ALGoritmů: Kruskalův algoritmus

1. Popis standardní metody algoritmu

Kruskalův algoritmus slouží k vyhledání minimální kostry grafu. Pracujeme s váženým neorientovaným grafem $G = (V, E, w)$ , kde $V$ je množina vrcholů, $E$ je množina neorientovaných hran a $w$ je kladné ohodnocení hran.

Na počátku algoritmu inicializujeme kostru $T = (V, \emptyset)$ obsahující všechny vrcholy grafu $G$ a prázdnou množinu hran.
Seřadíme všechny hrany grafu $G$ vzestupně dle jejich ohodnocení a v tomto pořadí je postupně zpracováváme.
Pokud přidáním konkrétní hrany $e$ do kostry $T$ nevniká kružnice, přidáme $e$ do $T$ , v opačném případě hranu do $T$ nepřidáme.
Po zpracování poslední hrany s nejvyšším ohodnocením získáme minimální kostru $T$ .

Při běžném provedení algoritmu pracujeme s vizuální reprezentací grafu. Hrany, které přidáváme do kostry, zvýrazňujeme (barevně či jiným způsobem) přímo v zadaném grafu. Na Obrázku 1 je znázorněn graf $H$ o sedmi vrcholech. Je ukázána situace před zpracováním 4. hrany v pořadí, mezi uzly $D$ , $G$ . Po prvních třech krocích se do kostry grafu vložily hrany $CF$ , $DE$ , $CD$ . Jelikož přidáním hrany $DG$ nevytvoříme kružnici, můžeme ji taktéž vložit do kostry.

Příklad 1: Vážený neorientovaný graf $H$

Obrázek 1: Vážený neorientovaný graf $H$ , ukázka zvýraznění hran kostry i aktuálně zpracovávané hrany

V dalším pokračování však do kostry grafu nemůžeme přidat ani jednu hranu s ohodnocením 4, protože jejich vložením by v obou případech vznikla kružnice délky 3 (mezi trojicí $C, D, F$ či $D, E, G$ ).

Pro názornost uvádíme i konkrétní příklad váženého neorientovaného grafu a Animaci 1 naznačující výpočet minimální kostry pomocí Kruskalova algoritmu.

Příklad 2: Vážený neorientovaný graf $H$

Počátek algoritmu - neorientovaný graf $H$ o sedmi uzlech $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$
Hrany kostry:
1/12
Dosud nezpracované hrany: $C$ – $2$ – $F$ , $D$ – $2$ – $E$ , $C$ – $3$ – $D$ , $D$ – $3$ – $G$ , $D$ – $4$ – $F$ , $E$ – $4$ – $G$ , $A$ – $5$ – $C$ , $B$ – $5$ – $D$ , $A$ – $6$ – $D$ , $B$ – $6$ – $E$ , $A$ – $7$ – $B$ , $F$ – $7$ – $G$
Nezobrazovat tento popisek

Animace 1: výpočet minimální kostry pomocí Kruskalova algoritmu

2. Návrh možných adaptací

1. Organizace hran grafu v tabulce podle vrcholů, zápis kostry do dalšího dokumentu (listu):

Graf je nabízen ve formě tabulky. Do jejího prvního sloupce zapisujeme návěští vrcholů. Do dalších buněk na stejném řádku pro daný vrchol $X$ vkládáme všechny hrany vycházející z $X$ , a to ve formátu $X$ – $n$ – $Y$ , kde $n$ je ohodnocení hrany a $Y$ je koncový vrchol hrany. $V$ dalším listu tabulky, případně v samostatném souboru, uchováváme hrany, které zařazujeme do minimální kostry. Taktéž tam evidujeme množiny uzlů, které jsou přidanými hranami propojeny. Uvažujme tentýž graf $H$ o sedmi uzlech, který jsme znázornili na Obrázku 1. Následující dvě tabulky (Tabulka 1 a Tabulka 2) zachycují stav po přidání prvních dvou hran do minimální kostry grafu $H$ .

Příklad 3: Graf $H$ z Obrázku 1 po přidání dvou hran

$A$	$A$ – $5$ – $C$	$A$ – $6$ – $D$	$A$ – $7$ – $B$
$B$	$B$ – $5$ – $D$	$B$ – $6$ – $E$	$B$ – $7$ – $A$
$C$		$C$ – $3$ – $D$	$C$ – $5$ – $A$
$D$		$D$ – $3$ – $C$	$D$ – $3$ – $G$	$D$ – $4$ – $F$	$D$ – $5$ – $B$	$D$ – $6$ – $A$
$E$		$E$ – $4$ – $G$	$E$ – $6$ – $B$
$F$		$F$ – $4$ – $D$	$F$ – $7$ – $G$
$G$	$G$ – $3$ – $D$	$G$ – $4$ – $E$	$G$ – $7$ – $F$

Tabulka 1: Graf $H$ formou tabulky, stav po přidání prvních dvou hran $C$ – $2$ – $F$ , $D$ – $2$ – $E$

Příklad 4: Kostra grafu $H$ z Obrázku 1 po přidání dvou hran

MKG – Hrany:	$C$ – $2$ – $F$	$D$ – $2$ – $E$
MKG – Množiny vrcholů:
$C, F$
$D, E$

Tabulka 2: Prozatimní kostra grafu $H$ , stav po přidání prvních dvou hran $C$ – $2$ – $F$ , $D$ – $2$ – $E$

Z předchozích dvou tabulek je patrné, že obě dosud přidané hrany propojují množiny uzlů $\{ C, F\}$ a $\{ D, E\}$ . Před přidáním další hrany v pořadí $(C$ – $3$ – $D)$ musíme ověřit, zda v kostře grafu $H$ nevznikne kružnice. Vidomý student provádí kontrolu vizuálně, nevidomý si k tomuto účelu eviduje množiny uzlů propojených hranami dosavadní kostry. Pokud oba vrcholy zpracovávané hrany patří do stejné množiny uzlů, jejím přidáním bychom vytvořili kružnici. $V$ opačném případě aktualizujeme Tabulku 3. Aktuální hranu vkládáme do kostry a následně upravíme množiny vzájemně propojených uzlů. Nesmíme zapomenout, že právě zpracovaná hrana byla v Tabulce 2 uvedena dvakrát, je tudíž nutné oba výskyty vymazat.

2. Organizace hran ve dvou sloupcích tabulky, zápis kostry do dalšího dokumentu (listu):

Graf je opět nabízen ve formě tabulky, hrany jsou však organizovány jiným způsobem. V 1. sloupci je jejich charakteristika, opět ve formátu $x$ – $n$ – $y$ , kde $x, y$ označují uzly propojené hranou s ohodnocením $n$ . Ve 2. sloupci je znovu zopakováno ohodnocení hrany. Ukázku tohoto způsobu organizace hran nabízíme v Tabulce 3 .

Příklad 5: Hrany grafu $H$ z Obrázku 1 včetně ohodnocení

$A$ – $5$ – $C$	$5$
$A$ – $6$ – $D$	$6$
$A$ – $7$ – $B$	$7$
$B$ – $5$ – $D$	$5$
$B$ – $6$ – $E$	$6$
$C$ – $2$ – $F$	$2$
$C$ – $3$ – $D$	$3$
$D$ – $2$ – $E$	$2$
$D$ – $3$ – $G$	$3$
$D$ – $4$ – $F$	$4$
$E$ – $4$ – $G$	$4$
$F$ – $7$ – $G$	$7$

Tabulka 3:Tabulková reprezentace grafu $G$ z Obrázku 1

Většina tabulkových procesorů nabízí možnost seřadit data podle hodnot určitého sloupce. Nevidomý student tedy může hrany seřadit vzestupně podle ohodnocení, když je uspořádá podle 2. sloupce. Pro zápis kostry grafu a množin dosud propojených uzlů používáme buď druhý list tabulky či samostatný dokument. Postupujeme stejným způsobem jako v předchozí metodě.

Adaptace Matematických ALGoritmů

Kruskalův algoritmus

Kruskalův algoritmus

1. Popis standardní metody algoritmu

Příklad 1: Vážený neorientovaný graf

Příklad 2: Vážený neorientovaný graf

2. Návrh možných adaptací

1. Organizace hran grafu v tabulce podle vrcholů, zápis kostry do dalšího dokumentu (listu):

Příklad 3: Graf z Obrázku 1 po přidání dvou hran

Příklad 4: Kostra grafu z Obrázku 1 po přidání dvou hran