Skripta

dilo řadu problémů, jež přispěly
k rozvoji teorie grafů. Gustav R. Kirchhoff uveřejnil své práce o elektrických ob-
vodech, Arthur Cayley o strukturních vzorcích v organické chemii. První knihu
o grafech napsal Dénes König. Vyšla pod názvem Teorie konečných a nekonečných
grafů (Theorie der endlichen und unendlichen Graphen) v Lipsku v roce 1936.
Grafem rozumíme množinu bodů a jejich spojnic. Body nazýváme uzly (vr-
choly, vertices), spojnice nazýváme hrany (vazby, edges). Například plánky, elek-
trické obvody, chemické vzorce, dopravní sítě, sociologické vztahy apod. můžeme
popisovat pomocí grafů. Grafy lze s výhodou znázorňovat kreslením formou dia-
gramu. Uzly kreslíme jako body nebo kroužky v rovině a hrany jako úsečky nebo
oblouky spojující příslušné dvojice uzlů.
Graf je konečný, jestliže je počet uzlů konečný. Například na obrázku 2.1.
Obrázek 2.1: Příklad grafu
V opačném případě je graf nekonečný. Například na obrázku 2.2.
Obrázek 2.2: Příklad nekonečného grafu
Zde se však budeme zabývat pouze konečnými grafy, aniž bychom to vždy
výslovně uváděli.
11
Operační výzkum
Jestliže mezi některou dvojicí uzlů existuje větší počet hran než jedna (para-
lelní hrany), máme multigraf. Například ve vzorci kyanovodíku
H −C ≡ N,
kde mezi atomy uhlíku a dusíku je trojná vazba. Jinak máme prostý (jednoduchý)
graf.
Graf je orientovaný, jestliže každé hraně je přiřazen určitý směr. Šipkou ur-
čujeme počáteční a koncový uzel hrany. Například na obrázku 2.3.
Obrázek 2.3: Příklad orientovaného grafu
V opačném případě je graf neorientovaný. Smíšený graf obsahuje oba druhy
hran.
Abychom mohli grafy zkoumat matematicky, uvedeme nyní formální matema-
tické definice.
Je-li U neprázdná konečná množina, H konečná množina a γ zobrazení mno-
žiny H do množiny{{u,v}; u ∈ U, v ∈ U}, pak uspořádanou trojici G = (U,H,γ)
nazýváme neorientovaný graf. Prvky v množině U se jmenují uzly, prvky v mno-
žině H hrany grafu. Zobrazení γ definuje umístění hrany: Je-li h ∈ H, γ(h) =
{u,v}, pak říkáme, že hrana h spojuje uzly u,v. Přitom nevylučujeme případ, kdy
u = v; pak příslušnou hranu nazýváme smyčkou v uzlu u. Obyčejnou hranou bu-
deme rozumět hranu, která není smyčkou.Je-li proh1 negationslash= h2 splněnoγ(h1) = γ(h2),
pak h1,h2 nazýváme paralelními hranami.
Předpokládáme, že U∩H = ∅. Chceme-li zdůraznit, že U,H,γ náleží ke grafu
G, píšeme U(G),H(G),γG.
Je-li V neprázdná konečná množina, E konečná množina a ζ zobrazení mno-
žiny E do množiny V × V, pak uspořádanou trojici G = (V,E,ζ) nazýváme
orientovaný graf. Prvky v množině V jsou vrcholy, prvky v množině E hrany
grafu. Je-li e ∈ E, ζ(e) = (u,v), říkáme, že u je počáteční a v koncový vrchol
hrany e.
Zamysleme se nad uvedenými definicemi. Především vidíme, že se v nich ne-
vyskytují geometrické pojmy. Nemluví se o kroužcích a úsečkách nebo obloucích.
Uzly jsou prostě prvky nějaké množiny, hrany jsou uspořádané dvojice (v pří-
padě orientovaného grafu), nebo neuspořádané dvojice (pro neorientovaný graf)
takovýchto prvků. Proč tedy říkáme, že na určitém obrázku je graf? Je to stejné,
jako když v geometrii říkáme, že na určitém obrázku je přímka. Přímka však není
vrstva tuhy nebo tiskařské černi na papíře. Je to abstraktní pojem a je dokonce
nekonečná, takže na obrázku nemůže být ani znázorněna celá. Proto v teorii grafů
říkáme, že na obrázku je diagram grafu. Je třeba mít na paměti, že týž graf lze
většinou nakreslit mnoha k nepoznání různými způsoby. Není totiž jednoznačně
předem dáno ani rozmístění uzlů, ani tvar hran.
Z nakreslení téhož grafu dáváme obvykle přednost takovému, v němž jsou
hrany kresleny pokud možno přímo a s co nejmenším počtem průsečíků. Názor-
12
2. grafy
Obrázek 2.4: Tvary hran
nosti a snadnému kreslení zřejmě vděčí teorie grafů za svou oblibu i za četné
praktické aplikace.
V ekonomických aplikacích se zpravidla pracuje s ohodnocenými grafy. Je-li
hranám grafu přiřazena určitá hodnota, máme hranově ohodnocený graf. Na ob-
rázku 2.5 je příklad grafu, který znázorňuje silniční síť (část automapy).
Obrázek 2.5: Hranově ohodnocený graf
Diagram obsahuje nový prvek, tzv. ohodnocení hran, které v tomto případě
představuje vzdálenosti mezi křižovatkami silnic (uzly), např. v kilometrech.
Grafem se také mohou modelovat situace, v nichž jsou nějaké charakteristiky
připisovány uzlům. Pak by šlo o uzlově ohodnocený graf. Na obrázku 2.6 je příklad
takového grafu, který představuje postup výroby a montáže určitého výrobku.
Uzly jsou jednotlivé výrobní nebo montážní operace, jejich ohodnocení je nutný
čas příslušné operace. Hrany grafu pak znázorňují způsob, jak na sebe jednotlivé
operace navazují.
Formálně: Je-li G graf, f zobrazení množiny jeho hran do množiny reálných
čísel, pak uspořádaná dvojice (G,f) je hranově ohodnocený graf. Podobně se
definuje uzlově ohodnocený graf jako uspořádaná dvojice (G,f), kde G je graf a f
zobrazení množiny jeho uzlů do množiny reálných čísel.
Zobecněním grafů jsou hypergrafy (společnosti), které představují systém ne-
prázdných podmnožin množiny uzlů (místo hran spojující dva uzly máme něja-
kou podmnožinu - tým). Máme-li například množinu uzlů {a,b,c,d,e} a množinu
13
Operační výzkum
Obrázek 2.6: Uzlově ohodnocený graf
týmů {{a,b,c},{a,d,e},{c,d},{e}}, pak na obrázku 2.7 je znázorněn diagram
tohoto hypergrafu.
Obrázek 2.7: Hypergraf
Sled délky n z uzlu u do uzlu v v neorientovaném grafu G = (U,H,γ) je
střídavá posloupnost uzlů a hran u = u0,h1,u1,h2,u2,...,un−1,hn,un = v, kde
n ≥ 1 a u0,...,un jsou uzly a h1,...,hn jsou hrany takové, že hrana hi spojuje
uzly ui−1 a ui, tj. γ(hi) = {ui−1,ui} pro i = 1,...,n. Je-li u negationslash= v, je sled otevřený,
je-li u = v, je uzavřený. Tah je sled, v němž jsou všechny hrany navzájem různé.
Sled, v němž jsou všechny uzly navzájem různé, je cesta. Uzavřený tah, který je
také cesta, je kružnice. V orientovaném grafu se pro pojmy sled, cesta a kružnice
také používají termíny spojení, dráha a cyklus. Řetězec v orientovaném grafu je
posloupnost na sebe navazujících hran bez ohledu na orientaci.
Příklad: G = (U,H,γ), U = {w,x,y,z}, H = {a, b, c, d, e, f, g}, zobrazení
γ je dáno tabulkou
i a b c d e f g
γ(i) {w,x} {w,y} {w,z} {x,y} {x,z} {y,z} {z,z}
pak lze graf znázornit diagramem na obrázku 2.8.
Smyčka v uzlu z, tedy z,g,z je uzavřený sled délky 1, tj. kružnice.
Otevřený sled délky 3 w,a,x,e,z,f,y z uzlu w do uzlu y je tah i cesta. Uzavřený
14
2. grafy
Obrázek 2.8: Příklad na sledy
sled w,a,x,e,z,g,z,f,y,b,w z uzlu w do uzlu w je tah, ale ne cesta, ani kruž-
nice. Kružnice je např. w,a,x,e,z,c,w. Sled w,a,x,a,w je uzavřený, ale není to
kružnice.
Graf, v němž každé dva různé uzly jsou spojeny hranou, je úplný graf. Má-li n
vrcholů, značíme jej Kn. Například na obrázku 2.9 je úplný graf o čtyřech uzlech
K4.
Obrázek 2.9: Úplný graf K4
Graf je souvislý, když mezi každou dvojicí jeho uzlů existuje aspoň jeden sled
(u orientovaných grafů řetězec), který je spojuje. V opačném případě je nesouvislý.
Části (podgrafy) nesouvislého grafu, které jsou souvislé, jsou komponenty grafu.
Formálně: Jestliže G = (U,H,γ),Gprime = (Uprime,Hprime,γprime) jsou neorientované grafy
takové, že Uprime ⊆ U,Hprime ⊆ H a γprime(h) = γ(h) pro každé h ∈ Hprime, pak Gprime nazýváme
podgrafem grafu G. Pro u,v ∈ U položíme (u,v) ∈ r, právě když buď u = v, nebo
u negationslash= v a existuje v G sled z u do v. Pak r je ekvivalence na U. Pro každé Uprime ∈ U/r
definujeme Hprime = {h ∈ H; γ(h) ∈ {{uprime,vprime}; uprime ∈ Uprime,vprime ∈ Uprime}}, γprime(hprime) = γ(hprime)
pro každé hprime ∈ Hprime. Pak (Uprime,Hprime,γprime) je podgraf grafu G, který nazýváme jeho
komponentou. Graf se nazývá souvislý, má-li právě jednu komponentu; jinak se
nazývá nesouvislý. Komponenty grafu jsou jeho maximální souvislé podgrafy.
Například na obrázku 2.10 je nesouvislý graf se třemi komponentami.
Obrázek 2.10: Nesouvislý graf
15
Operační výzkum
Orientovaný graf je silně souvislý, existuje-li z každého jeho uzlu dráha do kaž-
dého jiného jeho uzlu. Například graf, jehož diagram je na obrázku 2.11.
Obrázek 2.11: Silně souvislý graf
Silně souvislý graf je ovšem vždy souvislý. Obráceně to neplatí. Na obrázku
2.12 je graf, který je souvislý a přitom není silně souvislý. Neexistuje v něm spojení
z uzlu u do uzlu v.
Obrázek 2.12: Souvislý, ale ne silně souvislý graf
Například při určování jednosměrnosti ulic je třeba dbát na to, aby oriento-
vaný graf sítě ulic byl silně souvislý. Bylo by jistě nemilé, kdyby se auto mohlo
dostat z jednoho místa do druhého, ale už ne zpět.
Jestliže v souvislém grafu G existuje uzel, jehož odstraněním vznikne nesou-
vislý graf, pak tomuto uzlu říkáme artikulace grafu G. Jestliže v souvislém grafu
G existuje hrana, jejímž odstraněním vznikne nesouvislý graf, pak této hraně ří-
káme most grafu G. Most rozděluje graf na dvě části, přičemž z jedné části nelze
přejít na druhou, aniž by cesta nevedla přes tento most. Obdobně je graf rozdělen
i artikulací. V grafu na obrázku 2.13 jsou tři artikulace a jeden most.
Obrázek 2.13: Artikulace a most
Existuje-li cesta z uzlu u do uzlu v v neorientovaném grafu G, pak vzdálenost
uzlů u,v v G je délka nejkratší cesty z u dov, kterou značíme d(u,v). Připomeňme,
že délka cesty je počet jejích hran. Jestliže žádná cesta z u do v v G neexistuje,
klademe d(u,v) = ∞.
16
2. grafy
Platí d(u,v) = 0, právě když u = v. Dále d(u,v) = 1, právě když uzly u,v
jsou spojeny hranou. Pro libovolné uzly u,v platí d(v,u) = d(u,v).
Největší vzdálenost dvou uzlů v konečném grafu G se nazývá průměr grafu G.
Graf na obrázku 2.14 má průměr rovný čtyřem.
Obrázek 2.14: Průměr a centrum grafu
Pro každý uzel u souvislého neorientovaného grafu G označme e(u) největší
ze vzdáleností uzlu u od ostatních uzlů grafu G. Uzel u, pro nějž je e(u) nejmenší,
se nazývá centrum grafu G.
V grafu na obrázku 2.14 platí: e(u1) = e(u7) = 4,e(u2) = e(u3) = e(u5) =
e(u6) = 3,e(u4) = 2, takže centrum tohoto grafu je uzel u4.
Centrum je latinský výraz pro střed. V grafu takový uzel nemusí být jenom
jeden. Obecně graf může mít center několik, například graf na obrázku 2.15a má
dvě centra. Pro graf na obrázku 2.15b dokonce platí, že každý uzel je centrum.
Obrázek 2.15: Více center grafu
Uveďme si praktické využití tohoto pojmu. Představme si společnost lidí, kteří
si ústně předávají nějaké zprávy (např. anekdoty). Členové této společnosti bu-
dou uzly grafu. Dva uzly budou spojeny hranou, právě když odpovídající osoby
přicházejí spolu do styku. Chceme-li, aby se nějaká zpráva rozšířila v této společ-
nosti co nejrychleji, bude nejlépe, když ji sdělíme tomu členu společnosti, který
představuje centrum grafu.
Další aplikací pojmu centrum grafu je optimální umístění požární zbrojnice.
Jestliže hrana h spojuje v neorientovaném grafu G uzly u a v, také říkáme,
že hrana h je incidentní s uzlem u a uzlem v a rovněž říkáme, že uzly u a v
jsou incidentní s hranou h. U každého uzlu je důležitý počet hran, které jsou
s ním incidentní. Říkáme mu stupeň uzlu a značíme pak symbolem stu, který
tedy znamená počet hran s vrcholem v u (smyčky počítáme dvakrát). Například
pro graf na obrázku 2.16 platí: stx = 0,sty = 3, stz = 1.
Pro uzel stupně 0, tedy pro uzel, který není incidentní se žádnou hranou,
máme speciální název, říkáme mu izolovaný uzel. Vezmeme třeba určitou spo-
lečnost, v níž si někteří lidé spolu tykají, jiní nikoliv (jde ovšem vždy o tykání
oboustranné). Tuto společnost můžeme vzít jako množinu uzlů grafu, kde hrany
17
Operační výzkum
Obrázek 2.16: Stupně uzlů
budou spojovat ty osoby, které si spolu tykají. Pokud si někdo netyká s nikým
z této společnosti, bude v tomto grafu izolovaným uzlem.
Součet stupňů všech uzlů grafu je roven dvojnásobku počtu hran grafu zmen-
šený o počet smyček tohoto grafu. Počet uzlů lichého stupně v každém konečném
grafu je číslo sudé.
Graf, v němž všechny uzly mají tentýž stupeň rovný k, je pravidelný graf
stupně k. Například na obrázku 2.17 je diagram pravidelného grafu stupně 3
na šesti uzlech.
Obrázek 2.17: Pravidelný graf 3. stupně na 6 uzlech
Úplný graf o n uzlech je pravidelný graf stupně n−1.
Je-li u uzel orientovaného grafu G, pak počet hran z něho vycházejících je
jeho výstupní stupeň st+u, počet hran do něho vcházejících jeho vstupní stupeň
st−u.
Součet výstupního a vstupního stupně uzlu dává stupeň tohoto uzlu, tj. st+u+
st−u = stu. Pro uzly u,v,w grafu na obrázku 2.18 platí: st+u = 3,st−u =
0,st+v = 1,st−v = 2,st+w = 0,st−w = 3.
Obrázek 2.18: Vstupní a výstupní stupeň uzlu
Graf je acyklický, jestliže v něm neexistuje žádná kružnice (cyklus). Strom je
souvislý acyklický graf. Nemá ani smyčky, ani paralelní hrany, je v jistém smyslu
18
2. grafy
minimální souvislý graf. Pojmenování strom je odvozeno z toho, jak lze tyto grafy
nakreslit, obrázek 2.19.
Obrázek 2.19: Strom
Strom, který má n uzlů, má přesně n−1 hran. Mezi každými dvěma různými
uzly existuje jediná cesta.
V polovině 19. století se anglický chemik A. Cayley zabýval otázkou, kolik
existuje izomerů uhlovodíku CnH2n+2. První tři členy uhlovodíkové řady, metan,
etan a propan mají jediný izomer, obrázek 2.20.
Čtvrtý člen již má izomery dva, butan a izobutan, obrázek 2.21. Atomy jsou
uzly grafu. Hranou jsou spojeny atomy, mezi nimiž je chemická vazba. Jak vidíme,
uvedené grafy jsou stromy.
Obrázek 2.20: Metan, etan a propan
Graf, jehož každá komponenta je strom, se nazývá les, obrázek 2.22. Les je
tedy graf neobsahující žádnou kružnici. Uzel stromu, který má stupeň rovný 1,
se nazývá list.
Strom, který má aspoň jednu hranu, má aspoň dva listy. Každá hrana stromu
je mostem. Každý uzel stromu je buď list, nebo je artikulací. Strom má buď jediné
centrum, nebo právě dvě centra spojená hranou.
19
Operační výzkum
Obrázek 2.21: Butan a izobutan
Obrázek 2.22: Les
Pro n ≥ 2 existuje strom o n uzlech, který obsahuje právě dva listy, tzv. had.
Pro n ≥ 3 může ve stromu o n uzlech existovat nejvýše n−1 listů. Strom, který
jich má právě n−1, je tzv. hvězda.
Obrázek 2.23: Had a hvězda
Užitístromů:klasifikačnístrom(členěnídruhůvbotanice,zoologii,rodokmen),
organizační schéma (rektorát, fakulty, ústavy), sportovní soutěže (turnaje), rozho-
dovací strom (diagram možných rozhodnutí), výpočetní technika (polská notace)
apod.
Je-li G neorientovaný graf o n uzlech, pak počet grafů na dané množině uzlů
je dán vztahem
gn = 2(n2).
Posloupnost (gn)∞n=1 rychle roste,
20
2. grafy
n 1 2 3 4 5 6 7 8 ···
gn 1 2 8 64 1 024 32 768 2 097 152 2 684 354 544 ···
proto při řešení úloh na grafech nakreslení nebo vypsání všech možností nemá
ve většině případů naději na úspěch.
Na třech uzlech tedy existuje 8 grafů, viz obrázek 2.24.
Obrázek 2.24: Grafy na třech uzlech
Některé z nich jsou si natolik podobné, že je nerozlišíme, pokud se nedíváme
na označení uzlů (jde o grafy nakreslené pod sebou). Tato podobnost se dá ma-
tematicky precizovat takto.
Grafy G = (U,H,γ), Gprime = (Uprime,Hprime,γprime) jsou izomorfní, když existuje dvo-
jice vzájemně jednoznačných zobrazení f : U → Uprime, g : H → Hprime takových, že
pro každé h ∈ H platí, jestliže γ(h) = {x,y}, pak γprime(g(h)) = {f(x),f(y)}.
V jistém smyslu důležitější než otázka kolik existuje na n uzlech všech grafů,
je problém, kolik na n uzlech existuje neizomorfních grafů. Například na čtyřech
uzlech existuje 64 grafů, avšak jen 11 neizomorfních grafů. Obrázek 2.25.
Obrázek 2.25: Neizomorfní grafy na čtyřech uzlech
I posloupnost (hn)∞n=1 neizomorfních grafů na n uzlech roste velmi rychle.
n 1 2 3 4 5 6 7 8 9 ···
hn 1 2 4 11 34 156 1 034 12 344 308 168 ···
Dokonce i počet neizomorfních stromů tn na n uzlech
21
Operační výzkum
n 1 2 3 4 5 6 7 8 9 10 ··· 15 ··· 20 ···
tn 1 1 1 2 3 6 11 23 47 106 ··· 7 741 ··· 823 065 ···
při veškeré jednoduchosti stromů roste pořád ještě tak rychle, že i jejich systema-
tický přehled pro poměrně malá n je nemožný.
Příklad: Ve třech domech bydlí tři sousedé. Poblíž jejich domů jsou tři studny.
Každý chce mít od svého domu cesty ke všem studním. Nikdo však nechce, aby
se některá jeho cesta křižovala se sousedovou. Je to možné zařídit?
Mějme graf G, jehož uzly jsou zmíněné tři domy a tři studny a jehož hrany
představují popsané cesty, obrázek 2.26. Každý uzel představující dům je tedy
spojen hranami se všemi uzly představujícími studně, přitom žádné dva uzly
představující domy nejsou spojeny hranou a rovněž žádné dva uzly představující
studně nejsou spojeny hranou. Pokud by bylo možné cesty postavit žádaným
způsobem, znamenalo by to, že graf G vyhovuje následující definici.
Obrázek 2.26: Tři domy, tři studny, graf K3,3
Jestliže lze graf G zobrazit v rovině tak, že jeho hrany nemají společný vnitřní
bod, pak se G nazývá rovinný (planární) graf.
Budeme-li zkoušet náš graf tří domů a tří studní zobrazit popsaným způsobem,
nepodaří se nám to. Tento graf totiž nepatří mezi rovinné grafy. Ne každý graf
je tedy rovinný a i rovinný graf lze nakreslit nerovinným způsobem. Na dalším
obrázku 2.27 je nakreslen jeden a týž graf třemi různými způsoby. Jedná se tedy
o příklad navzájem izomorfních grafů. Vzhledem k třetímu způsobu zakreslení
však jde o rovinný graf.
Obrázek 2.27: Izomorfní grafy
Biparitní graf je takový graf, jehož množina vrcholů je disjunktním sjednoce-
ním dvou množin S a T a každá hrana biparitního grafu má jeden krajní vrchol
v S a druhý v T. Množiny S,T nazýváme stranami biparitního grafu. U orientova-
ného grafu zpravidla požadujeme, aby všechny hrany byly orientovány souhlasně.
22
2. grafy
Úplný biparitní graf je takový biparitní graf, že každá dvojice vrcholů s ∈ S, t ∈ T
je spojena přesně jednou hranou. Úplný biparitní graf, jehož strany mají m a n
prvků, značíme Km,n.
Jak už víme, graf tří domů a tří studní (neboli podle právě uvedené definice
odborně graf K3,3) rovinný není. Stejně tak není rovinný ani úplný graf o pěti
uzlech, označuje se K5, obrázek 2.28. To si můžeme rovněž zkoušením ověřit.
Obrázek 2.28: Graf K5
Není-li nějaký graf G rovinný, potom zřejmě není rovinný ani žádný graf, který
z něho vznikne nahrazením některých hran cestami délky aspoň dvě. Říkáme, že
takový graf vznikl z grafu G dělením hran, obrázek 2.29.
Obrázek 2.29: Dělení hran na K5
Vyjmenovali jsme si různé případy, kdy graf není rovinný. Ve všech ostatních
případech graf rovinný je. Platí totiž následující tvrzení (Kuratowského věta).
Konečný graf je rovinný, právě když neobsahuje jako svůj podgraf graf K3,3,
graf K5, ani žádný graf vzniklý z některého z těchto grafů dělením hran.
Užití: tištěné spoje (prvky spojené vodiči) musí představovat rovinný graf, aby
v obvodu mezi některými úseky vodiče nedošlo k nežádoucímu vodivému spojení
a tím ke zkratu.
Má-li graf nevelký počet vrcholů a zejména hran, lze jej asi nejsrozumitelněji
popsat diagramem. Má to však dvě nevýhody. Obrázek často svádí k jednostran-
nému pohledu (srovnej obrázek 2.27) a není vhodný jako vstup do počítače. Proto
se používají také jiné způsoby popisu grafu. Matematicky elegantní je maticový
popis grafu. Pro zadání grafu je vhodné označit uzly přirozenými čísly 1,...,n.
Incidenční (vazební) matice (sousednosti) vrcholů grafu je čtvercová matice
n-tého řádu, kde n je počet uzlů, jejíž prvky aij udávají počet hran, které spojují
vrcholy i,j. Pro neorientované grafy je symetrická, bez smyček má na hlavní
diagonále nuly, u multigrafů její prvky mají i hodnoty větší než jedna.
23
Operační výzkum
Příklad: Uvažujme graf, jehož množiny vrcholů a hran jsou popsány výčtem
prvků: U = {1,2,3,4,5,6}, H = {{1,4}, {1,5}, {2,5}, {3,5}, {3,6}, {5,6}}.
Diagram grafu je na obrázku 2.30.
Obrázek 2.30: Příklad pro různé popisy grafu
Incidenční matice tohoto grafu má tvar: