Tarry:
Hladáme taký sled ktorý začne v bode s, prejde všetkými hranami a skončí v bode s
Začnem v bode s a priradím k nemu incidentnú hranu podľa dvoch pravidiel:
1) Každú hranu môžem v jednom smere použiť iba raz
2) Naspäť po tej istej hrane môžem ísť iba ak nie je žiadna iná možnosť
Zapíšem si ju a aj smer v ktorom som ju použil
Ak takú hranu nenájdem, končím a zapísané hrany tvoria Tarrryho sled
---
Základný:
Každý vrchol bude mať dve značky, t a x; t bude dlžka, x bude predposledný vrchol
Začiatočný vrchol bude mať t = 0, ostatné budú mať nekonečno; x budú mať všetci nula
V orientovanej hrane (i,j) budem porovnávať dlžku vo vrchole j či nie je väčšia ako
dlžka vo vrchole i + ohodnotenie tej hrany ktorá ich spája
Ak áno, toto bude nová dlžka v bode j a značka x(j) bude i
Ak nie, toto je najkratšia orientovaná cesta
Dijkstrov:
Inicializácia je podobná ako v Základnom, ale značka t má dva druhy: dočasná a definitívna
Taktiež si na začiatku vyberem riadiaci vrchol r, on jediný bude mať definitívnu značku
V druhom kroku kontrolujem či aktuálny vrchol v nie je riadiacim
Ak áno, kontrolujem jeho značku t, ak je menšia než nekonečno, toto je dlžka cesty
Zostrojím ju pomocou smerníkov
Ak nie, kontrolujem všetky hrany (r,j), kde j má dočasnú značku podobne ako v Základnom:
Ak dlžka vo vrchole j je väčšia ako dlžka vo vrchole r + ohodnotenie hrany ktorá ich spája:
Toto je nové t vo vrchole j
Kontrolujem všetky vrcholy s dočasnou značkou, vyberám ten s najmenšou značkou t
Toto bude nový riadiaci vrchol a jeho značka sa mení na definitívnu
Floydov:
Zostrojím maticu C, kde na hlavnej diagonále budú nuly a všade inde bud c(i,j) alebo nekonečno
podla toho či tá hrana patrí do množiny H alebo nie
Podobne zostrojím maticu X, kde budú na hlavnej diagonále íčka, ak hrana patrí do H íčko, ak nie tak nekonečno
Pre všetky i != k a cik != nekonečno a všetky j != k a ckj != nekonečno:
Zaradom porovnávam či cij > cik + ckj, ak áno, toto bude nové cij a xij bude xkj
Label-set a Label-correct:
Inicializácia ako v Základnom ale mám aj množinu epsilon, v ktorej je na začiatku len prvý vrchol
Vyberiem riadiaci vrchol z epsilonu a všetky hrany, ktoré z neho vychádzajú kontrolujem:
Ak dlžka vo vrchole j je väčšia ako dlžka vo vrchole r + ohodnotenie hrany ktorá ich spája, toto bude nové t(j)
j sa pridá do epsilonu
Opakujem až kým epsilon nie je prázdny
---
Prehľadávanie do hlbky:
Mám triviálny strom T s jedným vrcholom, značku p(v) = 1 a k = 1
Ak T neobsahuje všetky vrcholy, nájdem hraničnú hranu s maximálnou značkou p(v), ak obsahuje, končím
Priradím túto hranu do T, zväčším k o jednu a toto bude nové p(v)
Prehľadávanie do šírky:
To isté ako do hlbky ale hľadám minimálnu značku p(v)
---
Kruskal I:
Najlacnejšia kostra = zoradím vzostupne
Zoradím hrany podľa ceny, vyberiem prvú hranu, ak už s vybranými hranami netvorí cyklus, zaradím ju do kostry
Opakujem až kým sa počet vybraných hrán nerovná počtu vrcholov - 1 alebo kým postupnosť nie je prázdna
Kruskal II:
Najdrahšia kostra = zoradím zostupne
Zoradím hrany podľa ceny, označím každý vrchol i značkou k = i, vyberiem prvú hranu a kontrolujem:
Ak sa značky vrcholov v hrane nerovnajú, zarad hranu do kostry a zmeň k značku vrcholov na rovnakú
Ak sa značky k rovnajú, tieto vrcholy sú v tom istom komponente
Ak zisťujem komponenty, nemusím na začiatku zoradovať hrany podla ceny ale môžem lubovolne
Hladanie maximálne priepustnej cesty:
Zostroj najdrahšiu kostru, nájdi v nej cestu, toto je maximálne priepustná cesta
Nie je optimálna kvôli prejdenej vzdialenosti
Hladanie najkratšej maximálne priepustnej cesty:
Nájdi maximálne priepustnú cestu, C je jej priepustnosť
Vytvor graf, ktorý bude mať iba hrany s priepustnosťou >= C, najdi najkratšiu u-v cestu v tomto grafe
---
Výpočet najkratšej u-v cesty:
Monotonne očísluj, pre každý vrchol daj značky t a x, počiatočný vrchol bude mať t nula, ostatné nekonečno
x budú mať všetci nula.
Zaradom pre všetky vrcholy kontrolujem vrcholy ich výstupnej hviezdy:
Ak dlžka vo vrchole w je väčšia než dlžka vo vrchole v + dlžka hrany ktorá ich spája, toto bude nové t(w)
x(w) = v
---
Najskôr možné začiatky:
Monotonne očísluj, prirad značky z=0 a x=0, pre všetky vrcholy výstupnej hviezdy každého vrchola kontroluj:
Ak z vrchola w je väčšie než z vrachola v + ohodnotenie vrchola v, toto je nové z(w)
Trvanie projektu je najväčšie z(w)+c(w) zo všetkých vrcholov s výstupnim stupňom nula
Najneskôr nutný koniec:
Monotonne očísluj, prirad značky k = trvanie projektu a y=0, postupne odzadu kontroluj výstupnú hviezdu každého vrchola:
Ak k vrchola v je väčšie než k vrchola w - ohodnotenie vrchola w, toto je nové k(v)
---
Konštrukcia eulerovskeho ťahu:
Začni ťah z lubovolneho vrchola z, predlžuj kým sa dá, ukončíš vo vrchole z
Nájdi vrchol ktorý má nepoužitú hranu, ak neexistuje našiel si uzavretý eulerovský ťah
Ak existuje, vytvor druhý ťah, predlžuj ho nepoužitými hranami kým sa da, ukonči kde si začal
Rozdel pôvodny ťah na z-v ťah T1 a v-z ťah T2, celý ťah T = T1 + S + T2, nájdi nepoužitú hranu atd...
Fleuryho hladanie eulerovskeho ťahu:
Začni v lubovoľnom vrchole a s ním incidentnú hranu zarad to ťahu
Vyber dalšiu hranu tak aby sa graf nerospadol na dva netriviálne komponenty alebo netriviálny komponent a začiatok ťahu
Opakuj až kým si nepoužil všetky hrany
Labyrintové hľadanie uzavretého eulerovskeho ťahu:
Začni z ľubovoľného vrchola, znač si smer použitia hrán a hrany prvého príchodu
Zaznamenaj si poradie hrán v ktorom sa vyskytujú po druhýkrát, každú hranu môžeš v jednom smere použiť iba raz
Najskôr vyberaj nepoužité hrany, potom raz použité hrany a nakoniec hrany prvého príchodu
Ak žiadna z tých hrán neexistuje, spätná postupnosť je eulerovský ťah
Ak áno, opakujem
---
Edmondsovo riešenie úlohy čínskeho poštára:
Nájdi vrcholy s nepárnym stupňom (párny počet), sprav z nich úplný graf G', v grafe urob najlacnejšie úplné párenie
Hrany párenia pridaj do pôvodného grafu a zostroj najkratší eulerovský ťah
Hrany párenia nahrad najkratšími cestami, dostal si najkratší eulerovský uzavretý sled
---
Pažravá metoda:
Začni v ľubovoľnom vrchole a vyber najlacnejšiu incidentnú hranu
Vyber najlacnejšiu hranu incidentnú s posledným použitým vrcholom a ktorá sa nespája s už použitým vrcholom
Opakuj až kým si nevybral n-1 hrán, uzavri cyklus, každú hranu nahrad najkratšou cestou v pôvodnom grafe
Zdvojenie kostry:
Zostroj najlacnejšiu kostru, zostroj v nej sled obsahujúci každú hranu 2krát
Prechádzaj sled a ak nájdeš opakujúce sa vrcholy, premosti ich priamou hranou
Kostra a párenie:
Zostroj najlacnejšiu kostru, nájdi v nej všetky vrcholy nepárneho stupňa, zostroj z nich úplný graf G'
V grafe G' nájdi najlacnejšie úplné párenie, hrany párenia pridaj do kostry, zostroj eulerovský ťah
Prechádzaj eulerovský ťah a ked nájdeš opakujúce sa vrcholy, premosti ich priamou hranou
---
Heuristika na hľadanie váženého p-mediánu:
Rozdeľ vrcholy na dve množiny, polož i je od 1 po veľkosť prvej množiny a j je od 1 po veľkosť druhej množiny vrátane
Hľadaj také i a j aby D'p(i,j) = (Dp zjednotenie {uj}) - {vi} bolo f(D'p) < f(Dp)
Ak si našiel, končíš, ak nie, Dp = D'p(i,j) a opakuj
---
Ford-Fulkerson:
Zvoľ si začiatočný tok, napríklad nulový, nájdi zväčšujúcu polocestu
Ak neexistuje, tok je maximálny, ak áno a má rezervu:
tok sa nemení ak hrana neleží na zväčšujúcej poloceste
nový tok = tok + rezerva ak hrana leží v smere orientácie
nový tok = tok - rezerva ak hrana leží proti smeru orientácie
opakuj
---
Sekvenčné farbenie grafu:
Zaradom prejdi všetky vrcholy a zafarbi ich tak aby susedia neboli rovnako zafarbení
Potrebujem najviac toľko farieb aký je najväčší stupeň vrchola zo všetkých vrcholov + 1
Paralelné zafarbenie grafu:
Zorad vrcholy podľa stupňa a polož množinu farieb, prechádzaj vrcholy a kontroluj:
Ak sused nie je zafarbený farbou j, použi farbu j
Ak áno, zvýš počet farieb a opakuj až kým nebudú zafarbené všetky vrcholy
vypocet najkratsej u-v cesty