16. 9. 2014
Diskrétní matematika
V podzimním semestru roku 2014 zapsala a obrázky opatřila Bc. Veronika Kosíková.
Vyučující: Mgr. Helena Durnová, Ph. D.
Ukončení: test – přibližně 10 příkladů, 6 musí být správně
seminární práce: formou přípravy na hodinu pro žáky základní školy, vybrat si jedno
z přednášených témat; v práci musí být uvedeno, pro kterou třídu je příprava určena; může
být psaná rukou, doplnit obrázky; odevzdat týden před udělením zápočtu
Skripta z diskrétní matematiky: Eduard Fuchs, Diskrétní matematiky pro učitele, Brno 2001 nebo 2011.
[Teorie grafů kolem nás]
Jde nakreslit tento graf jedním tahem?
Kolik existuje cest z bodu A do bodu B? A
B
Příklad:
Máme skleničky s obsahem 5, 3 a 2 dl. Na začátku jsou v první skleničce 4 dl, další dvě jsou prázdné
(4,0,0). Chceme, aby na konci byl počet dl ve sklenicích následující 2, 1, 1.
4, 0, 0
1, 3, 0 2, 0, 2
0, 3, 1 1, 1, 2 2, 2, 0 0, 2, 2
Teorie grafů: popisuje vlastnosti struktur složených z uzlů (vrcholů) a hran
graf musí mít aspoň jeden uzel, jinak nemáme o čem mluvit
v obyčejném grafu spojuje hrana dva (různé) uzly (vrcholy),
hrany: - orientované (se šipkami)
- neorientované
Patří sem také problematika pravidelných mnohostěnů
- aby byly pravidelné, musíme je skládat pouze z , a
mnohoúhelník
(polygon)
počet hran ve
vrcholu
„pohled shora“
čtyřstěn 3
šestistěn (krychle) 3
osmistěn 4
dvanáctistěn 3
dvacetistěn 5
Tímto zrušíme délku stran.
[Poznámky na okraj – k topologii:]
Pokud zrušíme i úhly, lze překreslit: , , a tak dále. Překreslený obrazec musí mít pořád
minimálně 3 vrcholy.
Z kuličky plastelíny lze udělat cokoli, co nemá díru.
Definice:
Nechť U je neprázdná množina, H je podmnožina množiny dvojic prvků U. Pak G(U,H) nazýváme graf.
H….. uspořádané dvojice uzlů ……… orientovaný graf
H …. neuspořádané dvojice uzlů ……. neorientovaný graf
Neřekneme-li jinak, tak se budeme zabývat KONEČNÝMI neorientovanými grafy.
Stupeň uzlu – počet hran vycházejících z daného uzlu 2 3
Např. v grafu na obr. je:
počet vrcholů: 4
počet hran: 5 3 2
součet stupňů uzlu: 10
Příklad:
Nakreslete 3 grafy a napište počet vrcholů, hran, součet stupňů uzlů.
počet vrcholů 6 5 7
počet hran 7 7 8
součet stupňů uzlů 14 14 16
Věta:
Součet stupňů uzlů je roven dvojnásobku počtu hran.
Příklad:
7 kamarádů se před prázdninami dohodlo, že každý pošle pohled 3 kamarádům tak, aby ten komu posílám
já, poslal pohled i mě.
Řešení: zkoušeli jsme to kreslit, nejde to, součet stupňů uzlů by musel být 21; neboli „nejde mít 10,5 hrany“.
IZOMORFISMUS
Je mi jedno jak velké to nakreslím a jak to otočím, záleží jen na tom, co je s čím spojeno – zda existuje mezi
danými dvěma grafy bijekce mezi uzly, z níž vyplývá i bijekce mezi hranami.
Grafy na 1 uzlu:
Grafy na 2 uzlech:
Grafy na 3 uzlech:
Grafy na 4 uzlech:
Definice: Pokud je v grafu každý uzel propojen s každým, nazýváme jej úplný graf.
Izolovaný uzel – stupeň uzlu je roven 0.
Příklad:
Nakreslete graf o 5-ti uzlech tak, aby se hrany nekřížili:
Opět nelze nakreslit (úloha o třech domech a 3 studnách)
23. 9. 2014
Příklad:
Na jedné straně je vlk koza a zelí a my je musíme převézt na druhou stranu tak, aby nedošlo k úhoně.
- do loďky: P+V nebo P+K nebo P+Z.
Příklad:
V klubu hádankářů mají deset pater. Ve výtahu mají tlačítka +3, -4, :2.
a) Lze se z libovolného patra dostat do jiného libovolného patra?
ano, lze se dostat do libovolného patra – Silně souvislý graf
b) Kolikrát zmáčkneme knoflík pro cestu z 5 do 9 patra?
Knoflík zmáčneme šestkrát.
Příklad:
Manželé Adamcovi byli na večerníku s dalšími třemi manželskými páry. Zdravili se podáváním ruky. Nikdo
nepodal ruku sám sobě, svému partnerovi ani téže osobě. Když to skončilo, tak se pan Adamec zeptal,
kolikrát kdo podal ruku. Od každého dostal jinou odpověď. Kolika lidem podala ruku paní Adamcová?
Součet v uzlu musí být šest (každý manželský pár podá ruku šesti lidem)
Podání ruky každý s každým (kromě párů)
Příklad:
Jak udělat, abych prošla celé bludiště?
Na křižovatce:
- První volba: kterou jsme nešli
- Druhá volba: zpět
- Třetí volba: chodba, kterou jsme prošli jednou
Tato metoda se nazývá prohledávání grafu do hloubky.
Prohledávání grafu do hloubky:
 Zjišťujeme, jestli je graf souvislý
 Snažíme se dostat co nejhlouběji
 Výsledek není jednoznačný, každé hledání může dopadnout rozdílně
Další metoda – prohledávání do šířky:
DÚ:
1. Tři misionáři a tři lidožrouti se potřebují přepravit přes řeku na dvoumístné loďce. Je nežádoucí, aby
se na některém břehu ocitlo více lidožroutů než misionářů. Loďka sama nepopluje. Zorganizujte
přepravu.
2. Máme plnou 12l nádobu a dvě prázdné nádoby – 7l a 4l. Přeléváním rozdělte vodu tak, aby ve dvou
nádobách bylo 6l vody.
30. 9.
24 způsobů 6 možností od každé dívky 6*4=24
V jakém pořadí mohou chlapci navštívit dívky a zase se vrátit zpět?
a) matice sousednosti (samé 1) – píšeme 1, pokud dané dva uzly spolu sousedí
b) matice vzdálenosti (hrany jsou ohodnocené, nemusí být každé dva uzly spojené hranou stejně
blízko, jako tomu bylo u neohodnoceného grafu)
A J H K CH
A x 15 10 8 5
J 15 x 7 12 20
H 10 7 x 9 11
K 8 12 9 x 10
CH 5 20 11 10 X
c) matice incidence
A J H K CH
5 1 - - - 1
7 - 1 1 1 A
J H K CH
A x 1 1 1 1
J 1 x 1 1 1
H 1 1 x 1 1
K 1 1 1 x 1
CH 1 1 1 1 x
od Jitky
6 možností J A K H chlapci 20 + 15 + 8 + 9 + 11 = 63 2
J A H K 20 + 15 + 10 + 9 +10 = 64 1
J H A K 20 + 7 + 10 + 8 + 10 = 55 5
J H K A 20 + 7 + 9 + 8 + 5 = 49 nejkratší 6
J K A H 20 + 12 + 8 + 10 + 11= 61 3
J K H A 20 + 12 + 9 + 10 + 5 = 56 4
Problém obchodního cestujícího = NP úplný
[To, že je problém NP úplný znamená zhruba to, že ho pro větší rozměr grafu nedokážeme v reálném čase
vyřešit: doba potřebná k vyřešení roste exponenciálně v závislosti na velikosti grafu, tj. roste „moc rychle“.]
[Příklady problémů, pro něž existují
relativně rychhlé algoritmy, tzv.
polynomiální]
 hledání nejkratší cesty
 hledání minimální kostry
1) Najděte nejkratší cestu z V do K
- Jen kladné vzdálenosti
- cestu, která je delší než již zjištěná, neberu v úvahu
2) Najděte nejkratší faktor – strom
a. Kruskalův algoritmus – seřadím si hrany podle velikosti, přidávám od nejmenší nebo ubírám od
největší, dávám pozor, aby se to nerozpadlo
…. Nejdelší vzdálenosti, které lze odstranit
b. Borůvkův algoritmus – (1926) postupně přiřazujeme nejkratší vzdálenosti
- na počítači nejrychlejší
VAD – BC 4 (AB)
VAD – EFK 7 (AE nebo DE)
BC – EFK 5 (BF)
c. Jarníkův algoritmus – je nejrychlejší pro ruční řešení [– a také srozumitelný, nejsnáze
uchopitelný – což je možná do jisté míry i věc názoru]
 „nabalování“
 mám AD co je nejblíž B (4)
 mám ADB co je nejblíž C (2)
 mám ADBC co je nejblíž V nebo F
7. 10.
Pod pojmem graf si představujeme „puntíky spojené čarami“.
a) Graf neorientovaný - konečný graf bez smyček
- platí (Věta): ∑ 𝑠𝑡𝑈 = 2/𝑢 𝑈 H/
- součet počtu uzlů je roven dvojnásobku počtu hran
- důsledek (Lemma): počet uzlů lichého stupně je sudý.
- součet stupňů uzlu je liché číslo ∑ 𝑠𝑡𝑈 = 1 + 2(𝑛 − 1)𝑢 𝑈
b) Úplný graf - je takový, kde každý uzel je spojený s každým jiným uzlem
Př. Nakreslit K4 K5 K6 K7
K3
Které se dají nakreslit jedním tahem??
Jedním tahem lze nakreslit: K3, K5, K7
- jedním tahem lze nakreslit pouze úplný graf na lichém počtu uzlů (všechny jeho uzly jsou
pak sudého stupně)
Definice:
Sled je posloupnost uzlů a hran u1(u1u2)u2(u2u3)u3(u3u4)….
uzel*hrana*uzel*hrana*….
- uzly i hrany se mohou opakovat
 speciální typy sledů:
o cesta – sled, v němž se neopakují uzly
o tah – sled, ve kterém se neopakují hrany
Souvislý graf je takový, v němž mezi každými dvěma uzly existuje sled.
Věta: Konečný souvislý graf, který má všechny uzly sudého stupně, lze nakreslit jedním tahem.
Poznámka: uzavřený graf začíná a končí ve stejném uzlu.
Hypotéza: Úplný graf na lichém počtu uzlů dokáži nakreslit jedním tahem.
- Důkaz například indukcí, když nakreslím ještě dva uzly, tak to musím umět doplnit
Při průchodu uzlem seberu grafu dvě hrany (když je stupně šest, tak uzlem projdu 3x). Do každého uzlu
musím vlézt a zase z něj vylézt.
Pokud je graf lichého stupně, tak se do jednoho uzlu musím jednou dostat a už z něj nevylezu. Vždy to jde
zařídit tak, že se tam dostanu. Cestu, kterou jsme našli, dokážeme zvětšit.
Obrázek nakreslit jedním tahem:
- Všechny uzly jsou sudého stupně
- Předtím než se vrátím, tak musím „vlézt dovnitř“
Otázka: Kolika otevřenými tahy lze nakreslit souvislý graf se 2, 4, 6, atd. (2k) uzly lichého stupně??
Překreslení
K5 – jeden uzavřený tah K6 – tři otevřené tahy
V grafu K3 se nic nekříží
Překreslení K4, aby se nic nekřížilo
Překreslení K5, aby se nic nekřížilo
- nikdy se nám nepovede překreslit úplný graf na pěti uzlech, aniž by se něco křížilo.
Definice:
Planární graf je takový graf, který LZE nakreslit V ROVINĚ tak, aby se žádné dvě hrany nekřížily.
Tzn. když nakreslím tak pokud mám dokázat, že je graf planární, tak musím dokázat, že to nelze
nakreslit bez křížení. U toho grafu ale nakreslení v rovině známe, totiž Tento graf tedy lze
nakreslit v rovině tak, aby se hrany nekřížily, proto je planární.
Příklad:
„tři domy, tři studně“ – musíme se dostat z každého domu do každé studny tak, aby se cesty nekřížily
Věta: (Kuratowského věta – Kuratowského grafy)
Graf, který osahuje K5 nebo K3,3 jako podgraf není planární – nelze jej v rovině nakreslit tak, aby se hrany
nekřížily.
Příklad:
Uveďte příklad planárního grafu na 8 uzlech.
!není nikde psané, že graf má být úplný! Pokud by graf měl být úplný, tak by to nešlo, takhle to jde.
- Může to být osm libovolně
spojených uzlů např.
- nebo K6,2
14. 10. 2014
Př. Vybarvěte mapu USA co nejméně barvami.
Př. 4-stěn  4-stěn
krychle  8-stěn
8-stěn  krychle
12-stěn  20-stěn
20-stěn  12-stěn
krychle a osmistěn jsou navzájem duální
Kolika barvami obarvíme krychli?
- 3 barvy
Barvení grafu
Definice: Obarvení grafu je funkce, která každému uzlu přiřadí hodnotu (barvu) podle následujícího
pravidla: jsou-li dva uzly spojeny hranami, nesmí mít stejnou barvu f: U  B
20-stěn (výřez) mapa
- stačí 3 barvy - stačí 4 barvy (empirické řešení
- nevezmeme raději 5 barev?? ano, 5 barev rozhodně
stačí
- zakážeme „…. státy", zakážeme společnou hranici 4 a
více států a nebo řekneme, že státy, které se dotýkají
pouze v jediném bodě, mohou mít stejnou barvu (v mapě
USA státy UT, CO, AZ, NM)
Příklad: Máme osm (chemických) látek a každé dvě spolu reagují. Kolik musíme mít skříní, aby ve stejné
skříni byly jen látky, které spolu nereagují?
- 8 skříní / 8 barev
Algoritmus obarvení
 Vezmu 1 vrchol a obarvím barvou 1 (max n barev)
 Další uzel – podívám se na jeho sousedy a obarvím nejnižší barvou, která se nevyskytuje
 Lze snížit počet barev?
o Zkusím snížit barvu u uzlů, kde jsou teď označeny nejvyšší barvou
o (Přesně jsme si algoritmus neformulovali, lze nalézt např. v knize Demel, Grafy a jejich
aplikace, Praha: Academia, 2002)
Definice: Uzlové chromatické číslo je nejmenší počet barev potřebných k obarvení uzlů daného grafu tak,
aby žádné dva uzly spojené hranou neměly stejnou barvu..
Uzlové chromatické číslo 2 - dvě strany; (kružnice sudé délky)
3 - kružnice liché délky
11. 11. 2014
Definice:
Podraf – část grafu, která je sama grafem.
Faktor – je podgraf, který obsahuje všechny uzly.
Příklad:
První pokus
Máme čtyři kostky, které jsou různobarevné.
Žluté stěny: 4
Červené stěny: 6
Modré stěny: 8
Zelené stěny: 6
Každá kostka má jednu stěnu žlutou.
Graf (barvy protějších stran kostek)
graf má 12 hran
Najdu podgraf (faktor), který mi splňuje zadání:
- faktor má stupeň 2
- nemusí být vše propojené
- musí obsahovat čtyři hrany
s různými čísly – podle kostek, na nichž jsou stěny příslušných barev proti sobě.
Skládám kostky podle faktoru:
Na první kostce dám proti sobě dvě modré, na druhé kostce naproti sobě zelenou a červenou, na třetí kostce
zelenou a žlutou, na čtvrté kostce červenou a zelenou.
Mám naskládánu přední a zadní stranu, teď řeším jen spodek a vršek, ale pozor, točíme jen dokola, přední a
zadní strana zůstává na místě.
Nakreslíme si to znova a zrušíme hrany, které jsme už použili.
graf má 8 hran
Teď potřebujeme dostat ještě jeden podgraf (faktor).
Z našeho zjištění je zřejmé, že tyto kostky nejde naskládat dle zadání.
Každá hrana musí mít jiné číslo a každý uzel musí být stupeň 2.
Možné kombinace:
Závěr: Jednu kostku musíme přeskládat
Druhý pokus po přeskládání
Faktor – přední/zadní strana: Zbyde:
Faktor – horní/dolní strana: Zbyde:
další podgraf už nenajdu
Pokud si kostky chceme seskládat sami, tak aby vznikl hlavolam, tak si vezmeme čtyři uzly a nakreslíme si
dva grafy a ten třetí uděláme tak, aby to nešlo, bylo by to moc jednoduché.
Tenhle hlavolam se jmenuje instantní šílenství.
Příklad: Je možné, aby v konečném souvislém grafu bez násobných hran a smyček existovaly dvě kostry,
které nemají žádnou společnou hranu?
Graf o 4 uzlech, hledáme 2 stromy.
Máme dáno n přirozených čísel, n≥2.
Nutná a postačující podmínka pro to, aby existoval strom, kde s1, …, sn jsou stupně uzlů, je:
∑ s𝑖 = 2𝑛 − 2
𝑛
𝑖=1
2, 2, 2 ∑ 6 
Existuje, ale není strom
2, 1, 0 ∑ 3 
není přirozené číslo  BLBOST 
ale ani kdybychom dovolili i nulu, nešlo by to: izolovaný uzel
má stupeň 0, ale nejde mít dva uzly, kde jeden má stupeň 1 a
druhý stupeň dva, ani kdybychom povolili smyčky
1, 1, 1 ∑ 3  lichý počet uzlů →
1
2
ℎ𝑟𝑎𝑛𝑦 NEJDE
2, 1, 1 ∑ 4 = 2 ∗ 3 − 2 dokážeme nakreslit strom (ale není to
důkaz!)
(nutná a postačující podmínka)
implikace
ekvivalence
1. "" Existuje strom se stupni s1, …, sn
 ∑ s𝑖 = 2𝑛 − 2 == 2(𝑛 − 1) = 2|H|𝑛
𝑖=1
dvojnásobek počtu hran
ukrajuju
strom: (n=1 hran)
2. "" ∑ s𝑖 = 2𝑛 − 1𝑛
𝑖=1  existuje strom
Kostra je taky faktor, který je stromem.
Kostrou grafu budeme rozumět libovolný podgraf, který hranami spojuje všechny vrcholy původního
grafu a zároveň sám neobsahuje žádnou kružnici (→ jde o strom).
Příklad:
(2, 2, 2, 0)
 nemůže být, strom musí
obsahovat alespoň jednu jedničku
(3, 2, 2, 1, 1, 1)
 2 * 6 – 2 = 10
(kdy m…… 2, 2, 2, 2, 1, 1)
není kostra
strom
18. 11. 2014
[Na zpestření – aneb jak zabít představivost]
Prasátko:
Předělejte dvě zápalky tak, aby se prasátko dívalo na druhou stranu.
Přesuňte smítko na lopatku:
IZOMORFISMY
Izomorfní – mají stejnou strukturu
Izomorfní grafy mají stejný počet uzlů a hran
Definice:
Izomorfismus grafů
Zobrazení G1(U1, H1) na G2(U2, H2), které je bijekcí: f1: U1U2
f2: H1H2
Dva grafy jsou izomorfní, pokud existují současně f1 a f2 – bijekce mezi množinami uzlů a hran.
Bijekce je mezi množinami uzlů taková, že bude bijekce i mezi množinami hran.
Aby byly dva grafy izomorfní, tak:
a) musí mít stejný počet uzlů
b) musí mít stejný počet hran
c) musí být stejné stupně uzlů
Které následující grafy jsou izomorfní??
a) Pokud chceme zjistit, jestli je tento graf izomorfní s nějakým jiným, tak hledáme příslušné hrany
c) Tento graf je jiný, obsahuje most (pokud jej odstraním, tak se graf rozpadne); jiné grafy jej neobsahují
Kružnice v grafech:
délky 3 4 5 6 7 8 9 10
a) 4
ACB, ABD,
GJK, HJK
2
ACBD,
GJHK
4
ACEFD, ACEFD,
EGJHF, EGKHF
4
ABCEFEC,
EFJKHF,
EFHJKC,
BCEFDA
- 2 4 1
b) 2 2 4
d) 4 2 4 4 - 2
Definice:
Hrana se nazývá mostem, pokud jejím odstraněním vznikne ze souvislého grafu graf nesouvislý.
Most – hrana, která nelež na žádné kružnici
Kružnice – souvislý podgraf, který má všechny uzly stupně 2
Grafy a a d jsou izomorfní:
Homeomorfní graf:
3 domy, 3 studny – nic si nezjednoduším, když tam
přidám uzel
Definice:
Homeomorfní graf vznikne z jiného grafu půlením hrany.
Příklad:
Mějme graf, jehož hrany se při daném nakreslení nekříží
a) b)
10 7 u … počet uzlů
15 7 h … počet hran
1 2 k … počet komponent (souvislých částí)
7 3 s … počet oblastí
u + s = h + k + 1
7 + 3 = 7 + 2 + 1
7 + 3 = 8 + 1 + 1
7 + 4 = 9 + 1 + 1
Nechť v G platí:
u + s = h + k + 1
Ubereme hranu, pak:
a) sníží se počet částí
u + s – 1 = h – 1 + k + 1
b) nebo se zvýší počet komponent
u + s = h – 1 + k + 1 + 1
2 + 1 = 1 + 1 +1 4 + 1 = 3 + 1 + 1
3 + 1 = 2 + 1 + 1 4 + 2 = 4 + 1 + 1
Pro souvislou mapu:
(graf s nakreslením v rovině)
! POZOR! Mapa není totéž co graf.
Co platí pro grafy, nemusí platit pro mapy. Co platí pro mapy, musí platit pro grafy.
Pro souvislou mapu:
k = 1, tj.
u + s = h + 1 + 1
u + s = h + 2
u + s – h = 2
4-boký jehlan: krychle:
5 uzlů 8 uzlů
5 stěn 6 stěn
8 hran 12 hran
Eulerova věta o mnohostěnech
Věta:
Součet uzlů a stěn v každé mapě je alespoň 8
u3 + s3  8
3s3 + 4s4 + 5s5 + … = 2h
3u3 + 4u4 + 5u5 + … = 2h
(A) 3(s3+u3) + 4(s4+u4) + 5(s5+u5) + … = 4h
víme: (u3 + u4 + u5 + …) + (s3 + s4 + s5 + …) = h + 2
(C) 4(u3+s3) + 4(u4+s4) + … = 4h + 8
(B-A) u3+s3 + 0 – s5 –u5 -2s6 -2u6 … = 8
25. 11. 2014
PERT - zkratka používaná ekonomy
- Program evaluation and review technique
Je zobecněním metody kritické cesty(CPM). Tato metoda se používá k řízení složitých akcí majících stochastickou
povahu. Zde se doba trvání každé dílčí činnosti chápe jako náhodná proměnná mající určité rozložení
pravděpodobnosti. [Empiricky bylo zjištěno, že v praxi toto nejlépe vystihuje tzv. beta rozdělení, které lépe vystihuje
proměnlivost provozních podmínek (například důlní provoz). ... to je pro mě novinka....]
CMP - Critical Path Method = metoda kritické cesty
- používá Dijkstrův algoritmus pro hledání nejkratší cesty
 …… číslo uzlu
 …… minimální čas
 …… maximální čas
- orientovaný graf
- cyklický graf cyklus
- neobsahuje cykly
Obložené chlebíčky:
1) Plátek veky, vlašský salát, salám, vajíčko, okurka
2) Plátky veky, máslo, vaječná pomazánka, okurka
Vaječná pomazánka: vajíčko natvrdo, hořčice, nakrájená cibule
Činnosti:
a) Krájení a loupání salámu 4 min
b) Krájení veky 5 min
c) Vaření vajec 11 min
d) Krájení cibule 5 min
e) Krájení okurek 2 min
f) Mazání salátem 8 min
g) Mazání máslem a pomazánkou 5 min
h) Loupání a krájení vajec 4 min
i) Pokládání salámu 9 min
j) Pokládání vejce 3 min
k) Pokládání okurky 2 min
l) Výroba (míchání) pomazánky 10 min
m) Skládání na mísu 5 min
První úroveň – úkony, které mohu dělat bez toho, abych měla něco jiného nachystané.
Druhá úroveň – musím vykonat činnosti, které předchází těm ostatním
Další úrovně – navazující činnosti
- hledáme nejdelší cestu
Algoritmus hledání minimální cesty pro acyklický graf:
1) Očíslujeme uzly vhodným způsobem (menší před větším)
2) Určíme orientovanou vzdálenost:  …… nedostanu se tam
0 …… uzel sám od sebe
Vzdálenost x od u1 = maximální vzdálenost ze všech uzlů, přes které se dostanu do tohoto uzlu
2. 12. 2014
TOKY V SÍTÍCH
cca 30 osob
cca 6 osob
Tramvaje 9 a 11 mají normálně určené trasy tak, že část jedou dohromady, kvůli počasí se musela dělat
optimalizace
Jak toho přepravit co nejvíce z jednoho místa to místa druhého?
Čísla hran nejsou vzdálenosti, jako při hledání nejkratší cesty či minimální kostry,, ale kapacita (kolik se tam
do toho vejde, kolik proteče, kolik může projet aut, ...).
Když něco bude protíkat, tak to musí mít směr. Můžeme si to představit tak, že na jedné straně lejeme do
potrubí určité množství vody za vteřinu a na druhé straně nám voda vytéká nebo si to představíme jako
město, kde se auta dostávají z jednoho konce na druhý.
Chceme poslat co nejvíce z S do T.
Z S může vyjet naráz 31 aut, do T může naráz dojet 34 aut. Menší z těchto čísel je také horní hranicí
maximálního toku danou sítí.
1. Cesta – červená - nejprve si vyberu nejmenší kapacitu na trase a tu naplním.
- S-A-B-G-C-T
- 8 autíček
2. Cesta – zelená - nejmenší možný počet je sedm, takže pošlu sedm
- S-D-B-C-T
- 7 autíček
3. Cesta – modrá - S-D-B-C-T
- 2 autíčka
4. Cesta – fialová - S-A-D-E-F-T
- 4 autíčka
5. Cesta – oranžová - S-D-E-F-T
- 1 autíčko
To co kreslíme je postup, neznamená to, že to na konci bude všechno obsažené. Kdybychom v prvním kroku
nevynulovali tři osmičkové hrany, udělali bychom líp – respektive nemuseli bychom to pak po sobě
spravovat..
Pouze pro toky, nikoliv pro kapacity hran, graf splňuje Kirchhofův zákon (množství, které teče do uzlu je
stejné jako množství, které z uzlu odtéká)
- přerušované hrany jsme nepoužili, není to výhodné (poznámka na okraj: budou se nám možná hodit jako
objízdné trasy)
Když hledáme maximální tok, tak to souvisí s minimálním řezem – graf by se měl rozpadnout na dvě části.
Potrubí – na začátku graf neorientovaný (může téct tam i zpátky) v momentě když něco pošlu, tak to teče
nějakým směrem, nemůžu to vzít zpátky.
Můžu jít proti směru tam, kde můžu kapacitu snížit a po směru tam, kde ji můžu zvýšit.
HAMILTONOVSKÝ GRAF
Hledáme souvislou kružnici, která obsahuje všechny uzly grafu.
Nutná podmínka pro existenci kružnice:
 G je souvislý graf
 G nemá uzly stupně 1
 G není strom
Dostatečná podmínka pro existenci kružnice: předpoklad |U| = u  3
 (Dirac) Je-li každý uzel stupně
𝑢
2
, pak je graf hamiltonovský
 Úprava předchozí podmínky (Ore): Je-li součet stupňů libovolných dvou uzlů
nespojených hranou roven alespoň
𝑢
2
, pak je graf hamiltonovský.
 (Pósa) Jestliže pro každé k <
𝑢
2
(kN) je počet uzlů stupně max. k menší než k, pak je graf
hamiltonovský.
Dostatečná podmínka je moc silná, existují grafy (viz grafy vzniklé z plaónských těles), které podmínky
nesplňují, ale hamiltonovské jsou.
Pósova podmínka v praxi: aby byla splněna, musel by níže uvedený graf obsahovat maximálně 2 uzlu stupně
nejvýše 3 – z obrázku je vidět, že je to splněno.
Uzly vyšších stupňů nás nezajímají, pouze do st. 3,5, tj. polovina
z počtu uzlů (7)
(Kdyby ale uzel stupně 3 v daném grafu měl stupeň 2, Pósova podmínka by
splněna nebyla , ale hamiltonovská kružnice by v grafu existovala.)