Hledaní minimální kostry neorientovaného grafu
Jedná se o jeden z klasických problémů, který řeší vědní disciplína teoretická informatika. Problém určení minimální kostry není samoúčelný, ale je motivován mnoha praktickými aplikacemi v reálném životě (hledání nejkratšího vlakového spoje, ...). Omezuje se pouze na část neorientovaných grafů - proto tuto skutečnost v dalším textu budeme už mlčky předpokládat.
Kostra grafu
Kostrou grafu nazýváme libovolný podgraf daného grafu, který obsahuje všechny uzly grafu a tolik hran z původního grafu tak, aby z každého uzlu podgrafu existovala cesta ke všem zbývajícím uzlům. Je jasné, že k jednomu grafu lze nalézt i více koster, pokud existuje dostatečné množství hran a původní graf již například není sám kostrou.
Minimální kostra grafu
Při generování všech koster grafu jsou různé kostry daného grafu v zásadě rovnocenné - všechny obsahují stejný počet hran. Jiná situace ovšem nastane, pokud každé hraně přiřadíme nějakou nezápornou reálnou délku. V takovém případě má smysl se zabývat hledáním takové kostry, která má nejmenší součet délek svých hran. Délku hrany označujeme w(h), kde h je hrana incidující se dvěma uzly. Podle potřeb aplikace můžeme této veličině přisuzovat také význam kapacity nebo toku hranou.
Ani řešení při hledání minimální kostry nemusí být nutně jednoznačné - koster splňujících kritérium minimálnosti (součet délek je minimální) může být i více. Applet demostrující hledání takové kostry vybírá takové řešení, které je nejbližší na základě vnitřní reprezentace grafu.
Problém určení minimální kostry má také svoji historii, do které se úspěšně zapsali i dva čeští matematici. Nejprve je formuloval a úspěšně vyřešil v polovině 20.let O. Borůvka v souvislosti s návrhem sítě pro rozvod elektřiny na Moravě. Efektivnější metodu řešení navrhnul r.1930 V. Jarník Používání prvních počítačů po r. 1950 přineslo oživení zájmu o algoritmické řešení problému minimální kostry, a tak byly algoritmy O. Borůvky a V. Jarníka znovu nezávisle objeveny a publikovány v USA, takže se potom staly všeobecně známými.
Borůvkův-Kruskalův algoritmus
Základní myšlenkou Borůvkova-Kruskalova algoritmu je, že pro přidání hrany k postupně vznikající kostře vybírá takovou hranu, která má ze všech možných hran spojujících dva různé podstromy ve vytvářené kostře tu nejmenší váhu.
Jinými slovy: Na počátku množina podstromů představuje izolované uzly (uzel = podstrom). Postupným sjednocováním podstromů přes hrany, které mají mezi danými podstromy (uzly) nejmenší délku, se množina podstromů zmenšuje, až nakonec zůstane podstrom jediný, který představuje minimální kostru původního grafu.
Jarníkův-Primův algoritmus
Jarníkova-Primova varianta algoritmu určení minimální kostry vychází z toho, že hrany, vybrané do množiny hran reprezentující dosud vytvořenou část kostry, tvoří stále jediný podstrom, k němuž se připojí přidanou hranou vždy pouze jeden nový uzel. Uzel, který je spolu s hranou přidáván, má k dosud vzniklé kostře ze všech zbývajících uzlů nejblíže. Protože hodnota "vzdálenosti od kostry" se přidáním uzlu může změnit, je po každém takovém kroku nutné provést přepočtení těchto údajů.
Úplný popis chování a vlastností obou algoritmů nabízí odkazovaná literatura. Tam lze najít i řešení vnitřní reprezentace pro konstrukci minimální kostry. Příslušná kapitola taktéž pojednává i výpočetní složitost, jež je při praktickém programování třeba brát v úvahu.
Základem appletu naprogramovaného v jazyce Java je editor neorientovaných grafů, který je umístěn na samostatném levém panelu a který lze bez vetších úprav převzít do jiných rovněž appletem řešených obdobných problémů.
Tlačítka editoru UZLY, HRANY a SMAŽ jsou konciovány jako přepínače reprezentující danou funkci.
Uzly lze před umístěním na plochu pro graf přejmenovat na jiné než implicitní jednoznakové označení velkým písmenem abecedy. Výhodou je, že pokud bude dostačovat právě toto implicitní označování, dochází k automatické "inkrementaci" na nejbližší volné písmeno v řadě abecedy.
Hrany vznikají ukázáním na oba krajní uzly incidující s hranou, na pořadí nezáleží. Současně dojde k přiřazení délky (kapacity) vznikající hraně. Dosazována je hodnota z příslušného editačního pole. Ta je implicitně nastavena na reálné číslo 1,0. Podle potřeby je dobré tuto hodnotu změnit před vytvořením hrany - podporována jsou reálná čísla. Pokud je třeba dodatečně změnit délku (kapacitu) hrany, lze to provést "přetažením" přes stávající hranu mezi dvěma uzly. Dojde k přepsání té existující - editor grafu nepovoluje rovnoběžné hrany (a ani smyčky).
Smazat lze izolované uzly, pro incidující s libovolnými hranami je nutné smazat nejprve tyto hrany ukazáním na jejich grafickou podobu.
V režimu standardních úprav (žádný přepínač není aktivní) lze měnit podobu vzniklého grafu přemísťováním (přatahováním) jednotlivých uzlů (dochází k překreslení i hran mezi uzly).
V horní části pravého panelu lze nechat vygenerovat jak prázdný graf, tak i jeden ze dvou nabízených demo grafů. Druhý ze zmiňovaných je příklad převzatý z literatury, konstrukci minimální kostry lze tedy sledovat jak interaktivně na obrazovce, tak i v papírové podobě.
Přepínač pro výběr algoritmů umožňuje sledovat rozdíl v hledání minimální kostry grafu - oba demo grafy byly záměrně vybrány tak, aby odlišnost jejich činnosti byla zřejmá a patrná.
Běh algoritmu lze řídit ovládacími prvky START, KROK a DOKONČI. V době, kdy je hledána minimální kostra, nelze provádět žádné úpravy na grafu. Krokování je vhodné pro podrobné sledování činnosti algoritmu, tlačítko dokonči je určeno pro okamžité nalezení kostry grafu, popřípadě pro ukončení běhu algoritmu.
Applet hledající minimální kostru
doc. Josef Kolář - Teoretická informatika - vydala Česká informatická společnost, září 1996, Praha