1) Definice základních pojmů Graf- v teorii grafů se grafem rozumí objekty popsané množinou hran a množinou vrcholů orientovaný X neorientovaný Neorientovaný graf- uspořádaná trojice množiny vrcholů, množiny hran a incidence G=(V,X,p) Incidence p grafu přiřazuje každé jeho hraně neuspořádanou dvojici vrcholů. Říká, které dva vrcholy ohraničují hranu. Daný vrchol je krajním příslušné hrany. Stupeň vrcholu st(v)- udává počet hran incidujících s vrcholem. Mohutnost množiny vrcholu- počet vrcholů v celém grafu n = /V/ Mohutnost množiny hran- počet hran v celém grafu q = /X/ 2) Podgrafy, různé typy podgrafů Podgrafem grafu G = (V,X,p) rozumíme graf G = (V,X,p) pro který platí: V je podmnožinou množiny V X je podmnožinou množiny X a každá hrana grafu musí incidovat se stejnou dvojicí vrcholů jako v původním grafu. Zkráceně zapisujeme: G je podmnožinou množiny G Typy: - Podgraf indukovaný množinou vrcholů - Podgraf indukovaný množinou hran - Podgraf indukovaný množinou vypuštění vrcholů 3) Faktorový podgraf, Komplementární grafy Faktorovým podgrafem (faktorem) grafu G = (V,X,p) rozumíme graf G = (V,X,p) pro který platí: V = V , X je podmnožinou množiny X, p(h) = p(h). Komplementární (doplňkový) graf- je doplněk k původnímu obyčejnému grafu a vždy sjednocení musí tvořit kompletní graf. 4) Komplementární grafy, Autokomplementární grafy Komplementární grafy- viz. otázka 3 Autokomplementární grafy- 2 grafy G1 a G2 musí být zároveň Doplňkové a Izomorfní. Nutné podmínky Autokomplementárních grafů v grafu G. graf je kompletním grafem počet hran grafu je celočíselně dělitelný dvěma 5) Izomorfismus grafů 2 grafy jsou izomorfní, když se liší pouze nakreslením (pojmenováním) vrcholů a hran, incidence zůstává stejná. Grafy které jsou izomorfní mají stejný počet vrcholů, hran a také mají stejný počet vrcholů stejného stupně. 6) Matice na grafech Matice přilehlosti (sousednosti) vij = 0, hrana neexistuje vij = 1, hrana existuje řádkové součty matice vyjadřují stupeň vrcholu vi sloupcové součty matice vyjadřují stupeň vrcholu vj Matice incidence bij = 0, vrchol neinciduje s hranou bij = 1, vrchol inciduje s hranu řádkové součty matice vyjadřují stupeň vrcholu vi sloupcové součty matice vyjadřují incidenci hrany hj Matice přímých vzdáleností dij = 0, pro i = j (na diagonále) dij = o(h)-ohodnocení hrany, spojuje-li vrcholy jedna hrana dij = ∞- nespojuje-li vrcholy jedna hrana 7) Způsoby prezentace grafů Množinová (výčtová) prezentace grafu Výčet hran a jejich incidence Výčet hran incidujících s každým vrcholem Výčet uspořádaných dvojic vrcholů Výčet množin sousedů Maticová prezentace grafu viz. otázka 6 Graf 8) Sled, Tah, Cesta Sled- střídavá posloupnost vrcholů a hran ve které se vrcholy i hrany opakují, začíná a končí ve vrcholu sled:{v1, h1, v2, h6, v5, h6, v2} Tah- je sled ve kterém se neopakuje žádná hrana, vrcholy se opakovat mohou (např. domeček jedním tahem- hrany se neopakují vrcholy ano) tah:{v1, h1, v2, h6, v5, h5, v1} Cesta- je tah ve kterém se neopakuje žádný vrchol cesta: m(u,v) {v1, h2, v2} Speciální případy: Uzavřený tah- klasický tah ale začíná a končí ve stejném vrcholu
Uzavřená cesta- (kružnice) 9) Theseova metoda Algoritmus rozmotávání niti. a) Theseus vstoupí do komnaty X, kde je Minotaurus ->theseus je v cíli, zabije Minotautra a po cestě určené odmotanou nití se vrátí k Adriané(počátek) b) Theseus vstoupí do komnaty X, kde není Minotaurus a je slepá(ustí pouze jedna chodba) ->Theseus se vrátí do předchozí komnaty, označí prošlou chodbu barvou, protože ji prošel v obou směrech c) Theseus vstoupí do komnaty X, kde není Minotaurus a není slepá -> možnosti: 1)theseus uzavřel příchodem do komnaty X kružnici, proto se vrátí zpět, namotává nit a obarví chodby kružnice. Kružnice je cesta ve které je výchozí komnata schodná s koncovou. 2) Theseus uzavřel kružnici, všechny chodby ústící do X jsou už zabarveny až na chodbu kterou Theseus do X přišel-touto chodbou se vrátí, namotává nit a chodbu zabarví. 3)Theseus neuzavřel kružnici, existuje však alespoň jedna chodba, která není zabarvená-Theseus ji později použije a pokračuje v rozmotávání niti. Algoritmus při namotávání niti. Namotáváním se Theseus dostane do komnaty X. Mohou nastat následující situace: α) analogie a) nastat nemůže β) analogie b) nastane když X=A (prošel všude a nenašel Minotaura) γ) analogie c) mohou nastat případy αa)z komnaty vede chodba, kterou pokračuje nit, ostatní chodby jsou označeny barvou – Theseus se vydá po niti a namotává klubko βb) z komnaty vede alespoň jedna neoznačená chodba, kterou T. nešel – zvolí jednu z nich a prochází jí rozmotávaje nit γc) z komnaty X nevede ani označená ani neoznačená chodba, kromě té označené kterou přišel – T. je ve výchozí komnatě 10) Souvislost grafů, Číslo vrcholové a hranové souvislosti grafů Souvislost grafů Sled, Tah, Cesta- viz. otázka 8 Graf nazýváme souvislým pokud mezi libovolnou dvojicí vrcholů u,v existuje alespoň jedna cesta. Délka cesty: (součet hran) m (u,v) = ∑ o(h) Vzdálenost dvou vrcholů: d (u,v) = min{∑ o(h)} Číslo hranové souvislosti γ(G)- je minimální počet hran, který je nutné odstranit z grafu, aby vznikl nesouvislý (skládá se ze 2 komponent mezi nimiž neexistuje cesta) nebo diskrétní (pouze množina vrcholů) graf. γ(G) = 0, pro nesouvislé grafy γ(G) = 1, pro grafy obsahující most γ(G) = n-1, pro kompletní grafy Most-je hrana grafu jejímž odstraněním se graf rozpadne na více komponent. Číslo vrcholové souvislosti δ(G)- je minimální počet vrcholů, které je nutno odstranit z grafu (včetně incidujících hran), tak aby vznikl nesouvislý, diskrétní, nebo triviální (pouze jeden vrchol) graf. δ(G) = 0, pro nesouvislé grafy δ(G) = 1, pro grafy s artikulací δ(G) = n-1, pro kompletní grafy Artikulace- je vrchol grafu jehož odstraněním z grafu se zvýší počet komponent alespoň o jednu. 11) Orientované grafy, Matice předchůdců, Matice následovníků, Matice incidence Orientovaný graf- G = (V,Y,p) Množina Y je tvořena uspořádanými dvojicemi [u,v] prvků množiny V, přičemž u ≠v a každá takováto dvojice existuje nejvýše jednou. Prvky množiny Y nazýváme orientovanými hranami (orhranami). Každá orhrana má orientaci vyjádřenou šipkou. (orientace hrany jedním směrem- např. jednosměrky v silniční dopravě) Matice incidence (k vyjádření orientovaného grafu) 1 -hrana vychází z vrcholu -1 -hrana vchází do vrcholu Matice sousednosti (následovníků, předchůdců) 12) Délka cesty, Vzdálenost vrcholů Délka cesty: mezi dvěma vrcholy u, v є V hranové ohodnocení grafu G je definováno jako:
m (u , v )
oh)
hm ( u , v )
1
Vzdálenost dvou vrcholů: u, v є V grafu G=(V,X,p) je definována:
d (u , v ) min o ( h ) , kde o(h) je ohodnocení hrany m ( u , v )M hm ( u ,v ) h X vyjadřující délku a M je množina všech cest mezi vrcholy u a v.
v p do množiny W,
4d) Ohodnocení vrcholu sloupce
v p vr V \ W
v0 , v1 ,.......,v n . Ohodnocení hran o(h) vyjadřuje jejich dálku.
vj
množiny
V \W
podle následujících pravidel:
- je-li vrchol
v p , vk V grafu G V , X , p pomocí tabulkové metody.
a platí-li:
K výpočtu minimální cesty touto metodou potřebujeme tabulku, která sestává z n+2 sloupců a n+1 řádků (n je počet vrcholů grafu
V
- položíme:
)). V tabulce označíme n sloupců označením vrcholů grafu
vi , i 1,..., n ,
vi , i 0,..., n 1 .
respektive
příslušnému
vrcholu
v j V v p V
z počátečního vrcholu
určuje
délku
minimální
v j V
do vrcholu
v j ) ).
v j V
dvojicí čísel
vrchol
Metoda
v j V
spočívá
v ohodnocování
v , d , kde v i
j
i
vp a v j
vrcholů
grafu
je vrcholem předcházejícím
na aktuálně známé cestě
mv p , v k
a
dj
je
délkou této cesty (součet ohodnocení hran této cesty). Algoritmus řešení: 1. Krok 1a) Zvolíme počáteční vrchol cesty
v p V
1b) Zvolíme koncový vrchol cesty
vk V
sloupce
v j ohodnotíme dvojicí v p , d j
do množiny W byl zařazen vrchol
-
v p vk
5. Krok Provedeme rekonstrukci minimální cesty tak, že určíme posloupnost vrcholů
vk vk0 , vk1 , vk2 , ....., vkr v p .
Obrácením
této
posloupnosti a doplněním příslušných hran obdržíme minimální cestu
m * v p , v k . S rekonstrukcí cesty začneme v koncovém vk .
Položíme
v k1 předcházejícího
vrchol
sloupce odpovídajích vrcholu
přepíšeme do
v p vypustíme z tabulky
Krok
p, d , kde
v j V , j p ohodnotíme dvojicí
j
d j jestliže h X p h v p , v j
d j o v p , v j jestliže h X p h v p , v j
4. Krok Obecný krok: 4a) Z množiny vrcholů
vr V \ W
v j V \ W
vybereme vrchol
, pro který platí:
d r min d j v j V \W
Poznámka: Je-li takovýchto vrcholů více, vybereme libovolný z nich, resp. vybereme vrchol s nejmenším indexem j. 4b) Položíme
d ´j d p ov p , v j
v k0 v k .
vk0 vk
Index na
k1
vrcholu
nejkratší
cestě
v k0 . Dále se přesuneme do řádku
tabulky odpovídajícímu vrcholu
v k1 .
Index
k2
vrcholu
v k 2 nalezneme jako první číslo ve dvojici ohodnocení v průsečíku řádku
a
sloupce
odpovídajích
vrcholu
v k1 .
Analogicky
pokračujeme dále do té doby, dokud se nedostaneme do
Ostatní vrcholy grafu čísel
nalezneme jako první číslo dvojice ohodnocení v průsečíku řádku a
D
2d) Sloupec odpovídající vrcholu 3.
d p 0
- vrchol
vrcholu
2. Krok 2a) Počáteční vrchol cesty ohodnotíme dvojicí čísel (0,0), ostatní vrcholy dvojicí (0, ∞) 2b) Počáteční vrchol cesty zařadíme do množiny W 2c) Ohodnocení počátečního vrcholu
d j d p ov p , v j
vp
4g) 4. krok opakujeme do té doby dokud nenastane jedna ze situací: všechny vrcholy již byly zařazeny do množiny W
. Podle definice
představuje délka minimální cesty vzdálenost vrcholů ( d (v p ,
cesty
sousedním vrcholem vrcholu
d j d ´j
Předposlední
). Složka vektoru definitivního ohodnocení dj odpovídající
vj
- dále položíme:
sloupec označíme W (množina definitivně označených vrcholů grafu), poslední sloupec potom D (vektor definitivního ohodnocení vrcholů grafu
v j V
v p vypustíme z tabulky
4f) Změníme (případně nezměníme) ohodnocení zbylých vrcholů
Algoritmus:
(n
přepíšeme do
D
4e) Sloupec odpovídající vrcholu
13) Dijkstrův algoritmus - algoritmus nalezení minimální cesty Uvažujeme hranově ohodnocený, souvislý graf G=(V,X,p), kde V=
4c) Zařadíme
v p vr
počátečního vrcholu
vk r v p .
Pokud v grafu existuje mezi zvoleným a počátečním a koncovým vrcholem více minimálních cest je možné daný postup opakovat a zjistit tak všechny cesty. 14) Tabulková metoda určování minimální cesty 15) Floydův algoritmus - se používá pro nalezení všech nejkratších orientovaných cest mezi všemi dvojicemi uzlů (pro jednoduchý orientovaný graf). autorem je R.W. Floyd 16) Spolehlivost cesty, Nejspolehlivější cesta, Algoritmus Hrany grafu jsou ohodnoceny (může jít například o pravděpodobnost že na úseku komunikace nedojde k havárii), problémem je vyhledání cesty, která je z hlediska pravděpodobnosti nejprůchodnější- „nejspolehlivější“ Spolehlivost cesty : s(m(u,v)) = Π p(h) Π- součin p(h)- ohodnocení hrany, <0,1> Nejspolehlivější cesta: s(m*(u,v)) = max {s(m(u.v))} Algoritmus: Uvažujeme obyčejný, souvislý, hranově ohodnocený, neorientovaný graf G. 1.krok: v grafu G zvolíme počáteční vrchol cesty – u a koncový vrchol – v 2.krok: pokud ohodnocení hran vyjadřuje pravděpodobnost uspěšného průchodu hranou, pokračujeme krokem 3 Nebo: Pokud ohodnocení hran vyjadřuje pravděpodobnost neuspěchu průchodu hranou, změníme původní ohodnocení následovně:
2
p ( h) 1 p ( h) d
dále položáme
p ( h) p ( h) a
pokračujeme krokem 3
o(h) log p (h)
3.krok: nově ohodnotíme hrany grafu:
4.krok:v grafu s ohodnocením podle kroku 2 vyhledáme minimální cestu. Tato cesta je zároveň nejspolehlivější cestou. 17) Kapacita cesty, Cesta s maximální kapacitou, algoritmus Ohodnocení hran představuje kapacitu (propustnost) komunikací Kapacita cesty: K(m(u,v)) =
min o(h)
hm ( u ,v )
Cesta s maximální kapacitou: K(m*(u,v)) =
max
m ( u ,v )M
{K(m(u,v))}
Algoritmus: 1.krok: zvolíme počáteční vrchol cesty – u a koncový vrchol – v. 2.krok: Zvolíme libovolnou množinu žezovou množinu XR 3.krok: Určíme K= max hX R
R V
a určíme odpovídající
o(h)
4.krokV grafu zkrátíme všechny hrany, pro které o(h)>=K. 5.krok: Porovnáme koncový a počáteční vrchol cesty, mohou nastat dva případy: -zkrácením dojde ke ztotožnění vrcholů u a v, potom následuje přechod na 6.krok -zkrácením hran nedojde ke ztotožnění vrcholů u a v, v tomto případě následuje přechod na krok 2 6.krok: v původním grafu zakreslíme faktorový podgraf, jehož množina hran je množinou všech zkrácených hran. V tomto podgrafu vyhledáme cestu, která je cestou s maximální kapacitou 18) Maximální dráha, Algoritmus Dráha: Orientovaná cesta m [u,v] Dráhou nazveme orientovaný sled, ve kterém se neopakuje žádný vrchol. Algoritmus: 1.krok: každému vrcholu orgrafu vi i=0,1,2,…..,n
V
2.krok: hledáme hranu orgrafu h Y , platí:
t j t i o vi , v j
přiřadíme hodnotu ti=0,
ph vi , v j , pro kterou
orhrana splňující nerovnost existuje, potom vrcholu vj přiřadíme nové ohodnocení:
t j ´ t i o vi , v j
,
změníme ohodnocení tj = tj´a pokračujeme krokem 2 orhrana splňující nerovnost neexistuje, pokračujeme krokem 3. 3krok: posledně určená hodnota tn udává délku maximální dráhy
m * u , v M , kde
4.krok: Dráhu Z nožiny
u= v0 a v = vn
m u , v určíme tak, že začneme ve vrcholu vk0 =vn . *
(v k )
vybereme uzel vk1
19) Síťová analýza, CPM (viz. vytisknuté listy) Síťová analýza V praxi se jedná o komplex činností, které na sebe časově a věcně navazují. Každá činnost vyžaduje určitý čas k realizaci, spotřebovává zdroje a vyžaduje lidskou aktivitu. Pro efektivní řízení systémů je potřebné: stanovení objektivně nutného času k realizaci projektu stanovení dílčích (etapových) časů používat efektivních prostředků pro kontrolu postupu prací Řídící systém- určuje strategii chování systému v čase Řízený systém- na základě řídících informací realizuje zamýšlenou činnost systému Řízení- je činnost vedoucí ke stanovení cílů řízeného systému Použití metod síťové analýzy v procesu řízení je vhodné zejména pro: sestavu plánů postupu prací řízeného objektu kontrolu průběhu prací (srovnávání skutečnosti s plánem) nápravu skluzů časového plánu opatřením vycházejícího z časového rozboru CPM (Critical Path Method) Pro projekty kde známe přesný čas trvání činností. U každého vrcholu jsou časové údaje. Vrchol- okamžik zahájení nebo ukončení činnosti. Ohodnocení hrany je čas strávený dobou činnosti.
20) PERT (viz. vytisknuté listy) Doba trvání činností se bude odhadovat. Časy: Optimistický (a), Pesimistický (b), Nejpravděpodobnější (m) Síťový graf – je orientovaný, neorientovaně souvislý, hranově ohodnocený, acyklický graf, vyjadřující závislost dílčích činností projektu. Vrchol síťového grafu – představuje časovou událost, kterou je začátek nebo konec činnosti. Hrana síťového grafu – představuje činnost, která klade nároky na čas, zdroje a má dynamický charakter. Činnost – je definována počátečním a koncovým vrcholem. Znázorňujeme ji orientovanou hranou. Kritická činnost – je činnost jejímž prodloužením doby trvání o libovolnou kladnou dobu e, dojde k prodloužení doby trvání celého projektu o dobu e. Kritická cesta – je sled kritických činností mezi začátkem a koncem projektu. Rozptyl – vyjadřuje míru rozptýlení hodnot náhodné proměnné okolo středu. Směrodatná odchylka – je druhá odmocnina z rozptylu. Měří variabilitu v původních jednotkách náhodné proměnné. Očekávaný čas trvání činnosti (střední hodnota) – převádí tři časové odhady dob trvání činnosti v jediný odhad střední hodnoty doby trvání činnosti. Pro potřeby určení času te byl sestaven vzorec: Rozptyl doby trvání činnosti – pro čas te byla hodnota rozptylu stanovena s využitím pravidla 3σ pro normální rozdělení pravděpodobnosti na: Nejdříve možný konec činností vcházejících do vrcholu i v E T – resp. nejdříve možný začátek činností vycházejících z vrcholu je dán součtem časů te, které tvoří maximální dráhu z vrcholu vo do vrcholu vi. Žádnou činnost nelze zahájit, dokud nejsou ukončeny všechny činnosti, které ji bezprostředně předcházejí. Čas i v E T chápeme jako střední hodnotu proměnné s normálním rozdělením pravděpodobnosti. Nejpozději nutný konec činností vcházejících do vrcholu i v L T – resp. nejpozději nutný začátek činností vycházejících z vrcholu je dán součtem časů te, které tvoří maximální dráhu z vrcholu vi do vrcholu vn. Aby nedošlo ke skluzu v době trvání projetu musí všechny činnosti vcházející do daného vrcholu být ukončeny v jistém časovém okamžiku, tak aby bylo možné realizovat následující činnosti v požadovaných termínech. Čas i v L T chápeme jako střední hodnotu proměnné s normálním rozdělením pravděpodobnosti. Směrodatná odchylka času i v E T – určí se analogicky podle definice času i v E T 21) Dopravní síť- definice, Tok na síti, vlastnosti, lineární model, Kirchhoffovy zákony Dopravní síť- je orientovaný, neorientovaně souvislý, hranově ohodnocený, acyklický graf Ohodnocení hrany- kapacita (propustnost) hrany c[h] ≥ 0 Dopravní síť obsahuje: zdroj- ze zdroje hrany pouze vycházejí ústí- do ústí hrany pouze vcházejí vnitřní vrcholy Tok na síti (y)- je funkce která keždé hraně sítě přiřadí reálnou hodnotu Nasycená orientovaná hrana: y[h] = c[h] Síť nazveme rovinnou, je-li graf rovinným- rovinně zakresleným orientovaným grafem. 22) Typy dopravních sítí Rovinná- Síť nazveme rovinnou, je-li graf rovinným- rovinně zakresleným orientovaným grafem. Hrany se nekříží. Všeobecná- všeobecná dopravní síť je prostorový graf (obsahuje protínající se hrany a nelze ji zakreslit, tak aby k protnutí nedošlo. Hrany se kříží. V sítích definujeme pojmy jako: Řezová množina, Kapacita řezové množiny Intervalově ohodnocená- hrany těchto sítí jsou ohodnoceny dvojicí čísel: b[h],c[h] 23) Ford-Fulkersonův algoritmus pro rovinné sítě Maximální tok v rovinné síti
3
Sestrojení maximálního toku v rovinné síti nasycováním hran 1. krok: V síti určíme nejvýše položenou dráhu m* [z, u]. Po této dráze vedeme tolik jednotek toku, aby došlo k nasycení alespoň jedné hrany. Nasycenou hranu označíme a v dalším postupu s ní neuvažujeme (označení hrany znamená její vyloučení z grafu). 2. krok: Postup podle 1. kroku opakujeme dokud existuje alespoň jedna nejvýše položená dráha m*[z, u] obsahující pouze nenasycené hrany. Jestliže taková dráha neexistuje, přejdeme na 3. krok. 3. krok: Sestrojený tok je maximálním tokem. Jeho hodnotu zjistíme tak, že sečteme tok vycházející ze zdroje po hranách končících v množině Ґ+z Sestrojení maximálního toku v rovinné síti snižováním kapacit 1. krok: Každou hranu dopravní sítě ohodnotíme číslem c(s čarou nad)[h] = c[h]. 2. krok: V síti určíme nejvýše položenou dráhu m*[z, u]. Na této dráze určíme minimální aktuálně platnou volnou kapacitu: MIN= minh náleží [z,u] {c(s čarou nad)[h] } 3. krok: O hodnotu MIN zmenšíme aktuálně platnou kapacitu všech hran nejvýše položené dráhy. c(s 2čárami)[h] = c(s čarou)[h] - MIN; h € m*[z, u] a položíme c(s čarou)[h] = c(s 2čarami)[h] Tímto postupem dojde k tomu, že minimálně jedna hrana bude mít kapacitu rovnou nule C(s čarou)[h] = 0. Hrany s nulovou kapacitou vypustíme z dalšího postupu. 4. krok: Postup podle kroku 2. a 3. opakujeme dokud se nám daří určovat nejvýše položená dráha obsahující pouze hrany s nenulovou kapacitou c(s čarou)[h]. Jinak následuje 5. krok. 5. krok: Určíme tok na hranách sítě podle následujících pravidel. Pro hrany, pro které je: • c(s čarou)[h] = 0 je hodnota toku y[h] = c[h], • c(s čarou)[h] = c[h] je hodnota toku y[h] = 0, • 0 < c (s čarou)[h]
y[vi, vj], toto pravidlo používáme dokud to lze 2b) - nacházíme-li se v označeném vrcholu vj € K, z množiny Ґ-vi vybereme vrchol vi a označíme indexem -j, pokud pro hranu [vi, vj] € platí Y [vi, vj] > 0 Kombinací pravidel a) a b) se snažíme označit ústí. Mohou nastat dvě možnosti: a)nepodařilo se označit ústí pokračuj 4. krokem,b) podařilo-li se označit ústí pokračujeme3. krokem 3. krok: Na označeném řetězci m(z,u) určíme: 3a) minh náleží(z,u) {c[h] - y[h] } - pro ohrany, které končí v uzlu označeném +i 3b) minh náleží(z,u) {y[h] } - pro ohrany, které začínají v uzlu označeném -j 3c) vezmeme menší z hodnot určených v krocích 3a) a 3b). O tuto hodnotu zvětšíme resp. zmenšíme hodnotu toku na orhranách pnslušného řetězce (hodnotu přičteme k toku hran řetězce končících ve vrcholu označeném indexem se znaménkem +; hodnotu odečteme od toku hran řetězce vycházejících z vrcholů označených indexem se znaménkem -). Tímto postupem dojde buď: - k nasycení minimálně jedné orhrany, nebo - k vynulování toku alespoň najedná orhraně. 3d) návrat na 2. krok. 4. krok: Tok v dopravní síti je tokem maximálním 25) Ford-Fulkersonův algoritmus pro intervalově ohodnocené sítě, přípustný tok
Určení maximálního toku v intervalově ohodnocené síti Existují praktické úlohy, ve kterých se setkáváme s intervalově ohodnocenými úseky sítě. V těchto sítích jsou orhrany ohodnoceny dvojicí čísel , přičemž 0 ≤ b[h] ≤ c[h]. Ohodnocení b[h] vyjadřuje hodnotu minimálního toku, který musí hranou protékat. Jestliže b[h] = 0 pro všechny hrany h € Y, jde o klasickou úlohu určení maximálního toku a postupujeme podle předešle popsaného algoritmu. Zatímco v dopravní síti vždy existuje nějaký tok (může být i nulový), v intervalově ohodnocené síti tomu tak nemusí být. Tok v intervalově ohodnocené síti jehož hodnoty na hranách splňují podmínku b[h] ≤ y[h] ≤ c[h] nazveme přípustným tokem. Postup při konstrukci maximálního toku na intervalově ohodnocené síti 1. krok: Vytvoříme novou (fiktivní) síť, která je tvořena: • původním grafem sítě D = (V, Y,p), propustnost původních hran změníme na c(s čarou)[h] = c[h] - b[h] • fiktivním zdrojem -z*, • fiktivním ústím – u*, • orientovanými hranami [z*, v] a [w, u*] s propustností b[w, v], • fiktivní orhranou [u, z] s kapacitou c[u, z] = ∞ 2. krok: Ve fiktivní síti určíme maximální tok - yzmax známým algoritmem, • pokud y -maxz =Suma h náleží Y [h], v síti D = (V,Y,p)existuje přípustný tok; pokračuj 3. krok • pokud y -maxz ≠Suma h náleží Y[h], přípustný tok v síti neexistuje=>neexistuje max.tok.konec 3. krokVrátímeSeDoPůvodníSítě.HodnPřípustnéhoTokuNaHranáchUrčím: y[h]=b[h]+y -max[h] 4. krok: V původní síti určíme max.tok značkovací metodou se změnou v pravidle b). Změna se týká výběru vrcholu vi € Ґ-vi. Jako vrchol vi,vyber vrchol, pro kt.platí: y[vi, vj] > b[h] 26) Aplikace úloh o tocích na dopravních sítích, Neadresné toky, Přiřazovací problém Aplikace Ford-Fulkersonovv metody - Přiřazovací problém Daná množ.prací U={u1,u2,.,ut},|U| = t a množina pracovníků V={v1,v2,....,vp}, |V|=p. Seřadíme pracovníky a práce. Mezi vi a vj vedeme orhranu pokud pracovník vi má kvalifikaci vykonávat práci uj. Do grafu přidáme fiktivní zdroj - z, fiktivní ústí - u a orhrany [z, vi], [uj, u]. Ohodnocení všech hran grafu položíme rovno jedné o[h] = 1. Dostaneme fiktivní dopravní síť Gp,t, ve které určíme maximální tok FordFulkersonov. Maximální tok ymaxz udává maximální přiřazení pracovníků k pracím. Pokud na hraně [z, vi] existuje tok y [z, vi] = 1; pracovník vi bude vykonávat práci. Pokud na hraně [uj, u] existuje tok y [uj, u] = 1; práce uj, bude vykonána. Pokud na hraně [vi, uj] existuje tok [vi, uj] = 1; pracovník vi bude vykonávat práci uj. Neadresné toky Řešíme-li dopravu jistého substrátu od dodavatelů Di ke spotřebitelům Sj po zadané síti, budeme postupovat následovně: • seřadíme dodavatele Di; i = 1,2,..., m a spotřebitele Sj; j =1,2,..., n • přidáme fiktivní zdroj - z, fiktivní ústí - u a fiktivní hrany [z, Di] a [Sj, u], • kapacitou hran [z, A] je množství substrátu dodávané dodavatelem A, • kapacitou hran [Sj, u] je množství substrátu požadované spotřebitelem Sj, • kapacita hran [Di, vr][vr, vs][vs, Sj] je kapa.konkrétních úseků doprav.sítě,přičemž vr V této síti určíme maximální tok F-F alg. Hodnota toku y [z, Di]; i = l,..., m určuje, jak bude využita kapacita dodavatele Di. Hodnota toku y[Sj, u]; j = l,..., n určuje, jak bude nasycen požadavek spotřebitele Sj. Hodnota toku na ostatních hranách určuje využití propustnosti konkrétních úseků sítě mezi dodavateli a spotřebiteli. 27) Lokační úlohy, Spojitá a diskrétní lokace, Lokace na dopravních sítích V praxi se jedná o rozmístění např.: max stanovišť vozidel hasičské ochrany, záchranné služby, pekáren, skladů, poštovních úřadů,… z
yh y
hYz
4
Společným problémem je potřeba výběru místa z kterého budeme obsluhovat vrcholy a úseky sítě. Odlišné pro úlohy je: počet rozmísťovaných středisek, jde-li o obsluhu vrcholů, úseků nebo hran sítě, kritérium kvality řešení, způsob obsluhy úseků. Sítí rozumíme souvislý, vrcholově a hranově ohodnocený graf bez smyček. Síť vyjadřuje běžnou komunikační síť. w(v)- váha vrcholu (požadavek uzlu na obsluhu) o(h)- ohodnocení hrany (délka úseku) w(h)- váha hrany (např. důležitost komunikace) Depem rozumíme místo na síti kde je umístěno středisko obsluhy 28) Atrakční obvody- definice, vlastnosti Atrakční obvod A(v)- je množina vrcholů a hran sítě pro kterou platí: u € A(v), pokud neexistuje žádné další depo pro které platí w € Dk, tak že vzdálenost d (w,u) < d (v,u) Prvotní atrakční obvod A’(v)- je množina vrcholů a hran pro které platí: u € A’(v) pokud neexistuje žádné depo w € Dk, d (w,u) ≤ d (v,u) Přidělený atrakční obvod A*(v) 29) Vážená excentricita vrcholu/bodu, Vzdálenostně optimální depo, Absolutní depo Vážená excentricita vrcholu v: ec(v) = max {d(u,v) x w(u)} Vzdálenostně optimální umístění depa je vrchol v*: ec(v*) = min {ec(v)} Absolutní depo je bod y* pro který platí: ec(y*) = min {ec(y)} 30) Hakimiho věta, Hakimiho algoritmus Pro všechny hrany hk X určíme bod (body) yk hk s minimální váženou excentricitou. Na hraně (hranách) může existovat více bodů s touže minimální váženou excentricitou. Ze všech yk (k = 1, ..., m); m q, q = X určíme bod yk* G, který má minimální váženou excentricitu.
Bod
y k*
je absolutním depem.
Praktický postup: 1. krok:V závislosti na e sestrojíme pro každou hranu sítě diagram hodnot:
Ti w(vi ) (e d (vb , vi ))
,
Ti w(vi ) (d (va , vi ) cab e) , /
kde cab je délka hrany (va, vb). 2. krok: Určíme lomenou čáru určující dolní ohraničení Ti a
Ti /
pro všechny vrcholy vi V. 3. krok: Určíme nejmenší horní ohraničení všech předchozích dolních ohraničení. 4. krok: Minimum z tohoto ohraničení je ec(yk), příslušnou polohu yk určuje e. Uvedený postup je značně pracný , protože je potřebné vytvořit diagramy pro všechny hrany sítě. Počet diagramů můžeme omezit na základě následujících úvah: Každé absolutní depo na hraně (vi, vj) je spojeno s hodnotou:
pij max w(vt ) min d (vi , vt ), d (v j , vt ) vt V
, tato hodnota je dolní ohraničení vážené excentricity absolutního depa ležícího na hraně (vi, vj). Dolní ohraničení absolutního depa v síti G = (V, X) je dáno:
p min
( vi , v j ) X
p ij
Uvažujeme-li, že absolutní depo je na hraně (vi, vj), potom hodnota:
hij pij 1 / 2 cij w(vr )
, kde w(vr) je váha vrcholu pro který je pij maximální, je horním ohraničením vážené excentricity absolutního depa ležícího na hraně (vi, vj) Horní ohraničení absolutního depa v síti G = (V, X) je dáno:
H min
( vi ,v j ) X
p
ij
1 / 2 cij w(v r )
Každá hrana (vi, vj) X, pro kterou platí pij H může být vyloučená z množiny hran, pro které se sestrojují diagramy. 31) Kritéria pro řešení lokačních úloh Obsluha vrcholů sítě –množinu dep nazveme vrcholově optimálním umístěním k dep na síti Obsluha hran sítě - množinu dep nazveme hranově optimálním umístěním k dep na síti , depa musí být obecně umístěna pouze ve vrcholech sítě, ale mohou být umístěna i na hranách sítě 32) Iterativní algoritmus 1.krok: Zvolíme množinu výchozích dep ->určíme množinu neprozkoumaných vrcholů ->položíme z=0 -> 2.krok: zjistíme zda je množina neprozkoumaných vrcholů prázdná->je-li N=0 pokračujeme krokem 4 nebo je-li N ≠0 vybereme libovolný vrchol a vytvoříme množiny 3.krok: porovnáváme hodnoty kritéria 4.krok: je-li z=0 pokračujeme krokem 5 nebo je-li z>0 položíme znovu z=0 určíme novou množinu N=V/Dk a pokračujeme krokem 2 33) Stromy, vlastnosti, typy, Základní pojmy Strom – T – je souvislý graf, který neobsahuje jako podgraf kružnici. Strom dále budeme značit T = (V, X). Pro graf, který je stromem platí q = n - 1, kde q = ⎪X⎥ a n = ⎪V⎥ . Pro T mezi každou dvojicí vrcholů u, v ∈ V, u ≠ v existuje právě jedna cesta, každá hrana stromu je mostem a každý vrchol stromu mající st(v) ≥ 2 je artikulací. Les – je nesouvislý graf, jehož komponentami jsou stromy (popř. triviální grafy). Hvězda – speciální případ stromu, ve kterém jeden vrchol má st(v) = n – 1 a n – 1 vrcholů má stupeň st(v) = 1. Excentricita (výstřednost) vrcholu v – e(v) – je číslo, které udává { }) , ( max ) ( v u d v eV u∈ = Vážená excentricita vrcholu v – ec(v) – je číslo, které udává { }) ( ) , ( max ) ( u w v u d v ecV u× =∈ , kde w(u) je váha vrcholu u ∈ V Rádius (poloměr) grafu T = (V, X) – r(T) – je číslo, které udává { } ) ( min ) ( v e T rV v∈ = Diametr (průměr) grafu T = (V, X) – d(T) – je číslo, které udává { } ) ( max ) ( v e T dV v∈ = Centrální vrchol – je vrchol v ∈ V pro který platí e(v) = r(T). Centrum grafu – množina všech centrálních vrcholů. Větev vrcholu – pro v ∈ V nazýváme podgraf, který je stromem, obsahuje vrchol v a maximální počet vrcholů a platí v něm st(v) = 1. Síla vrcholu – s(v) – udává počet vrcholů větve, která obsahuje maximální počet vrcholů. Centroidní vrchol – vrchol s minimální silou. Centroid – množina všech centroidních vrcholů. 34) Konstrukční úlohy na grafech, Kostra grafu Kostra grafu G = (V, X) je graf T = (W, Y) | W = V, Y množinou X, který je stromem(Protože množina vrcholů kostry grafu je shodná s množinou vrcholů původního grafu, je kostra faktorovým podgrafem) Minimální kostra souvislého hranově ohodnoceného grafu je taková kostra, pro kterou je součet ohodnocení hran minimální. Maximální kostra souvislého hranově ohodnoceného grafu je taková kostra, pro kterou je součet ohodnocení hran maximami. Sestrojení kostry grafu Sestroj.minimální(maximální)kostry gr.postupným výběrem hran 1. krok: Položíme Y= {0} 2. krok: Vybereme hranu h* € X s minimálním (maximálním) ohodnocením: o(h*)=minh€X {o(h)} a zařadíme ji do kostry grafu (h* => Y). 3. krok: Z dosud nevybraných hran vybereme další hranu s minimálním (maximáhiím) ohodnocením. Do kostry ji zařadíme v případě, že jejím zařazením nevznikne kružnice. V opačném případě vybereme další hranu. 4. krok: Podle 3. kroku postupujeme do té doby, dokud je možné vybrat alespoň jednu hranu, jejíž zařazení nezpůsobí vznik kružnice, jinak přejdeme na krok 5. 5. krok:Sečteme ohodnocení vybraných hran,hodn.součtu je hodnotou min.(max.)kostry grafu 35) Eulerovský graf, Eulerovský tah Neorientovaný graf, jehož každý vrchol má sudý stupeň, nazýváme eulerovským grafem
5
(E-grafem). Graf G = (V, X, p) je E-grafem právě tehdy, lze-li jej vyjádřit jako sjednocení soustavy vzájemně hranově disjunktních kružnic: Eulerovský tah (E-tah) může. ale nemusí začínat a končit v témže vrcholu. Podle toho hovoříme o otevřeném, nebo uzavřeném E-tahu. Nutnou a postačující podmínkou k tomu, abychom konečný souvislý G=(V, X, p) mohli sestrojit 1uzavřeným E-tah.je,aby byl E-grafem Nutnou a postačující podmínkou k tomu, abychom konečný souvislý graf G = (V, X, p) mohli sestrojit jedním otevřeným E-tahem je,aby graf obsahoval právě dva vrcholy lichého stupně; eulerovský tah v jednom z nich začíná a ve druhém končí. V konečném, souvislém grafu, který má 2t uzlů lichého stupně t ≥ l, se každé minimální pokrytí grafu(o hraně grafu hovoříme, že je pokryta E-tahem, pokud jev E-tahu obsažena) skládá z t otevřených E-tahů, z nichž každý spojuje dvojici uzlů lichého stupně. Na sestrojení uzavřeného E-tahu v E-grafu a grafu se dvěma vrcholy lichého stupně použijeme Fleuryho alg.. V grafech s počtem vrcholů lichého stupně větším než dva použijeme Edmondsův alg. 36) Hamiltonovský graf, Hamiltonovská kružnice, podmínky existence Hamiltonovská kružnice je podgraf grafu, který je kružnicí a obsahuje všechny vrcholy grafu. Hamiltonovskou kružnici můžeme rovněž definovat jako souvislý pravidelný graf druhého stupně, který obsahuje všechny vrcholy grafu. Nutnou podmínkou pro existenci hamiltonovské kružnice je, že nesmí obsahovat most, artikulaci a vrcholy stupně 1. Splnění nutné podmínky není postačující k existenci hamiltonovské kružnice. Jsou známy postačující podmínky existence hamiltonovské kružnice, které naopak nejsou nutnými podmínkami, co znamená, že z jejich neplatnosti nevyplývá pro existenci hamiltonovské kružnice žádné tvrzení. Uvedeme dvě známé postačující podmínky, které jsou důsledkem Posovy věty: a) uvažujme graf G = (V, X), kde |V| = p ≥ 3, pro jehož dva různé nepřilehlé vrcholy u, v € V platí vztah: st(u)+st(v) ≥ p, potom graf G=(V,X)obsahuje hamilton.kružnici(je hamiltonovský) b) nechť v obyčejném grafu G = (V, X) s p ≥ 3 pro každý vrchol v € V platí: st(v) ≥ p/2, potom graf G = (V, X) obsahuje hamiltonovskou kružnici (je hamiltonovský). Pro řešení praktických úloh je potřebné vyhledávat minimální (maximální) hamiltonov¬ské kružnice v hranově ohodnocených grafech (o(h) > 0). Minimální (maximami) hamilto-novská kružnice je taková hamiltonovská kružnice, jejíž součet ohodnocení hran je minimál(maximál) 37) Fleuryho algoritmus, Edmondův algoritmus Fleuryho algoritmus 1. krok: Konstrukci E-tahu začneme v libovolném vrcholu grafu. Vybereme libovolnou hranu incidující s tímto vrcholem a projdeme jí. Prošlou hranu označíme. 2. krok: Při příchodu do vrcholu vi € V grafu nikdy nepoužijeme hranu, která je v dané situaci mostem, jehož odstraněním by se graf složený z dosud neoznačených hran rozpadl na: a) netriviální komponenty; b) netriviální komponentu a vrchol, ve kterém tah začíná. Pokud použijeme algoritmus správně, skončíme ve vrcholu, ve kterém Etah začíná. Fleuryho algoritmus použijeme i v případě, že graf obsahuje dva vrcholy lichého stupně. Tyto dva vrcholy spojíme násobnou hranou (vznikne multigraf), kterou projdeme jako první. Po dokončení uzavřeného E-tahu hranu opět vypustíme; tím vznikne otevřený E-tah.. V hranově ohodnocených grafech s počtem vrcholů lichého stupně větším než dva definujeme uzavřený E-tah minimální délky.E-tah minimální délky je tah,jehož součet ohodnocení hran je minimální Edmondsův algoritmus 1. krok:V gr G=(V,X)urči vrcholy lichého stupně v počtu 2t, t ≥ 1(t =počet dvojic lichého st.) 2. krok: Sestrojíme kompletní graf K2t (jeho vrcholy jsou vrcholy lichého stupně grafu G). 3. krok: Hrany kompletního grafu ohodnotíme vzdáleností příslušných vrcholů v grafu G. 4. krok: Určíme párování minimální délky. 5. krok: Hrany minimálního párování přidáme do původního grafu mezi příslušné vrcholy, vznikne graf (případně multigraf), který je E-grafem. 6. krok: V grafu (multigrafu) z 5. kroku sestrojíme uzavřený E-tah Fleuryho algoritmem. Tento tah je E-tahem minimální délky. 7. krok: V E-tahu nahradíme každou hranu párování odpovídající cestou minimální délky. Dostaneme sled, který je uzavřeným E-sledem pokrývajícím hrany grafu minimální délky.
38) Heuristický algoritmus vyhledávání HK v kompletním grafu Heuristický algoritmus určení hamiltonovské kružnice v kompletním grafu 1. krok: Uvažujme graf Kn = (V,X). Určíme minimální hamiltonovskou kružnici H=(W,Y). Kce. hamiltonovské kružnice začneme v libovolném vrcholu vp € V, (vp je počáteční vrchol): a) položíme W = 0, Y = 0 b) počáteční vrchol zařadíme do W (vp => W), položíme vs = vp, c) určíme Ґ (vp) -je to množina přilehlých vrcholů vrcholu vp, d) polož Ґ(s čarou)(vp)=v(vp)/W 2. krok:Vyber hranu h* € X | p(h*) = (vp, vi), vi € Ґ(s čarou)(v) s minimálním ohodnocením o(h*) = minvi€ Ґ(s čarou)(vp) {o(vp, vi)} a zařadíme ji do hamiltonovské kružnice h => Y 3. krok: Položíme vp = vi, a určíme Ґ(s čarou)= Ґ (vp)\W : a) je-li Ґ (s čarou)(vp) = {0}; zařadíme poslední hranu uzavírající hamiltonovskou kružnici (vp, vs) => Y a pokračujeme 4. krokem, b) je-li Ґ(s čarou)(vp) ≠ {0}; pokračujeme 2. krokem. 4. krok: Sečteme ohodnocení hran zařazených do hamiltonovské kružnice. Součet je hodnotou minimální hamiltonovské kružnice. 39) Metoda Branch and Bound, Littlův algoritmus, Formulace úlohy obchodního cestujícího Princip metody Branch & Bound (větve a hranice) Nechť E={S1, S2,..., Sn} je množina řešení některé úlohy diskrétní optimalizace a f je funkce definovaná na této množině. Je potřeba nalézt podmnožinu Em množinou E, na které funkce f dosahuje minima (jestliže existuje). Metody větve a hranice lze použít i pro vyhledávání podmnožiny Em množinou E maximálních řešení. Uvažujme, že s pomocí vlastnosti PA je možné rozdělit E na 2podmnož.A, A(s čarou),přičemž: A A(s čarou)={0},A A(s čarou)=E Předpokládej, že dokážeme nalézt spodní hranici b0 hodnot funkce f na E. Dále předpokládejme, že dokážeme stanovit i spodní hranice b1 ≥ b0, b1´ ≥ b0, funkce f na A, resp. A(s čarou). Vlastnosti PB, PC, a další, rovněž dovolují rozložit E na dvě části. Potom vlastnostem PB PA, PB(s čarou) PA, PA(s čarou) PB, PA(s čarou) PB(s čarou) odpovídají podmnožiny B A, B(s čarou) A, A(s čarou) B, A(s čarou) B(s čarou). Každou podmnožinu považujeme za vrchol grafu. Tímto způsobem je možné vytvořit graf. Postup vytváření prastromu je následovný: • předpokládejme, že jsme sestavili část prastromu využitím k - vlastností P1, P2, ..., Pk a našli spodní hranici funkce/této části • vezmeme visící vrchol prastromu, který má nejnižší hranici, • s pomocí k vlastností, nebo možná k + l vlastností obdržíme další dva nové vrcholy, pro které určíme spodní hranici b. Pro vrcholy prastromu reprezentující podmnožiny množiny řešení E platí: sjednocením všech vrcholů (visících), v každé fázi dostaneme původní množinu řešení E. E = A(s čarou) (A B) (A B(s čarou) C(s čarou)) (A B(s čarou) C) Je-li výsledkem daného procesu visící vrchol, který představuje jednoprvkovou množinu, potom funkce f nabývá na této množině min.hodnotu.Nazýváme metodou optim. pomocí síta Algoritmus pro nalezení minimální hamiltonovské kružnice grafu s n vrcholy(Litlův alg) •uvažujme symetrický(neorientovaný),nebo nesymetrický(orientovaný)hranově ohodnoc.graf •každá hrana grafu má ohodnocení vij ≥ 0. nebo vij = ∞, •hodnoty vij; i = l, 2,..., n; j =1,2,...,n tvoří matici sazeb – V=(vij)nij=1, •symbol ∞ vyjadřuje skut.,že mezi vrcholy vi a vj neexistuje hrana nebo je zakázáno ji použít 1. krok: V každém řádku matice V odečteme od všech prvků minimální prvek řádku. Dostaneme matici V´, kde: vij´ = vij - minj {vij}, pro i = 1, 2,..., n. 2. krok: V každém sloupci matice V´, odečteme od všech prvků minimální prvek sloupce. Dostaneme matici F , kde: vij´´= vij´minj{vij´} pro j = l, 2,..., n. Poznámka: Výsledkem l. a 2. kroku je minimálně jedna nula v každém řádku a sloupci. 3. krok: Krok 3a) se provede pouze při 1.průchodu algoritmem, jinak provedeme krok 3b). 3a) Vytvoříme kořen prastromu řešení úlohy E a přiřadíme mu hodnotu b0 rovnající se součtu odečítaných minimálních hodnot v l. a 2. kroku: a přejdeme na 4. krok algoritmu
6
3b) Sečteme řádková a sloupcová minima odečítaná v 1. a 2. kroku za účelem vytvoření nul v redukované matici a přejdeme na 9. krok. Poznámka: Hodnota b0 vyjadřuje skutečnost, že žádná hamiltonovská kružnice grafu nebudemít menší hodnotu než bo. 4. krok: Ohodnotíme všechny nuly v matici V´´ číslem γij tak, ze sečteme minimální prvek v příslušném i-tem řádku j-tém sloupci (právě ohodnocovanou nulu nebereme na zřetel): 5.krok: Vybereme pole (vk, vl), které obsahuje nulu s max.ohodnocením γkl=maxi,j {γij} toto pole určuje vlastnost Pkl (Pkl (s čarou)); Pkl znamená,že hamilton.kružnice bude obsahovat hranu(vk,v/);vlastnost Pkl(s čarou)znamená,že hamilton.kružnice hranu(vk,vl)obsahovat nebude 6.krok: Rozvineme prastrom o vrchol s vlastností Pkl(s čarou); vrchol ohodnotíme tak, že k ohodnocení předchůdce přičteme γ kl 7. krok: Rozvineme prastrom o vrchol odpovídající vlastnosti Pkl, vyloučíme z matice k-tý řádek a l-ty sloupec, čímž dojde k redukci matice sazeb o 1řádek a sloupec. Ty prvky redukované matice,kt.by umožnily vznik hamiltonovské kružnice menší délky než n polož=∞ 8. krok: S maticí, která je výsledkem 7. kroku provedeme l. a 2. krok algoritmu. 9. krok: S maticí, která je výsledkem 8. kroku provedeme 3b) krok; hodnotu součtu přičteme k ohodnocení předchůdce a tímto součtem ohodnotíme vrchol s vlastností Pkl. 10. krok: Jestliže výsledkem 7. krokuje matice rozměru l x l, je proces ukončený, v opačném případě pokračujeme 11. krokem. 11. krok: Z visících vrcholů vybereme vrchol s nejmenším ohodnocením (je-li jich více, vybereme libovolný z nich). 12. krok: Jestliže vybraný vrchol odpovídá posledně uvažované vlastnosti Pkl, přejdeme na 4. krok, jinak přejdeme na 13. krok. 13. krok: Mohou nastat dvě možnosti: 13a) Visící vrchol vybraný vil. kroku odpovídá vlastnosti Pij(s čarou),potom v matici odpovídající této vlastnosti změníme hodnotu vij´´= ∞, v i-tém řádku resp. j-tém sloupci určíme minimální prvek a tento odečteme od všech hodnot řádku resp. sloupce; následuje přechod na 4. krok 13b) Visící vrchol vybraný vil. kroku odpovídá vlastnosti Pij, pokračujeme 4. krokem s maticí odpovídající vlastnosti Pij.
libovolné vrcholy jsou přilehlé (vi, vj) € X jestliže stát prezentovaný vrcholem vi sousedí se státem vj Graf G = (V, X) nazveme n – zabavitelným, když n různými barvami můžeme zabarvit jeho vrcholy tak, aby žádné dva přilehlé vrcholy neměly stejnou barvu. Chromatickým číslem grafu - b(G) - nazveme to číslo n, které udává minimální počet barev potřebných na to, aby graf G = (V, X) byl n zabarvitelný. Odhad chromatického čísla- b (G) ≤ 1+ delta G delta G- maximální stupeň vrcholu grafu 44) Heuristický algoritmus barvení grafu, Hypotéza 5/4 barev Heuristický algoritmus barvení grafu 1. krok: Vrcholy grafu G = (V, X) seřadíme do posloupnosti P = { vk1, vk2,..., vkp } tak, aby platilo: st(vk1) ≥ st(vk2) ≥...≥ st( vkp). 2. krok: Položíme j = l (první barva). 3. krok: 3a) vybereme z P dosud nezabarveny vrchol, který není přilehlý k vrcholům již zabarveným barvou/ a zabarvíme jej. 3b)postup podle a) opakujeme, dokud lze v P vybrat další vrchol, jinak přejdeme na 4. krok. 4. krok: Pokud při barvení vrcholů grafu barvou j nezabarvíme všechny vrcholy z P, položíme j = j + l a pokračujeme 3. krokem, v opačném případě pokračujeme 5. krokem. 5. krok: Poslední hodnoty udává odhad chromatického čísla grafu. 45) Aplikace rovinných grafů Aplikace rovinných grafů: elektronika; existuje n dvojic bodů, které je nutné elektricky spojit. Problém spočívá v tom, že se vyžaduje aby maximální počet spojení mohl být "natištěn" na nevodivou desku a pouze objektivně nutný (minimální) počet spojů se realizoval klasickou technologií, tzn. přemostěním a pájko váním vodičů,(telekomunikace; určování minimálního počtu vysílacích pásem pro vysílače televizního vysílání; geografie; barvení politické mapy)
Cílem úlohy obchodního cestujícího je navštívit všechny místa (vrcholy grafu), každé pouze jednou a vrátit se do místa odkud vyšel s tím, že vzdálenost kterou ujde musí být minimální. 40) Aplikace úlohy obchodního cestujícího, Přiřazovací problém viz. otázky 39 a 26 41) Rovinné grafy, Kuratowského věta Graf nazveme rovinným grafem, když je možné tento graf rovinně zakreslit. O grafu hovoříme, že je rovinně zakreslený, když je zakreslen tak, že se žádné z jeho hran neprotínají jinde než ve vrcholech. Rovinně zakreslený graf můžeme také definovat následovně: • je to graf, ve kterém žádné dvě hrany nemají společný vnitřní bod hrany, • je to graf, ve kterém dvě hrany mohou mít společný pouze jeden a to koncový bod hrany, který představuje krajní (incidující) vrchol hrany. Kuratowského věta: Graf je rovinný právě tehdy, když neobsahuje podgraf, který je homeomorfní s grafem K5, nebo s grafem K 3,3 42) Petersonův graf, Homeomorfismus HomeomorfismusUvažujme dva rovinné grafy G1 a G2. Graf G1 je homeomorfnís grafem G2, když: a) je s grafem G2 izomorfní (G1 =(s vlnovkou)G2) b)je možné konečným půlením hran5) (nebo vypouštěním vrcholů) grafu G1; dosáhnout toho, že vzniklé grafy jsou izomorfní. Petersonův graf- není rovinný, protože obsahuje podgraf, který je homeomorfní s grafem 43) Barvení grafů, Chromatické číslo grafu, Odhady chromatického čísla Barvení grafů Problém určení minimálního počtu barev potřebných k zabarvení politické mapy. Při barvení politické mapy se požaduje, aby státy, které mají společnou hranici nenulové délky, byly zabarveny různou barvou. Požadavek minimálního počtu barev souvisí s problémy tisku. Grafickým modelem pol.mapy je rovinný graf,v němž vrcholy představují státy. 2
7
