1
Část I
Základní pojmy teorie grafů [Graph theory] V matematice grafem obvykle rozumíme grafické znázornění funkční závislosti. Pro tento předmět je však podstatnější pohled jiný. V teorii grafů rozumíme grafem objekt popsaný množinou vrcholů [vertices] a množinou hran [edges].
1
Neorientovaný graf
Definice 1 (Neorientovaný graf). Graf (z pohledu teorie grafů) definujme jako dvojici G = (V, E), kde V = {u1 , u2 , . . . , un } je konečná množina objektů, kterým říkáme vrcholy, někdy též uzly (dále budeme používat termín uzly) grafu a E = {ui , uj , i, j = 1, 2, . . . , n} je množina některých dvojic uzlů, kterým říkáme hrany grafu.
Obrázek 1: Příklad neorientovaného uzlového grafu – matice sousednosti (1) 2
4
1
6
3
5
Tak jak jsme zvyklí v matematice, je graf obvykle znázorněním určité situace a proto i my budeme na grafy nahlížet jako na realizace rozličných problémů. Graf pak může znázorňovat počítačovou síť, postup stavby rodinného domku, sociologické vztahy ve skupině apod. Uzly grafu ui , pro i = 1, 2, . . . , n, budeme zobrazovat jako očíslované je kroužky – viz obrázek 1. Hrany grafu ui , uj , pro i, j = 1, 2, . . . , n a i 6= j, budeme zobrazovat přímými nebo různě lomenými čarami. Obyčejný graf, tak jsem jej zavedli v definici 1, je grafem konečným, má tedy konečný počet uzlů a hran. Někdy bývá uvažováno vícero hran mezi dvěma uzly, ale touto situací se zabývat nebudeme – viz multigraf. Počet uzlů |V | = n omezuje i počet možných hran |E|, které lze v grafu udělat. Maximální počet hran v grafu bez vícenásobných hran mezi uzly a bez smyček (hrana, která vychází a končí v tom samém uzlu) je n2 . Počet všech různých n grafů vytvořených na množině n uzlů je tedy: 2( 2 ) . Pro efektivní popis grafů samotných, jakožto i popisu reálných situaci zadefinujme několik pojmů, které nám umožní srozumitelně a přesně hovořit o různých typech grafů o jejich vlastnostech a charakteristikách.
2
1
NEORIENTOVANÝ GRAF
Obrázek 2: Příklad neorientovaného uzlového grafu s vícero hranami 2
4
1
6
3
1.1
5
Definice/vysvětlení základních pojmů
• Sousedními uzly nazveme nazveme takovou dvojici uzlů, která je spojena hranou. Hrana ui , uj je pak incidentní s uzly ui a uj , pro i, j = 1, 2, . . . , n a i 6= j. • Multigraf je graf, ve kterém mezi některou dvojicí uzlů existuje více hran (obrázek 2). • Stupeň uzlu deg(ui ) definujeme jako počet hran, které do uzlu vstupují/vztupují1 . Platí: n P deg(ui ) = 2 · |E|, neboť každá hrana začíná/končí2 ve dvou uzlech. i=1
• Okolím uzlu ui nazveme množinu všech uzlů, do kterých vede z uzlu ui hrana. • Diskrétním grafem nazveme takový graf, který neobsahuje ani jednu hranu. Naopak úplným (komplexním) grafem bude nazýván takový graf, který obsahuje všechny možné hrany3 . Obrázek 3 zobrazuje čtyřuzlový diskrétní a kompletní graf. Obrázek 3: Čtyřuzlový diskrétní (vlevo – matice sousednosti (2)) a komplexní (vpravo – matice sousednosti (3)) graf 1
2
1
2
3
4
3
4
D4
K4
• Doplněk grafu G = (V, E) je graf (V, E 0 ), který obsahuje právě ty hrany, které neobsahuje graf původní. Například grafy D4 a K4 z obrázku 3 jsou si doplňkem. 1
Uvědomme si, že mluvíme o neorientovaném grafu. U neorientovaného grafu nelze rohodnout 3 Uvědomme si, že mluvíme o neorientovaném grafu, který není multigrafem! 2
1.1
Definice/vysvětlení základních pojmů
3
• Podgraf grafu G = (V, E) je graf takový G0 , který vznikne z toho původního vypuštěním některých uzlů nebo některých hran. Úplným podgrafem nazýváme takový podgraf, který má s ohledem na vypuštěné uzly všechny hrany, které měl graf původní, tj. nemá jen ty hrany, které by vedly k vypuštěným uzlům. • Sledem obvykle rozumíme posloupnost uzlů, kde pro uzel ui a uzel následující ui+1 existuje hrana. Někteří autoři sledu říkají procházka. • Sled končící ve stejném uzlu, ve kterém začal se nazývá cyklus, nebo také kružnice. Kružnice je tedy sled, ve kterém jsou všechny uzly pospojované – jakoby navlečené na niť. Dvě různé kružnice na šesti uzlech zobrazuje obrázek 4. Obrázek 4: Kružnice na šesti uzlech (vlevo – matice sousednosti (4) i vpravo – matice sousednosti (5)) 2
2
1
3
1
3
6
4
6
4
5
5
C6
C6
• Graf bez kružnice (cyklu) se nazývá acyklický. • Pokud se ve sledu žádný z uzlů neopakuje víckrát mluvíme o cestě. • Méně přísným požadavkem na graf než je předpoklad sledu je neexistence opakující se hrany. V tomto případě mluvíme o tahu. U tahu se tedy uzly opakovat mohou. • Pro vyjádření obyčejného grafu například pro softwareovou implementaci se nejčastěji používá tzv. matice sousednosti – obvykle značeno AG . Matice sousednosti (nebo také incidenční matice) je čtvercová matice, která má na pozici ij nulu pokud mezi i-tým a j-tým uzlem neexistuje hrana. Pokud mezi i-tým a j-tým uzlem hrana existuje je ij-tá pozice obsazena jedničkou. Matice sousednosti pro obyčejné grafy jsou přílohách a odkazované v popiscích obrázků jednotlivých grafů. Je zřejmé, že popis multigrafu by musel probíhat jinak. Vzhledem k tomu, že zatím byla řeč jen o neorientovaných grafech, musí být matice sousednosti symetrické podle hlavní diagonály.
4
1
NEORIENTOVANÝ GRAF
• Dalším možným vyjádřením důležitých vlastností grafů je matice dosažitelnosti (RG ) a matice vzdáleností 4 (DG ). Jedná se opět o čtvercové matice. Matice dosažitelnosti má na pozici ij nulu pokud mezi i-tým a j-tým uzlem neexistuje procházka. Pokud mezi i-tým a j-tým uzlem procházka existuje je ij-tá pozice obsazena jedničkou. Matice vzdáleností má na pozici ij nulu pokud mezi i-tým a j-tým uzlem neexistuje procházka. Pokud mezi i-tým a j-tým uzlem procházka existuje je ij-tá pozice obsazena počtem hran, který obsahuje nejkratší cesta. Zkuste vytvořit tyto matice jako cvičení. • Průměrem grafu je nejdelší vzdálenost kroků mezi libovolnými uzly. Průměr je nejvyšší hodnota v matici vzdáleností. • Excentricitou vrcholu ui označíme nejdelší z nejkratších cest, tj. nejvyšší číslo v i-tém řádku matice vzdáleností. • Uzel/uzly s nejnižší excentricitou se nazývají středem grafu. Excentricitu těchto uzlů navíc označujeme jako poloměr grafu. • Hamiltonovskou cestou nazveme takovou cestu, která prochází skrz všechny uzly. Končíli cesta ve stejném uzlu jako začala mluvíme o Hamiltonovské kružnici. Hamiltonovský graf je tedy graf obsahující alespoň jednu hamiltonovskou kružnici. • Graf, který lze nakreslit jedním tahem (žádná hrana se neopakuje), nazýváme eulerovským grafem. Obrázek 5: Eulerovský graf 2 7
6 3
1
4 2
8 4
3
1
5 5
• Souvislý graf je takový graf, pro který platí, že pro všechny dvojice jeho uzlů existuje alespoň jedna cesta, která je spojuje5 . • Kostrou grafu nazveme libovolný podgraf grafu původního, který obsahuje všechny uzly a který je stále souvislý. Tj. vypouštíme pouze některé hrany, ale tak, aby i po vypoštění zůstal graf souvislý. • (Souvislými) komponentami se nazývají takové maximální úplné podgrafy, které jsou souvislé (tj. přidáním/znovuvrácením dalšího uzlu původního grafu by se podgraf stal nesouvislým). 4 5
Matice vzdáleností je daleko zajímavější za předpokladu stranově ohodnoceného orientovaného grafu Matice dosažitelnosti obsahuje samé jedničky.
5 • Graf, který lze překreslit tak, aby se jeho hrany nekřížily se nazývá rovinným grafem. • Stromem je takový souvislý graf, který neobsahuje cyklus. Příkladem může být logický strom zobrazující jak může proběhnout tenisové utkání, které se hraje na dva vyhrané sety. Každý set může vyhrát hráč A nebo hráč B. A aby to nebylo tak jednoduché uvažme, že hráč A či hráč B může odstoupit, tj. utkání „skrečovatÿ. První set tedy může vyhrát hráč A nebo hráč B a utkání pokračuje, nebo vzdá hráč A či B a utkání končí. Po druhém setu utkání skončí jen v případě, že vyhrál stejný hráč jako v setu prvním, nebo opět někdo skrečuje. To se to komplikuje, že? Pojďme možné výsledky uspořádat do logického stromu, kde A bude znamenat vítězství hráče A v setu, AS skreč hráče A u hráče B obdobně. Spojnice mezi jednotlivými stavy nazýváme větve a stavy, které jsou konečné, pak listy. Listy na obrázku 6, které jsou červené, zobrazují výsledek, který skončil vítězstvím hráče A, modré pak symbolizují vítězství hráče B. Počet listů (16) je počtem všech možných výsledků tenisového zápasu. V polovině vyhrává samozřejmě hráč A v polovině hráč B. Obrázek 6: Logický strom výsledků tenisového zápasu S
A
A
A
B
BS
AS
AS
AS
BS
BS
B
BS
B
AS
A
A
BS
B
AS
B
Jak se situace změní pokud budeme uvažovat orientované hrany popisuje následující podkapitola.
2
Orientovaný graf
Definice 2 (Orientovaný graf). Graf (z pohledu teorie grafů) definujme jako dvojici G = (V, E), kde V = {u1 , u2 , . . . , un } je konečná množina objektů, kterým říkáme vrcholy, někdy též uzly grafu a E = {ui , uj , i, j = 1, 2, . . . , n} je množina některých uspořádaných dvojic uzlů, kterým říkáme orientované hrany grafu. Orientace hrany bývá v grafu zobrazena šipkou. Některé pojmy jsou shodné pro orientované i neorientované grafy. Některé pojmy naopak mají smysl jen pro jeden typ grafů. Následující definice se týkají výhradně orientovaných grafů. I u nich však nepředpokládme existenci cyklů a více souhlasně orientovaných hran.
6
2
ORIENTOVANÝ GRAF
Obrázek 7: Příklad orientovaného uzlového grafu – matice sousednosti (6) 2
4
1
6
3
2.1
5
Definice/vysvětlení základních pojmů
• Orientovaným sledem je obvykle rozuměna posloupnost uzlů kde pro uzel ui a uzel následující ui+1 existuje orientovaná hrana. • Pokud se v orientovaném sledu žádný z uzlů neopakuje víckrát mluvíme o orientované cestě. • Podobně se definuje orientovaný tah, Hamiltonovská cesta a Hamiltonovská kružnice v orientovaném grafu. • Síť je konečný souvislý, orientovaný, acyklický graf, v němž existuje jeden počáteční uzel (nevstupuje do něj žádná hrana) a jeden uzel koncový (žádná hrana z něj nevystupuje). Příkladem sítě je telefonní síť, rozvod plynu, kanalizace, atd. Příkladem může být na rozdíl od grafu na obrázku 7 graf na obrázku 8. Obrázek 8: Příklad sítě – matice sousednosti (7) 2
4
POČÁTEK
KONEC
1
6
3
5
Konkrétní použití grafů je součástí ostatních kapitol.
7
A
Matice sousednosti
A.1
Neorientované grafy
1. Matice sousednosti pro graf 1
0 1 1 0 0 0
0 0 0 1 1 0
1 0 1 1 1 0
1 1 0 0 1 0
0 1 0 0 0 1
0 1 1 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
(2)
1 0 1 1
1 1 0 1
1 1 1 0
(3)
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
1 0 0 0 1 0
1 0 0 0 1 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 1 0 0
(1)
2. Matice sousednosti pro graf 3 – vlevo
3. Matice sousednosti pro graf 3 – vpravo
0 1 1 1 4. Matice sousednosti pro graf 4 – vlevo
0 1 0 0 0 1
1 0 1 0 0 0
(4)
5. Matice sousednosti pro graf 4 – vpravo
0 0 1 0 0 1
0 0 0 1 1 0
(5)
8
A
A.2
MATICE SOUSEDNOSTI
Orientované grafy
1. Matice sousednosti pro graf 7
0 0 0 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
0 1 0 0 0 0
0 1 1 0 0 1
0 0 0 1 1 0
0 0 0 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
0 1 0 0 0 0
0 1 1 0 0 0
0 0 0 1 1 0
(6)
2. Matice sousednosti pro graf 8
(7)
