r
7   Pojem grafu
Třebaže grafy jsou jen jednou z mnoha struktur v matematice a vlastně pouze speciálním případem binárních relací, vydobyly si svou užitečností a názorností (a to především ve vztahu k informatice) důležité místo na slunci.
Neformálně řečeno, graf se skládá z vrcholů (představme si je jako nakreslené „puntíky") a z hran, které spojují dvojice vrcholů mezi sebou.
Stručný přehled lekce
* Zavedení a pochopení grafů, jejich základní pojmy.
* Příklady běžných tříd grafů, podgrafy a isomorfismus, souvislost.
* Stromy a jejich speciální vlastnosti.
c
Petr Hliněný, Fl MU Brno, 2015
1/22
Fl: IB000: Pojem grafu
7.1   Definice grafu
Definice 7.1. Graf (jednoduchý neorient.) je uspořádaná dvojice G = (V, E), kde V }e konečná množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů.
1
2 3 4
Značení: Hranu mezi vrcholy u a v píšeme jako {u, v}, nebo zkráceně uv.
Vrcholy spojené hranou jsou sousední a hrana uv vychází z vrcholů u a v.
Na množinu vrcholů grafu G odkazujeme jako na V(G), na množinu hran E{G).
Grafy se často zadávají přímo názorným obrázkem, jinak je lze formálně zadat výčtem vrcholů a výčtem hran. Například:
^ = {1,2,3,4},   E= {{1,2}, {1,3}, {1,4}, {3,4}}
Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace.
Petr Hliněný, Fl MU Brno, 2015
2/22
Fl: IB000: Pojem grafu
Stupně vrcholů v grafu
Definice 7.2. Stupněm vrcholu v v grafu G
rozumíme počet hran vycházejících z v. Stupeň v v grafu G značíme dc(v). c
Slovo „vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí u neorientovaných grafů říkat, že hrana vychází z obou svých konců zároveň.
Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň d.n
Značení: A/e/Vyšš/'stupeň v grafu G značíme A(G) a nejnižšíô(G). c
Věta 7.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran.
Petr Hliněný, Fl MU Brno, 2015
3/22
Fl: IB000: Pojem grafu
r
Běžné typy grafů
Kružnice délky n má n > 3 různých vrcholu spojených „do jednoho cyklu1 n hranami:
C r,
Cesta délky n > 0 ma' n+1 různých vrcholů spojených „za sebou" n hranami:
12      3 4
n   n + 1
Petr Hliněný, Fl MU Brno, 2015
4/22
Fl: IB000: Pojem grafu
r
Úplný graf na n > 1 vrcholech má n různých vrcholu spojených po všech dvojicích (tj. celkem (™) hran): ^
Kr.
Úplný bipartitní graf na m > 1 a ti > 1 vrcholech má m + n vrcholu ve dvou skupinách (partitách), přičemž hranami jsou spojeny všechny m • n dvojice z různých skupin:
12    3 4
K r,
Petr Hliněný, Fl MU Brno, 2015
5/22
Fl: IB000: Pojem grafu
Hvězda s n > 1 rameny je zvláštní název pro úplný bipartitní graf K\.
Petr Hliněný, Fl MU Brno, 2015
6/22
Fl: IB000: Pojem grafu
r
Zmínka o zobecněných grafech
Všimněme si, že v definici grafu (Def. 7.1) vůbec neuvažujeme možnosti vícenásobných hran (mezi stejnou dvojicí vrcholů) a tzv. „smyček" (hrana se stejným jedním koncem)—takovému zobecnění by se říkalo multigraf; ani zatím nepřisuzujeme hranám žádný směr.
V Lekci 9 si však ještě zavedeme orientované grafy, které každé hraně přiřazují jistý směr. Orientované grafy budou mít množinu orientovaných hran A C V (G) x V (G) a zobrazíme je třeba takto.. .
c
Petr Hliněný, Fl MU Brno, 2015
7/22
Fl: IB000: Pojem grafu
7.2   Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholu V (H) C V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V (H).
Píšeme H C G, tj. stejně jako množinová inkluze (ale význam je trochu jiný).c
Na následujícím obrázku vidíme zvýrazněné podmnožiny vrcholu hran. Proč se vlevo nejedná o podgraf? Obrázek vpravo už podgrafem je.
Definice: Indukovaným podgrafem je podgraf H C G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H).
Petr Hliněný, Fl MU Brno, 2015
8/22
Fl: IB000: Pojem grafu
„Stejnost" grafů
Definice 7.4. Isomorfismus ~ grafů G a, H
je bijektivní zobrazení / : V(G) —> V(H), pro které každá dvojice u, v G V (G) je spojená hranou v G právě, když je dvojice f(u),f(v) spojená hranou v H.
Grafy G a H jsou isomorfní, G ~ fř, pokud mezi nimi existuje isomorfismus.
Petr Hliněný, Fl MU Brno, 2015
9/22
Fl: IB000: Pojem grafu
Fakt: Mějme isomorfismus / grafů G a H. Pak platí následující
* G a H mají stejný počet hran, c
* / zobrazuje na sebe vrcholy stejných stupňů, tj. dc{v) = du{f{v)). c
U výše zakreslených dvou grafů objevíme isomorfismus velmi snadno - podíváme se, jak si odpovídají vrcholy stejných stupňů, c
Naopak v této trojici grafů (se stejnými počty vrcholů i hran) žádné dva nejsou isomorfní. Proč? Ten vlevo má vrchol stupně 4, čímž se od obou zbylých liší. Prostřední graf pak má jediné dva vrcholy stupně 2 spojené hranou, kdežto v pravém takové dva vrcholy spojené nejsou (isomorfismus by je však i s hranou musel zachovat).
Petr Hliněný,  Fl MU Brno, 2015
10/22
Fl: IB000: Pojem grafu
Příklad 7.5. Jsou následující dva grafy isomorfní?
Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. □ Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého.
Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické, proto si bez újmy na obecnosti můžeme vybrat, že vrchol označený 1 se zobrazí na 1'. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu 4'. A zbytek již plyne snadno:
Z
Petr Hliněný,  Fl MU Brno, 2015
11/22
Fl: IB000: Pojem grafu
Důsledek: Stejnost grafů jako isomorfismus!
Celá
Graf G       <_> třída isomorfismu
grafu G
Je uvedený přístup, tj. zaměňování konkrétního grafu za celou jeho třídu isomorfismu, v matematice neobvyklý? nNe, například už v geometrii jste říkali „čtverec o straně 2" či „jednotkový kruh" a podobně, aniž jste měli na mysli konkrétní obrázek, nýbrž celou třídu všech těchto shodných objektů.
Petr Hliněný,  Fl MU Brno, 2015
12/22
Fl: IB000: Pojem grafu
Další grafové pojmy
Definice: Mějme libovolný graf G. c
* Podgrafu H CG, který je isomorfní nějaké kružnici, říkáme kružnice vG.
* Speciálně říkáme trojúhelník kružnici délky 3. c
* Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta v G. c
* Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika v G.
* Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G. c
* Indukovanému podgrafu H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G.
Petr Hliněný,  Fl MU Brno, 2015
13/22
Fl: IB000: Pojem grafu
7.3   Souvislost grafů, komponenty
Důležitou globální vlastností grafů je souvislost, tedy možnost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu, c
Tvrzení 7.6. Mějme relaci ~ na množině vrcholů V{G) libovolného grafu G takovou, že pro dva vrcholy x ~ y právě když existuje v G cesta začínající v x a končící vy. Pak ~ je relací ekvivalence, c
Důkaz.
• Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou cestou délky 0. c
• Symetrická je také, protože cestu z x do y snadno v neorientovaném grafu obrátíme na cestu z y do x. c
• Důkaz tranzitivity však není takto triviální— pokud vezmeme cestu z x do y a cestu z y do z, tak se tyto dvě cesty mohou protínat i jinde než v y a nelze je prostě „navázat" na sebe.
Petr Hliněný,  Fl MU Brno, 2015
14/22
Fl: IB000: Pojem grafu
• Zmíněný problém vidíme například zde:
Pro důkaz tranzitivity si označme P cestu z x do y a Q cestu z y do z. Pokud označíme P' C P tu část první cesty z x do prvního vrcholu p v průniku s Q (tj. p G V(-P) fl V(Q)) a označíme Q' Q Q zbytek druhé cesty od p do z, tak P' U Q' vždy je cestou z x do z.
□
Petr Hliněný,  Fl MU Brno, 2015
15/22
Fl: IB000: Pojem grafu
r
Definice 7.7. Komponentami souvislosti grafu G nazveme třídy ekvivalence výše popsané (Tvrz. 7.6) relace ~ na V(G). c
Jinak se také komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence, c
Podívejte se, kolik komponent souvislosti má tento graf:
Vidíte v obrázku všechny tři komponenty? Jedna z nich je izolovaným vrcholem, druhá hranou (tj. grafem isomorfním K2) a třetí je to zbývající.
Petr Hliněný,  Fl MU Brno, 2015
16/22
Fl: IB000: Pojem grafu
Definice 7.8. Graf G je souvislý pokud je G tvořený nejvýše jednou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou, c
Který z těchto dvou grafů je souvislý?
Petr Hliněný,  Fl MU Brno, 2015
17/22
Fl: IB000: Pojem grafu
7.4   Stromy - grafy bez kružnic
Charakteristickými znaky stromu je absence kružnic a souvislost.. . c
Definice 7.9. Strom je jednoduchý souvislý graf T bez kružnic.
c
Les je jednoduchý graf bez kružnic (nemusí být souvislý). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a prázdný graf jsou také stromy.
Grafy bez kružnic také obecně nazýváme acyklické.
Petr Hliněný,  Fl MU Brno, 2015
18/22
Fl: IB000: Pojem grafu
Vlastnosti stromů
Tvrzení 7.10. Strom s více než jedním vrcholem obsahuje vrchol stupně 1. c
Důkaz: Souvislý graf s více než jedním vrcholem nemůže mít vrchol stupně 0. Proto vezmeme libovolný strom Tav něm libovolný vrchol v. □Sestrojíme nyní co nejdelší cestu S v T začínající ve v:
* S začne libovolnou hranou vycházející z v; c
* v každém dalším vrcholu u, do kterého se dostaneme a má stupeň větší než 1, lze pak pokračovat cestu S další novou hranou.
S
Pokud by se v S poprvé zopakoval některý vrchol, získali bychom kružnici. Proto cesta S musí jednou skončit v nějakém vrcholu stupně 1 v T. □
Petr Hliněný,  Fl MU Brno, 2015
19/22
Fl: IB000: Pojem grafu
Věta 7.11. Strom na n vrcholech má přesně n — 1 hran pro n > 1. □
Důkaz: Toto tvrzení dokážeme indukcí podle n. * Strom s jedním vrcholem má n — 1 = 0 hran. c
* Nechť T je strom na n > 1 vrcholech.
Podle Tvrzení 7.10 má T vrchol v stupně 1. Označme T" = T — v graf vzniklý z T odebráním vrcholu v. Pak T" je také souvislý bez kružnic, tudíž strom na n — 1 vrcholech. Dle indukčního předpokladu T" má n — 1 — 1 hran, a proto T má n — 1 — 1 + 1 = n — 1 hran. a
Petr Hliněný,  Fl MU Brno, 2015
20/22
Fl: IB000: Pojem grafu
Věta 7.12. Mezi každými dvěma vrcholy stromu vede právě jediná cesta. □
u ®---
Důkaz: Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u,v vede nějaká cesta, c
Pokud by existovaly dvě různé cesty P±,P2 mezi u, v, tak bychom vzali jejich symetrický rozdíl, podgraf H = P1AP2 s neprázdnou množinou hran, kde H zřejmě má všechny stupně sudé. Na druhou stranu se však podgraf stromu musí opět skládat z komponent stromů, a tudíž obsahovat vrchol stupně 1 podle Tvrzení 7.10, což je spor. 1 □
Důsledek 7.13. Přidáním jedné hrany do stromu vznikne právě jedna kružnice.
Petr Hliněný,  Fl MU Brno, 2015
21/22
Fl: IB000: Pojem grafu
Alternativní charakterizace stromů
Na dané množině vrcholů je (vzhledem k inkluzi množin hran) strom
• minimální souvislý graf (plyne z Věty 7.12)
• a zároveň maximální acyklický graf (plyne z Důsledku 7.13).
Petr Hliněný,  Fl MU Brno, 2015
22/22
Fl: IB000: Pojem grafu