1   Pojem grafu
Grafy jsou jedním z nejdůležitějších pojmu diskrétní matematiky. Neformálně, graf se skládá z
• vrcholů neboli take uzlů (.puntíků")
• a hran (.spojnic") mezi dvojicemi vrcholu.
(Pozor, nepletme si graf s grafem funkce!)
Takový graf muze vyjadřovat souvislosti mezi objekty, návaznosti, spojení nebo toky, atd. Sve dulezite místo v informatice si grafy získaly dobre vyvízenou kombinací svych vlastností -snadním názorným nakreslením a zíroven jednoduchou zpracovatelností na pocítacích.
Stručný přehled lekce
• Zaveden í a pochopen í grafů, jejich zakladn í pojmy.
• Pr íklady beZnych tř íd grafů.
• Stůpne vrcholů v grafech.
• Podgrafy, isomorfismus grafů a jeho poznan í.
Petr Hliněný,  FI MU Brno
-I: MA010: Pojem grafu
1.1   Dennice grafu
Definice 1.1. Graf (rozšířeně obyčejný ci jednoduchý neorientovaný graf)
je uspořádaná dvojice G = (V, E), kde V je mnoZina vrcholU a E je mnoZina hran -
mnoZina vybraných dvouprvkových podmnoZin mnoZiny vrchol U.
ZnaCení: Hranu meZi vrcholy u a v píšeme jako {u, v}, nebo Zkracene uv. Vrcholy spojene hranou jsou sousední.
Na mnoZinu vrcholu grafu G odkaZujeme jako na V (G), na mnoZinu hran E (G). c
Fakt: Na graf se lZe dívat take jako na symetrickou ireflexivní relaci, kde hrany tvorí prave dvojice prvku z teto relace. c
Poznámka: Grafy se často zadávají přímo názorným obrázkem, jinak je lze take zadat výčtem vrcholů a výčtem hran. Například:
V = (1, 2, 3, 4},    E =   (1, 2}, (1, 3}, (1,4}, {3,4}
1
2
3
4
V
Petr Hliněný,  FI MU Brno
I: MA010: Pojem grafu
Běžné typy grafů
Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Krůžnicě délky n ma n > 3 vrcholů spojenych do jednoho cyklů n hranami:
4
3
Cěsta délky n ma n + 1 vrcholů spojenych za seboů n hranami:
12      3 4
n n+1
Petr Hliněný,  FI MU Brno
-I: MA010: Pojem grafu
2
5
1
6
7
_
n
Úplný graf na n > 1 vrcholech má n vrcholu, všechny navzájem pospojované (tj. celkem (™) hran):
2
Úplný bipartitní graf na m > 1 a n > 1 vrcholech má m + n vrcholů ve dvou skupinách (partitách), přicemZ hranami jsou pospojovane všechny m • n dvojice z různých skupin:
Petr Hliněný,  FI MU Brno
I: MA010: Pojem grafu
3
1
n
m
n
1.2   Stupně vrcholů v grafu Definice 1.2. Stupněm vrcholu v v grafu G
rozumíme pocet hran vycházejících z v. Stupeň v v grafu G značíme dG(v).
Slovo „vycházející" zde nenaznačuje žádný smer; je totiz obecnou konvencí říkat, ze hrana vychází z obou svých koncu zaroveň.
2
2
3
> 3
2
2
3 A-'	i 3
	(5
> 3
Například v nakreslene ukazce jsou stupne přímo zapsaný u vrcholu.c
Definice: Graf je d-regulárni, pokud všechny jeho vrcholy mají stejny stupen d.
ZnaCení: Nejvyššístupen v grafu G znacíme A(G) a nejnižšíS(G).
Věta 1.3. Součet stupnU v grafu je vždy sudy, roven dvojnásobku počtu hran. c
Důkaz. Pňi scítaní stupnu vrcholu v grafu zapocítame kazdou hranu dvakrát - jednou za kazdy její konec. Proto výsledek vyjde sudy. □
Petr Hliněný,  FI MU Brno
-I: MA010: Pojem grafu
Vlastnosti stupňů
Jelikož v obyčejném grafu zvlášť nerozlisujeme mezi jednotlivými vrcholy, nemáme dáno žádné pořadí, ve kterem bychom stupne vrcholU meli psát. Proto si stupne obvykle seřazujeme podle velikosti.
íjc   Zajímavou otázkou je, ktere posloupnosti stupnu odpovídají vrcholum skutečnych grafu?
(Napríklad posloupnost stupnu 1, 2, 3,4, 5, 6, 7 nemuze nastat nikdy.)
Věta 1.4. Necht dl < d2 < • • • < dn je posloupnost přirozených čísel. Pak existuje graf s n vrcholy stupnU
dl, d2,. .., dn právě tehdý, kdýZ existuje graf s n — 1 vrcholy stupnU
dl,  d2, . . . ,  dn-dn-l,    dn-dn — 1, . . . ,  dn-2 — 1,  d„_i — 1 .
K použití Vety 1.4: Mírně nepřehledný formální zápis vety znamená, ze ze seřazené posloupnosti odebereme poslední (nejvetsí) stupeň dn a od tolika dn bezprostredne předchozích stupňů odečteme jedniCky. Zbyle stupne na zaCatku posloupnosti se nezmení. (Nezapomenme, ze posloupnost je treba znovu seradit dle velikosti.)
Petr Hliněný,  FI MU Brno
I: MA010: Pojem grafu
Příklad 1.5. Existuje graf se stupni vrcholu:
(1,1,1, 2, 3,4) ?
Dle Vety 1.4 upravíme na (1, 0, 0,1, 2), uspořádáme ji (0,0,1,1, 2),
pak znovu (0,0, 0,0) a takovy graf už jasne existuje. Na druhou stranu, jak takovy graf sestrojíme? c
(Obvykle není jediny, ale nas zajíma aspon jeden z nich.) Proste obratíme předchozí postup, zaCneme z grafu se 4 vrcholy bez hran, pridame vrchol stupne 2 spojeny se dvema z nich a dalsí vrchol stupne 4 takto:
(1,1,1,1, 2, 3, 4, 6, 7) ? c
Podobne upravíme na (1, 0,0,0,1, 2, 3, 5) a usporadame ji (0, 0,0,1,1, 2, 3, 5), pak znovu (0,0, —1, 0,0,1, 2), ale to uz přece nelze - stupne nejsou zaporne.
•
4
Proto takovy graf neexistuje.
□
V
Petr Hliněný,  FI MU Brno
I: MA010: Pojem grafu
1.3   Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholu V (H) C V (G), který mí za hraný libovolnou podmnožinu hran grafu G majících oba vrcholy ve V (H).
Píšeme H C G, tj. stejne jako množinova inkluze (ale význam je trochu jiný). c
Na následujícím obrázku vidíme zvýrazněné podmnožiny vrcholu hran. ProC se vlevo nejedná o podgraf? Vpravo už podgrafem je.
Definice: Indukovaným podgrafem je podgraf H C G takový, který obsahuje všechný hraný grafu G mezi dvojicemi vrcholu z V (H).
c
v
Petr Hliněný,  FI MU Brno
I: MA010: Pojem grafu
Definice 1.6. Isomorfismus grafů G a H
je bijektivní (vzájemně jednoznacne) zobrazená f : V (G) — V (H), pro ktere platí, Ze kaZda dvojice vrcholů u, v G V(G) je spojena hranou v G prave tehdy, kdyz je dvojice f (u), f (v) spojena hranou v H.
Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus. Píseme G ~ H. c
Fakt: Isomorfní grafy mají stejny pocet vrcholu (i hran).
Z nakreslených tří grafů jsou prvn í dva isomorfn í - jsou to jen různá nakreslen í téhož grafu, kružnice delký 5. (UrCite snadno najdete isomorfismus mezi nimi. Pro jednoduchost isomorfismus zakreslete do obrazku tak, že vrcholy prvn ího oC íslujete C íslý 1 až 5 a vrcholy druheho stejnými c íslý v porad í odpovídaj íc ím jeho bijekci.) Tret í graf jim isomorfn í nen í, nebol;, napríklad, ma vrcholý jiných stupňu. c
Fakt: Pokud je bijekce f isomorfismem, musí zobrazovat na sebe vrcholy stejnych stupnu, tj. d g (v) = dH (f (v)). Naopak to vsak nestačí!
Petr Hliněný,  FI MU Brno_9_FI: MA010: Pojem grafu
Příklad 1.7. Jsou následující dva grafy isomorfní?
Pokud mezi nakreslenými dvema grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný pocet vrcholU a hran. nMají. Pak se podívame na stupne vrcholU a zjistíme, ze oba mají stejnou posloupnost stupnU 2, 2, 2, 2, 3, 3. TakZe ani takto jsme mezi nimi nerozlisili a mohou (nemusejí!) být isomorfní. Dale tedy nezbýva, nez zkouset vsechny přípustne moznosti zobrazení isomorfismu z leveho grafu do praveho. c
Na levem grafu si pro ulehcení vsimneme, ze oba vrcholy stupne tri jsou si symetricke, proto si bez ujmy na obecnosti muzeme vybrat, ze vrchol oznaceny 1 se zobrazí na 1'. Druhy vrchol stupne tri, oznaceny 4, se musí zobrazit na analogicky vrchol druheho grafu 4'. A zbytek j i z plyne snadno:
1
3'
4'
V
□
Petr Hliněný,  FI MU Brr
I: MA010: Pojem grafu
Věta 1.8. Relace „být isomorfní" ~ na třídě všech grafů je ekvivalencí, c
Důkaz. Relace ~ je reflexivn í, protože graf je isomorfn í sam sobe identickým zobrazen ím. Relace je take sýmetricka, nebol: bijektivn í zobrazen í lze jednoznacne obratit. Tranzitivnost ~ se snadno dokaze skiadan ím zobrazen í-isomorfismů. □
Dusledkem je, ze vsechny grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud mluvíme o grafu, mysl íme t ím obvykle jeho celou trídu isomorfismu, tj. nezalezí nam na konkretn í prezentaci grafu.
Petr Hliněný,  FI MU Brr
I: MA010: Pojem grafu
Další grafové pojmy
Značení: Mejme libovolný graf G.
• Podgrafu H C G, ktery je isomorfní nejake kruznici, ríkame kružnice v G.
• Specialne ríkame trojúhelník kruznici delky 3. c
• Podgrafu H C G, ktery je isomorfní nejake ceste, ríkame cesta v G. c
• Podgrafu H C G, ktery je isomorfní nejakemu uplnemu grafu, říkame klika v G.
• Podmnozine vrcholu X C V (G), mezi kterymi nevedou v G vubec zadne hrany, říkame nezávislá množina X v G. c
• Indukovanemu podgrafu H C G, ktery je isomorfní nejake kruznici, říkáme indukovanú kružnice v G.
V
Petr Hliněný,  FI MU Brn
I: MA010: Pojem grafu
6
5
6
5
1 «
• 4
1 ^
• 4
Prvn í z ukázaných grafu například neobsahuje žádný trojuheln ík, ale obsahuje kružnici delky 4, dokonce indukovanou. Druhý graf trojuheln ík obsahuje a kružnici deiký 4 taktez. Prvn í graf obsahuje cestu delky 4 na vrcholech 1, 2, 3, 4, 5, ale ta nen í induko-vana. Indukovana cesta delky 4 v nem je třeba 2, 3,4, 5, 6. Druhý graf tyto cesty take obsahuje, ale naopak žadna z nich nen í indukovana.
Prvn í graf ma nejvets í kliku velikosti 2 - jedinou hranu, kdezto druhý graf ma vets í kliku na vrcholech 3,4, 5. Nejvets ínezavisla mnozina u obou grafu ma 3 vrcholy 2, 4, 6.
V
Petr Hliněný,  FI MU Brr
-I: MA010: Pojem grafu
Příklad 1.9. Jsou následující dva grafy isomorfní?
□
Postupovat budeme jako v Príklade 1.7, nejprve oveříme, Ze oba grafy mají stejne mnoho vrcholu i stejnou posloupnost stupnu 2, 2, 2, 2, 3, 3. Pokud se vsak budeme snaZit najít meZi nimi isomorfismus, neco stále nebude sedet, Ze? Co nám tedy v naleZení isomorfismu braní? Podívejme se, Ze v druhem grafu oba vrcholy stupne tři mají sveho spolecneho souseda, tvoří s ním trojuhelník. V prvním grafu tomu tak není, první graf dokonce nema Zadny trojuheln ík. Proto Zadane dva grafy nejsou isomorfn í. □ □
Poznamka: VýSe ůvedene príklady nam ůkazůj í nektere cesty, jak poznat (tj. naj ít nebo vyloučit) isomorfismus dvoů grafů. Ty vSak ne vzdy můsí fungovat. Čtenar se můze ptat, kde tedy najde nejaky ůniverzaln í postůp pro nalezen í isomorfismů? □
Bohůzel vas můs íme zklamat, zadny rozůmny ůniverzaln í postůp nen í znam a zat ím plat í, ze jedina vzdy fůngůj íc í cesta pro nalezen íči nenalezen í isomorfismů mezi dvema grafy je ve stylů vyzkoušejte všechny možnosti bijekc í mezi vrcholy techto grafů. (Tech je, jak znamo, az n!)
Petr Hliněný,  FI MU Brno_14_FI: MA010: Pojem grafu
1.4   Orientované gřafy a multigřafy
V nekterych případech (například u toku v sítích) potřebujeme u kazde hrany vyjadrit její smer. To vede na definici orientovaného grafu, ve kterem hrany jsou usporadane dvojice vrcholu. (V obrazcích kreslíme orientovane hrany se sipkami.)
Definice: Orientovaný graf je uspořadana dvojice D = (V, E), kde E C V x V.
Fakt: Orientovane grafy odpovídají relacím, ktere nemusí byt symetricke.
ZnaCení: Hrana (u,v) v orientovanem grafu D začína ve vrcholu u a konči ve (míří do) vrcholu v. Opacna hrana (v,u) je mzna od (u,v) !
Petr Hliněný,  FI MU Brr
I: MA010: Pojem grafu
Navíc nekdý muzeme mluvit o tzv. multigrafech, ve kterých padají temeř všechna omezení na hraný. ..
V multigrafu rrmze mezi dvojicí vrcholu vest libovolný počet hran - tzv. násobné hrany, a nektere z nich mohou být i orientovane.
Take jsou povolený hraný, ktere mají oba konce totozne - tzv. smycky.
Definice: Multigraf je uspořadana trojice M = (V, E, e), kde V n E = 0 a e : E — ("22) U V U (V x V) je incidencní zobrazení hran.
ZnaCen í ("22) v definici reprezentuje neorientovane hrany, V neorientovane smyCky a V x V orientovane hrany a smyCky. SmyCky a paraleln í hrany lehce ilustruje nasleduj íc í obrazek:
V
Petr Hliněný,  FI MU Brr
I: MA010: Pojem grafu
1.5   Implementace grafu
Mejme jednoduchy graf G na n vrcholech a znacme vrcholy jednoduse císly V(G) = {0, l,...,n — 1}. Pro pocítacovou implementaci grafu G se nabízejí dva zakladní zpusoby:
• Maticísousednosti, tj. dvourozmernym polem g[] [], ve kterem g[i] [j]=1 zna-mena hranu mezi vrcholy i a j.
• Výčtem sousedU, tj. pouzitím opet dvourozmerne pole h[][] a navíc pole d[] stupnu vrcholu. Zde prvky h[i] [0] ,h[i] [1] ,h[i] [d[i]-1] udavají seznam sousedu vrcholu i.
Poznamka: Davejte si pozor na sýmetrii hran v implementaci!
Implementace matic í sousednosti je hezka svou jednoduchost í.
Druha moznost se vsak mnohem lepe hod í pro grafý s malým poctem hran, coz nastava ve vetsine praktických aplikac í.
(Navíc je implementace výctem sousedu vhodna i pro multigrafý.)
Ke grafum lze do zvlastn ích pol í pridat take ohodnocení vrcholů a hran libovolnými c íslý ci znaňckami. . .
Petr Hlinený,  FI MU Brr
I: MA010: Pojem grafu