Hledání kostry v grafu Flashcards
(4 cards)
Kostra grafu - definice
Kostra grafu je podmnožina hran souvislého grafu, která obsahuje všechny vrcholy a tvoří souvislý podgraf bez cyklů (tedy strom).
Vytváří se tak, aby propojila všechny body a celková váha hran byla co nejmenší. Hledání kostry s co nejmenší váhou nazýváme minimal spanning tree.
Nejznámějšími algoritmy jsou Kruskalův algoritmus (centralizovaný) a distribuovaný algoritmus (paralelní). U souvislého grafu se hledá podmnožina hran, která tvoří strom (obsahující všechny uzly) a jejíž celková váha (součet délek hran grafu) je minimální.
V případě nesouvislého grafu o více komponentách, algoritmus hledá les minimálních koster, tedy minimální kostru každé komponenty.
Uplatnění kostry grafu
Uplatnění:
– Odstranění cyklů z grafu (např. přepínač)
– Návrh sítí (telefonické, elektrické, hydraulické, TV kabelové, počítačové, silniční,…)
– Analýza shluků (hledání shluků kvazarů a Seyfert galaxií, analyzování plísní prostorových modelů)
– Přibližná řešení tzv. NP-těžkých problémů (metrický TSP (Traveling Salesman Problem), Steiner stromy)
Nepřímá uplatnění:
– Rakovinový výzkum
– Učení charakteristických rysů pro real-time verifikaci tváře
– Modelování lokálnosti interakce částic turbulentního toku kapalin
– Snižuje množství ukládaných dat pro popis aminokyselin v proteinu
Centralizovaná varianta nalezení kostry v grafu - Kruskalův algoritmus
Funguje na principu shlukování dvou množin hran. Ze všech hran se vybere hrana s nejnižší hodnotou a množiny vrcholů, jenž hrana propojuje se seskupí do jedné množiny. Tak se postupuje tak dlouho dokud všechny vrcholy nejsou v jedné množině. Pokud cesta propojuje vrcholy ze stejné množiny vrcholů tak se nepoužije a pokračuje se z následující hranou. Využívá se pokud známe celou topologii grafu.
paralelní varianta nalezení kostry v grafu - Distribuovaný algoritmus
Zde se pracuje na principu, že se kostra tvoří na každé množině zároveň. Z každého vrcholu se vyrazí směrem po nejmenší hodnotě hrany. Pokud se vrcholy na cestě potkají, tak vytvoří množinu. Pokud se nepotkají, nic se neděje.
Dále se pak vysílají znovu po nejmenší hodnotě hrany. Toto se děje, dokud se celá kostra nenajde (všechny uzly náleží stejné množině). Tento algoritmus se nejčastěji využívá v
telekomunikačních sítích, kde neznáme celou topologii grafu.
