Skripta







0 0 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 1
1 0 0 0 0 0
1 1 1 0 0 1
0 0 1 0 1 0






Maticový popis grafů s málo hranami je dosti neúsporný. Matice pak obsahuje
značné procento nul a vyhledávání nenulových prvků stojí zbytečně mnoho času.
Popis tohoto grafu lze úsporně zakódovat následující posloupností:
(6,6,1,4,1,5,2,5,3,5,3,6,5,6).
První číslo udává počet uzlů, druhé počet hran, a pak následuje soupis všech hran
(závorky v označení vynecháváme).
Příklad: Město Královec (Königsberg, Kaliningrad) se rozkládá na obou bře-
zích řeky Pregel (Pregolja) a na dvou ostrovech. Břehy a ostrovy jsou spojeny
sedmi mosty, obrázek 2.31. Obyvatelé se zajímali, zda je možné jít na procházku,
aby se prošlo všemi mosty, a přitom po žádném nešlo dvakrát. Kde začít, v ja-
kém pořadí mosty přecházet a kde skončit? Byly dokonce uzavírány sázky, dokud
L. Euler v roce 1736 nedokázal, že taková procházka není možná. Tento problém
a jeho řešení bývá označován za počátek teorie grafů. Vede to na úlohu, zda lze
graf na obrázku 2.32 sestrojit jedním tahem.
Graf lze sestrojit jedním tahem, když v něm existuje tah obsahující všechny
hrany grafu a každou právě jednou. Například domeček na obrázku 2.33 se dá
nakreslit, aniž bychom některou čáru kreslili dvakrát nebo zvedli tužku od papíru.
L. Euler dokázal, že vytvořit tah procházející všemi hranami souvislého neori-
entovaného grafu je možné pouze při splnění jednoho z těchto dvou předpokladů:
– buď jsou všechny uzly grafu sudého stupně – pak je možné začít v kterémkoliv
z nich a na konci se do něj opět vrátíme (jde o tzv. uzavřený eulerovský tah),
– anebo jsou dva uzly lichého stupně a všechny ostatní uzly sudého stupně – pak
je nutné začít v některém uzlu lichého stupně a tah bude ukončen ve druhém uzlu
lichého stupně (jde o tzv. otevřený eulerovský tah).
24
2. grafy
Obrázek 2.31: Plán města Královec
Obrázek 2.32: Graf procházky po mostech
O něco komplikovanější situace nastává, uvažujeme-li graf orientovaný. Pak
musí platit:
– buď vstupní stupeň se rovná výstupnímu stupni ve všech uzlech grafu – pak je
možné nalézt uzavřený eulerovský tah,
– anebo je v jednom uzlu výstupní stupeň o jednotku větší – zde se musí začít –
a současně v jiném uzlu o jednotku menší – zde se bude končit.
Graf se nazývá eulerovský graf, jestliže všechny jeho uzly mají sudý stupeň
větší nebo rovný dvěma.
Jak víme, takový graf se dá sestrojit jedním uzavřeným tahem. Na některé
obrázky jeden tah nestačí, např. čtverec s oběma úhlopříčkami nebo graf na ob-
rázku 2.32. Vzniká tedy přirozená otázka, kolik nejméně tahů je třeba k nakreslení
obrázku, abychom žádnou čáru nekreslili dvakrát.
Jestliže G je souvislý neorientovaný graf, který obsahuje k vrcholů lichého
Obrázek 2.33: Jednotažka domečku
25
Operační výzkum
stupně, pak nejmenší počet tahů pokrývajících hrany grafu G je roven k/2.
Graf je hamiltonovský, jestliže v něm existuje kružnice (cyklus) procháze-
jící všemi uzly grafu. Název je podle Williama R. Hamiltona, který v polovině
19. století připojil ke každému z dvaceti vrcholů pravidelného dvanáctistěnu, je-
hož povrch je tvořen jedenácti shodnými pětiúhelníky, jméno některého světového
velkoměsta a nabídl výrobci hraček hlavolam, jehož řešením je cesta kolem světa
po hranách dvanáctistěnu, během níž se vyjde z některého města, každým z dal-
ších měst se projde právě jednou a nakonec se vrátí do výchozího města.
Grafová formulace hlavolamu: Je dán graf o 20 uzlech (vrcholy dvanáctistěnu),
hrany grafu (je jich 30) odpovídají hranám dvanáctistěnu; tedy jde o pravidelný
graf 3. stupně na dvaceti uzlech. Úkolem je v tomto grafu najít kružnici prochá-
zející všemi uzly (tzv. hamiltonovskou kružnici). Řešení je na obrázku 2.34.
Obrázek 2.34: Hamiltonův hlavolam
Je však zřejmé, že existují grafy, které hamiltonovské nejsou. Takové jsou
například všechny stromy, protože v nich neexistuje žádná kružnice, tím méně
hamiltonovská kružnice. Dále například graf vrcholů a hran rombického dodeka-
edru zobrazený na obrázku 2.35 také není hamiltonovský.
Obrázek 2.35: Rombický dodekaedr
26
2. grafy
Na grafu je 6 černých a 8 bílých vrcholů, které jsou umístěny tak, že se na každé
hraně střídají. Proto sestrojit cestu takovou, aby přechod od vrcholu k vrcholu
byl doprovázen změnou barvy není možný. K tomu by bylo potřeba, aby černých
a bílých vrcholů byl stejný počet.
Platí však tato tvrzení: Úplný graf s více než dvěma vrcholy je vždy hamilto-
novský. Jestliže pro graf s n uzly (n ≥ 3) platí stu+stv ≥ n pro každé dva různé
uzly, které nejsou spojeny hranou, pak je hamiltonovský. (Dostatečná podmínka,
aby byl graf hamiltonovský; nutná podmínka není známa.)
Například pro hranami nespojené dvojice uzlů grafu na obrázku 2.36 platí:
stx + sty = 2 + 3 = 5, stx + stw = 2 + 3 = 5, stv + stz = 3 + 3 = 6. Protože
n = 5, je tento graf hamiltonovský.
Obrázek 2.36: Hamiltonovský graf
Příklad: Může jezdec projít šachovnici tak, aby každým polem prošel právě
jednou a posledním tahem se vrátil na výchozí pole? Grafová formulace: Uvažujme
graf, jehož uzly jsou jednotlivá pole na šachovnici. Dva uzly jsou spojeny hranou,
když jezdec může skočit z jednoho pole na druhé. Úkolem je v tomto grafu najít
hamiltonovskou kružnici. Je známo, že popsaný graf je hamiltonovský. Dodnes se
však neví, kolik hamiltonovských kružnic v tomto grafu vlastně existuje. Nakreslit
daný graf nemá smysl, neboť diagram by byl značně nepřehledný. Hamiltonovskou
kružnici popíšeme tak, že do polí schematicky znázorněné šachovnice vepíšeme
čísla 1,2,...,64 v takovém pořadí, v jakém jimi bude jezdec postupně procházet.
Řešení, které uvádíme, popsal v roce 1862 šachista Karl Jänisch. Je mimořádně
důvtipné tím, že je současně magickým čtvercem – součet čísel v každém řádku
a v každém sloupci je 260.
50 11 24 63 14 37 26 35
23 62 51 12 25 34 15 38
10 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 1 20 41 54 29
59 4 45 8 53 32 17 42
6 47 2 57 44 19 30 55
3 58 5 46 31 56 43 18
27
Operační výzkum
2.2 Některé grafové problémy
2.2.1 Problém čínského listonoše
Listonoš musí denně projít všechny ulice svého obvodu a vrátit se na místo,
odkud vyšel. Jde mu o to, aby tato cesta byla co nejkratší. Obvod je souvislý
ohodnocený graf, jehož hrany (ulice) jsou ohodnoceny délkou, uzly jsou rozcestí.
Hledá se nejkratší uzavřený sled, který obsahuje alespoň jednou každou hranu
grafu.
Listonoš to má nejsnazší, jestliže graf je eulerovský (všechny uzly mají sudý
stupeň). Pak může procházet obvodem tak, jako by kreslil graf jedním tahem.
Každou ulici projde právě jednou a nakonec se vrátí na to místo, odkud vyšel.
Taková cesta je zřejmě ze všech možných cest nejlepší, neboť žádnou ulicí nepro-
chází vícekrát. Neexistuje-li v grafu uzavřený eulerovský tah (tj. v grafu jsou i uzly
lichého stupně), pak uzavřený sled pokrývající všechny hrany musí procházet ně-
kterými hranami vícekrát. Dá se ušetřit minimalizací vícekrát procházených hran
(metodou nejlevnějšího párování). Například pro graf na obrázku 2.37 je řešení:
a−b−f −d−f −b−g −d−c−g −a−e−c−e−a,
4 + 1 + 1 + 1 + 1 + 2 + 4 + 4 + 5 + 3 + 2 + 2 + 2 + 2 = 34.
Obrázek 2.37: Obvod čínského listonoše
Možná, že je vám divné, proč jde zrovna o problém čínského listonoše. Copak
u nás nemají listonoši stejné problémy? Výraz „problém čínského listonošecsquotedblright vznikl
ne zcela přesným překladem z angličtiny, ale vžil se natolik, že se stále používá.
Ve skutečnosti však jde o „čínský problém listonošecsquotedblright, protože jeho autorem je
čínský matematik Kwan.
Užití úlohy: optimalizace automatického kreslení výkresů, map na počítači
(perový nebo řezací plotr), svoz odpadu z městských ulic, trasy čištění vozovek.
2.2.2 Problém obchodního cestujícího
Máme k měst, vzdálenosti mezi nimi známe. Cestující se vydá na cestu z jednoho
z nich tak, že navštíví všechna ostatní města, každé právě jednou, a vrátí se
do výchozího města. Jde mu opět o to, aby tato cesta byla co nejkratší. Hledá
se nejkratší hamiltonovská kružnice v úplném hranově ohodnoceném grafu. Uzly
jsou města, hrany jsou ohodnocené vzdálenostmi mezi městy.
28
2. grafy
Obrázek 2.38: Rajon obchodního cestujícího
Příklad: Máme dánu matici délek hran ohodnoceného grafu na obrázku 2.38.
A = (aij) =



0 pro i = j,
∞ kdyžhranaz i do j neexistuje,
délkanejkratšíhranyz i do j.
a b c d e f
a 0 4 10 18 5 10
b 4 0 12 8 2 6
c 10 12 0 4 18 16
d 18 8 4 0 14 6
e 5 2 18 14 0 16
f 10 6 16 6 16 0
Pro daný úplný graf má řešení problému obchodního cestujícího tvar:
a−c−d−f −b−e−a, 10 + 4 + 6 + 6 + 2 + 5 = 33. (Přitom např. cesta po
obvodu dá v součtu 60.)
Při řešení těchto úloh se používá tzv. metoda větvení a mezí (Branch and
Bound Method). Je to iterační metoda pro hledání globálního extrému funkce
f na množině přípustných řešení M, založená na opakování následujících dvou
operací:
– větvení, při němž se nejprve množina M, později její vybraná podmnožina,
rozkládá na po dvou disjuktní podmnožiny. Postup rozkladu množiny M se dá
znázornit stromem, jehož uzly odpovídají jednotlivým podmnožinám;
– omezování, při němž se pro každou podmnožinu získanou předchozí operací
určuje dolní (při minimalizaci), resp. horní (při maximalizaci) mez hodnot funkce
f na této podmnožině.
Pro další rozklad se volí podmnožina s nejnižší dolní, resp. nejvyšší horní mezí.
Cílem je najít takové přípustné řešení, pro něž hodnota funkce f není větší než
dolní meze, resp. není menší než horní meze dosud nerozložených podmnožin.
Takové řešení je optimální.
Užití úlohy: kromě dealerství rozvoz zboží ze skladu do prodejen, vrtání děr
číslicově řízeným obráběcím strojem (minimalizace přesunů).
29
Operační výzkum
2.2.3 Problém minimální kostry grafu
Máme souvislý graf G. Jeho podgraf K je kostra grafu G, jestliže K je strom ob-
sahující všechny uzly grafu G. V grafu G ponecháme uzly, ale vynecháme některé
hrany. Například na obrázku 2.39 je graf G a jeho dvě kostry K a Kprime.
Obrázek 2.39: Graf a jeho kostry
Kdysi dávno, v dvacátých letech minulého století v začátcích elektrifikace, se
na profesora Otakara Borůvku obrátili energetici, kteří chtěli z malé elektrárny
přivést elektřinu do okolních obcí tak, aby elektrické vedení bylo co nejkratší a tím
i nejlevnější.
Grafová formulace problému: Je dán neorientovaný hranově ohodnocený sou-
vislý graf. Hledá se jeho kostra, která má nejmenší součet ohodnocení hran mezi
všemi kostrami daného grafu, tzv. minimální (nejlevnější) kostra tohoto grafu.
Profesor Borůvka energetikům jejich úlohu vyřešil. Proto se také někdy mluví
o problému profesora Borůvky.
Příklad: Pro graf na obrázku 2.40 má minimální kostra hodnotu 3 + 4 + 1 +
2 + 5 + 2 + 2 = 19.
Obrázek 2.40: Minimální kostra
Úloha nemusí mít jediné řešení, minimálních koster může být v grafu více.
Například obrázek 2.41.
30
2. grafy
Obrázek 2.41: Dvě minimální kostry
Užití úlohy: Má se propojit n míst například telefonní sítí, vedením vysokého
napětí, železnicí apod. Pro každou dvojici míst je znám odhad nákladů na po-
stavení jejich přímého spojení. Snahou je propojit všechna místa co nejlevněji.
V zimě se udržuje sjízdná co nejkratší část silniční sítě, která vzájemně propojí
všechny obce v dané oblasti.
2.2.4 Problém nalezení optimálních cest v grafu
Nalézt nejlepší cestu, nejlepší podle různých kriterií, patří k častým problémům
ekonomické a technické praxe. Například nejširší cesta (cesta s největší propust-
ností, s největší výškou podjezdů, s největší nosností mostů atd.) je taková cesta,
do níž se vejde co nejširší vozidlo. Obráceně nejužší cesta (údržba vozovek s co
nejužším pluhem) je taková cesta, u níž se šířky úseků vejdou do šířky pluhu,
který má být co nejužší, a přitom, aby všechny úseky cesty byly zcela bez sněhu.
Další dvojicí úloh je hledání nejkratších cest (s minimální délkou) a nejdelších
cest (s délkou maximální). A konečně dvojice nejspolehlivější cesta (s maximál-
ním součinem pravděpodobností) a nejporuchovější cesta (s minimálním součinem
pravděpodobností).
Například na obrázku 2.42 má nejširší cesta z uzlu 1 do uzlu 9 šířku 8, nejužší
cesta šířku 7.
Obrázek 2.42: Nejširší a nejužší cesta
Nejkratší cesta na obrázku 2.43 z uzlu 1 do uzlu 9 má délku 23, nejdelší cesta
délku 34.
Nejspolehlivější cesta na obrázku 2.44 z uzlu 1 do uzlu 9 má spolehlivost
51,84%, nejporuchovější cesta spolehlivost 10,5%.
Při řešení těchto úloh se používá tzv. Bellmanův princip optimálnosti, který
říká, že každá část optimální cesty je optimální cestou (vede-li z místa A do místa
C optimální cesta přes místo B, musí být i cesta z A do B optimální).
31
Operační výzkum
Obrázek 2.43: Nejkratší a nejdelší cesta
Obrázek 2.44: Nejspolehlivější a nejporuchovější cesta
2.2.5 Problém optimální lokace
Najít nejvhodnější polohu pro umístění skladiště, závodu apod. vzhledem k da-
ným polohám prodejen, měst apod. a jejich spotřebě.
Při řešení určujeme matici (nejkratších) vzdáleností mezi jednotlivými vrcholy
odpovídajícího grafu
D = (dij) =



0 pro i = j,
∞ kdyžcestaz i do j neexistuje,
délkanejkratšícestyz i do j
metodou minimálního sčítání.
Jestliže známe všechny nejkratší vzdálenosti míst (např. v kilometrech), mů-
žeme násobením matice vzdáleností vektorem, představujícím požadavky jednot-
livých spotřebitelů (např. v tunách), dostat výsledný vektor objemu přepravy
(např. v tunokilometrech). Minimální prvek vektoru přepravy určuje nejvhod-
nější vrchol pro umístění uvažovaného zdroje.
Příklad: Optimální umístění skladiště, je-li rozmístění spotřebitelů dáno gra-
fem na obrázku 2.45 a požadavky dány vektorem (1,3,2,1,5), je v uzlu u5.
2.2.6 Problém batohu
Lupič má batoh, do kterého může dát nejvýše K kilogramů kořisti. Jeho lup se
skládá z n předmětů, přičemž j-tý předmět má hmotnost aj a cenu cj. Cílem
lupiče je odnést v batohu co nejdražší kořist, ale nesmí batoh přetížit.
32
2. grafy
Obrázek 2.45: Poloha skladiště
Příklad: Řešením problému batohu, ve kterém n = 4, K = 15, hmotnosti
jednotlivých předmětů jsou 7, 6, 4 a 3 kg a jejich ceny jsou po řadě 2, 3, 4 a 5
tisíc Kč, je výběr předmětů o hmotnosti 6, 4 a 3 kg, které mají celkovou cenu 12
tisíc Kč.
Tato úloha má mnoho poctivějších podob, stačí místo lupiče si představovat
turistu balícího se na cestu. Tento model lze dále v praxi uplatnit při sestavování
rozvrhů a při plánování paralelně probíhajících procesů, které spotřebovávají ně-
jaký materiál, energii nebo práci. Vždy se snažíme co nejužitečněji vytížit daný
zdroj.
Pro řešení problému batohu existuje řada postupů založených na různých
principech, např. opět metoda větvení a mezí, nebo hledání nejdelší cesty ve
speciálním grafu.
2.2.7 Problém maximálního toku v síti
Síťový graf (síť) je orientovaný, souvislý, ohodnocený graf s jedním vstupním uz-
lem (nevstupuje do něj žádná hrana, zdroj) a jedním výstupním uzlem (nevystu-
puje z něj žádná hrana, stok, spotřebič). Graf představuje síť nějakého potrubí,
jímž protéká kapalina ze zdroje ke stoku. Orientace každé hrany představuje směr
proudění, její ohodnocení objem kapaliny, který příslušným úsekem potrubí může
protéci za časovou jednotku. Měli bychom určit celkový objemový tok potrubím.
Můžeme také zkoumat i jiné sítě a toky. Například po silnicích nebo železnicích
dopravovat určité zboží. Stejně jako u úseků potrubí lze i u úseků komunikací
určovat propustnost, tj. množství zboží, které lze po nich dopravit za časovou
jednotku. Pak řešíme organizaci dopravy zboží, jak to celková propustnost sítě
dovoluje.
Máme dánu síť tvořenou n+1 uzly P0,P1,...,Pn a hranami (Pi,Pj). Z uzlu P0
(vstupu) je posílána kapalina, plyn, nebo náklad do uzlu Pn (výstupu). Hranám
sítě je přiřazeno nezáporné číslo hij, tzv. propustnost (kapacita) hrany. Tok xij
v hraně (Pi,Pj) je množství látky, které projde v této hraně za jednotku času.
Předpokládáme, že toky vyhovují omezením
33
Operační výzkum
(1) 0 ≤ xij ≤ hij tok je v každé hraně nezáporný a nepřesahuje její propustnost;
(2) n−1summationtext
i=0
xis = nsummationtext
j=1
xsj, s negationslash= 0,n množství látky vstupující do každého uzlu (kromě
zdroje a spotřebiče) je rovno množství látky z něj vystupující – Kirchhoffův zákon
(vyjadřuje skutečnost, že v síti nedochází k hromadění nebo ztrátám).
Hledáme maximální tok Φ mezi uzly 0 a n za předpokladu neomezeného
zdroje, tj. řešení soustavy podmínek (1), (2), které maximalizuje výraz
Φ =
n−1summationdisplay
i=0
xin =
nsummationdisplay
j=1
x0j.
Φ určuje maximální propustnost sítě, což je tedy maximálně možný součet toků
vstupujících do stoku nebo maximálně možný součet toků vystupujících ze zdroje.
Tok v uvažované síti je tok od zdroje ke spotřebiči. Přidáním tzv. návra-
tové hrany ze spotřebiče ke zdroji dostáváme tzv. cirkulaci, kdy podmínku (2),
Kirchhoffův zákon, splňují všechny uzly sítě.
Obecnější formulace úlohy připouští libovolné dolní omezení toku v hranách.
Podmínka (1) má tvar lij ≤ xij ≤ hij, kde lij je dolní a hij horní omezení toku
v hraně (Pi,Pj). Je-li xij = hij, je hrana nasycená, je-li xij < hij, nenasycená,
rozdíl hij −xij je tzv. zbytková kapacita.
Řešení problému maximálního toku v síti se opírá o Fordovu–Fulkersonovu
větu: Velikost maximálního toku od zdroje ke spotřebiči je rovna kapacitě mini-
málního řezu oddělujícího zdroj a spotřebič. To připomíná úsloví, že řetěz je tak
pevný, jak pevný je jeho nejslabší článek.
Hranový řez mezi P0 a Pn je množina hran v dané síti, po jejímž odstranění
neexistuje cesta z P0 do Pn. Tedy množina U všech uzlů sítě je rozdělena na dvě
disjunktní podmnožiny X,Y (X∪Y = U, X∩Y = ∅) takové, že P0 ∈ X, Pn ∈ Y
a řez pak představuje množinu orientovaných hran (Pi,Pj) splňujících podmínky
Pi ∈ X, Pj ∈ Y. Kapacita řezu je součet kapacit (propustností) hran tohoto
řezu. Do řezu nezahrnujeme opačně orientované hrany, tj. takové, které směřují
z podmnožiny obsahující výstupní uzel do podmnožiny se vstupním uzlem.
Příklad: Uvažujme síť na obrázku 2.46.
Obrázek 2.46: Řezy v síti
Řez I obsahuje hrany 1−2,1−5,1−3, kapacita řezu je 4 + 10 + 2 = 16.
Řez II obsahuje hrany 1−2,5−6,3−7, kapacita řezu 4 + 6 + 5 = 15.
34
2. grafy
Řez III obsahuje hrany 1−2,6−8,1−3, kapacita řezu 4+3+2 = 9 je minimální.
Maximální tok má tedy taky hodnotu 9. Horní cestou 1−2−4−8 tok 4, prostřední
cestou 1−5−6−8 tok 3 a dolní cestou 1−3−7−8 tok 2, dohromady 9.
2.2.8 Problém čtyř barev
Máme zeměpisnou mapu, na níž je několik států. Chceme, aby každý stát byl
vybarvený nějakou barvou tak, aby žádné dva sousední státy nebyly obarveny
stejně. Chceme zjistit, jaký počet barev nezbytně potřebujeme, abychom mohli
takto obarvit každou zeměpisnou mapu.
Aby byla formulace problému korektní, je nutné upřesnit dvě skutečnosti.
Předpokládáme, že území každého státu je „souvislécsquotedblright (což v praxi není vždy
splněno – viz např. Aljaška v USA) a dále dva státy považujeme za sousední,
když mají společnou hraniční „čárucsquotedblright, tj. nedotýkají se v izolovaných bodech.
Lehce se dá ukázat, že je nutné mít k dispozici alespoň čtyři barvy, obrázek 2.47.
Ve všech konkrétních příkladech se vždy podařilo najít obarvení čtyřmi barvami.
Nalezení důkazu, že je tomu tak zákonitě, bylo obtížné a patřilo k nejznámějším
matematickým problémům 20. století.
Přeformulujeme si uvedený problém do grafové terminologie. Mějme dánu ně-
jakou zeměpisnou mapu. Nyní zkonstruujeme graf G následovně: Na území kaž-
dého státu zvolme jeden bod; tyto body vytvoří množinu uzlů. Dva uzly spojíme
hranou, právě když příslušné státy sousedí. Takto získaný graf je jistě rovinný,
neboť hrany můžeme kreslit tak, aby neprocházely územím žádného dalšího státu.