A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Jarníkův algoritmus (v zahraničí známý jako Primův algoritmus) je v teorii grafů algoritmus hledající minimální kostru ohodnoceného grafu. Najde tedy takovou podmnožinu hran grafu, která tvoří strom obsahující všechny vrcholy původního grafu a součet ohodnocení hran z této množiny je minimální. Poprvé algoritmus popsal Vojtěch Jarník roku 1930, později byl znovuobjeven roku 1957 Robertem Primem a poté ještě jednou roku 1959 Edsgerem Dijkstrou. V zahraničí se téměř výlučně používá označení Primův algoritmus, vzácně pak Jarníkův algoritmus nebo DJP algoritmus.
Popis
Algoritmus začíná s jedním vrcholem a postupně přidává další a tím zvětšuje velikost stromu do té doby, než obsahuje všechny vrcholy.
- Vstup: souvislý ohodnocený graf
- Inicializace: , kde je libovolný vrchol z ,
- Opakuj dokud není :
- Vyber hranu z s minimální cenou tak, že je ve a není ve
- Přidej do , přidej do
- Výstup: je minimální kostra grafu
Časová složitost
Datová struktura s ohodnocením hran | Celková časová složitost |
---|---|
matice sousednosti | V2 |
binární halda (v pseudokódu níže) a seznam sousedů | O((V + E) log(V)) = E log(V) |
Fibonacciho halda a seznam sousedů | E + V log(V) |
Jednoduchá implementace s použitím reprezentace grafu pomocí matice sousednosti a prohledáváním pole cen má časovou složitost O(V2). S použitím binární haldy a seznamu sousedů dosáhneme složitosti O(E log V), kde E je počet hran a V je počet vrcholů. S použitím sofistikované Fibonacciho haldy složitost snížíme až na O(E + V log V), což je obzvláště rychlé u grafů, kde E je .
Příklad
Obrázek | Popis | Dosud neviděn | Sousedé | Dosavadní řešení |
---|---|---|---|---|
![]() |
Toto je náš původní ohodnocený graf. Není to strom, protože definice stromu požaduje, aby v grafu nebyly žádné kružnice a tento graf kružnice obsahuje. Čísla poblíž hran označují jejich cenu. Žádná hrana zatím není označena a vrchol D byl vybrán náhodně jako startovní vrchol. | C, G | A, B, E, F | D |
![]() |
Druhý vybraný vrchol je nejbližší k vrcholu D: cena hrany do A je 5, do B je 9, do E je 15 a F je 6. Cena hrany do bodu A (5) je nejnižší, použijeme tedy (a v našem diagramu vyznačíme) tuto hranu. | C, G | B, E, F | A, D |
![]() |
Dalším vybraným vrcholem je nejbližší vrchol buď k D nebo k A. Cena hrany z D do B je 9 a z A do B je 7, do E je 15 a do F je 6. Cena poslední jmenované hrany je nejnižší, zvolíme tedy hranu z D do F. | C | B, E, G | A, D, F |
![]() |
V tomto případě je nejkratší hrana z A do B. |
žádný | C, E, G | A, D, F, B |
![]() |
V tomto případě je nejkratší hrana z B do E. Další dvě hrany obarvujeme na červeno, protože je už nebudeme moci použít. Nechceme, aby vznikla kružnice. | žádný | C, G | A, D, F, B, E |
![]() |
Jediné zbývající vrcholy jsou C a G. Hrana z E do C váží 5 a hrana z E do G váží 9. Vybíráme tedy hranu do C. Hranu z B do C obarvujeme na červeno. | žádný | G | A, D, F, B, E, C |
![]() |
Zbývá nám už jenom vrchol G. Hrana do F váží 11 a do E 9. Vybíráme tedy hranu do E. Všechny vrcholy jsou už součástí stromu, získali jsme tedy minimální kostru grafu (na diagramu je obarvená zelenou). Celková váha kostry je 39. | žádný | žádný | A, D, F, B, E, C, G |
Implementace v pseudokódu
S použitím haldy
- Inicializace
- vstupy: Graf, funkce vracející ohodnocení hran a startovní vrchol
na začátku jsou všechny vrcholy nastaveny na status dosud neviděn, startovní vrchol je umístěn do grafu a všechny hrany do haldy tak, aby vracela hranu s nejnižší vahou.
Pro každý vrchol v grafu nastav min_vzdálenost vrcholu na ∞ nastav otec vrcholu na null nastav min_seznam_sousedů vrcholu na prázdný_seznam nastav je_v_Q vrcholu na true nastav vzdálenost startovního vrcholu na nula přidej do haldy Q všechny vrcholy v grafu.
- Algoritmus
V popisu algoritmu výše,
- nejbližší vrchol je Q
- okraj je v v Q, kde vzdálenost v < ∞ poté, co je nejbližší vrchol vyjmut z haldy
- dosud neviděn je v v Q, kde vzdálenost v = ∞, co je nejbližší vrchol vyjmut z haldy
Cyklus selže pokud halda vrátí nulu. Seznam sousedů je vytvořen tak, aby mohl vrátit orientovaný graf.
- časová složitost: V na cyklus, log(V) na vyjmutí hrany z haldy
Dokud poslední_přidaný = vrať minimum v Q nastav je_v_Q čeho poslední přidaný na false přidej poslední_přidaný na (min_seznam_sousedu čeho (otec čeho poslední_přidaný)) přidej (otec čeho poslední_přidaný) do (min_seznam_sousedů čeho poslední_přidaný)
- časová složitost: E/V, průměrný počet vrcholů
pro každý soused čeho poslední_přidaný Jestliže (je_v_Q čeho soused) a zároveň (váha(poslední_přidaný, soused) < min_vzdálenost čeho soused) nastav otec čeho soused na poslední_přidaný nastav min_vzdálenost čeho soused na váha(poslední_přidaný, soused)
- časová složitost: log(V), výška haldy
uprav soused v Q, podle min_vzdálenost
Důkaz správnosti
Nechť je souvislý, ohodnocený graf. S každou iterací Jarníkova algoritmu je přidána hrana, která spojuje vrchol v podgrafu s vrcholem mimo podgraf. Jelikož je souvislý, musí existovat cesta mezi všemi dvojicemi vrcholů. Nechť výstup Jarníkova algoritmu je a je minimální kostra grafu . Jestliže , pak je minimální kostra grafu. V opačném případě, nechť je první hrana přidaná během konstrukce , která není v a je množina vrcholů spojených hranami přidanými před . Pak jeden konec hrany je v a druhý není. Jelikož je kostra grafu , pak musí existovat cesta v spojující oba konce hrany. Někde v této cestě se musí objevit hrana spojující vrchol ve s vrcholem, který není ve . Ve chvíli, kdy je přidána k by mohla být místo ní přidána také , pokud by ovšem vážila méně. Jelikož ale byla přidána , můžeme soudit, že
Nechť je graf získaný odstraněním a přidáním z . Je snadné ukázat, že je souvislý, má stejný počet hran jako a celková váha hran není vyšší než u . je tudíž minimální kostra grafu a obsahuje
Antény
Chemické zdroje elektriny
Chladenie v elektrotechnike
Elektrická sústava automobilu
Elektrická trakcia
Elektrické prístroje
Elektrické súčiastky
Elektrické spotrebiče
Elektrické stroje
Čítanie (elektrotechnika)
Činný výkon
Štatistická dynamika
Živý vodič
Admitancia
Antiparalelné zapojenie
Asynchrónny motor
Blúdivý prúd
Bočník (elektrotechnika)
Diak (polovodičový prvok)
Displej s kvapalnými kryštálmi
Elektrická inštalácia
Elektrická rezonancia
Elektrická sila
Elektrická vodivosť
Elektrické zariadenie
Elektrický obvod
Elektrický zvonec
Elektroenergetika
Elektromer
Elektrometer
Elektromobil
Elektromotor
Elektromotorické napätie
Elektrotechnický náučný slovník
Elektrotechnika
Elektrotechnológia
Fázor
Faradayova klietka
Frekvencia (fyzika)
Graetzov mostík
Impedancia
Indukčnosť
Induktancia
Istič
Izolácia (elektrotechnika)
Izolant
Jadro vodiča
Jednobran
Jednosmerný prúd
Joulovo teplo
Katóda
Koaxiálny kábel
Kompenzácia účinníka
Konduktometria
Konektor (elektrotechnika)
Korónový výboj
Lanko (elektrotechnika)
Leptanie
Logické hradlo
Magnetická susceptibilita
Magnetizácia (veličina)
Merný elektrický odpor
Mobilné zariadenie
Napájací zdroj
Napäťový chránič
Napäťový násobič
Nortonova veta
Odpínač
Odpojovač
OLED
Olovený akumulátor
Paralelné zapojenie
Peltierov článok
Plošná hustota elektrického prúdu
Poistka (elektrotechnika)
Posuvný prúd
Prúdový chránič
Prenosové médium
Prieletový klystrón
Primárny elektrochemický článok
Reaktancia
Rekuperácia (dopravný prostriedok)
Relé
Reproduktorová výhybka
Rezistancia
Rozhranie (interface)
Sériové zapojenie
Seebeckov jav
Sekundárny elektrochemický článok
Settopbox
Skrat
Sonar
Spínač
Spínaný zdroj
Straty v mikropásikových vedeniach
Striedavý prúd
Stupeň ochrany krytom
Svetelná výbojka
Symetrizačný člen
Technická normalizácia
Tepelné relé
Tepelne vodivostný detektor
Termočlánok
Théveninova veta
Transformátor
Transformátor s fázovou reguláciou
Trojfázová sústava
Tuhá fáza (elektronika)
Tyratrón
Usmerňovač (elektrotechnika)
Uzemnenie
Uzol (vodiče)
Vírivý prúd
Výbojka
Varistor
Ventilátor
Vodič (elektrotechnika)
Voltov stĺp
Vstavaný systém
Zásuvka (elektrotechnika)
Zdroj (elektrotechnika)
Zisk antény
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk