7   Pojem grafu, ve zkratce
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í 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.
Petr Hliněný, Fl MU Brno, 2013
1/20
Fl: IB000: Pojem grafu
7.1   Definice grafu
Definice 7.1. Graf (jednoduchý neorient.) je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů, c
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
^ = {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, 2013
2/20
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, 2013
3/20
Fl: IB000: Pojem grafu
Běžné typy grafů
Kružnice délky n má n > 3 vrcholů spojených do jednoho cyklu n hranami:
3
Cn
Cesta délky n > 0 ma' n + 1 vrcholů spojených za sebou n hranami:
12      3 4
n   n + 1
Petr Hliněný, Fl MU Brno, 2013
4/20
Fl: IB000: Pojem grafu
Úplný graf na n > 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem (™) hran): 3
K,
Úplný tripartitní graf na m > 1 a u > 1 vrcholech mámin vrcholů ve dvou skupinách (partitách), přičemž hranami jsou pospojované všechny m ■ n dvojice z různých skupin:
12    3 4
1    2 3
Petr Hliněný, Fl MU Brno, 2013
5/20
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, 2013
6/20
Fl: IB000: Pojem grafu
Zmínka o orientovaných grafech
V Lekci 9 si zavedeme také takzvané orientované grafy, které každé hraně přiřazují jistý směr. Formálně orientované grafy budou mít množinu orientovaných hran A C V (G) x V (G) a zobrazíme je takto...
Petr Hliněný, Fl MU Brno, 2013
7/20
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.
c
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, 2013
8/20
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 ~ H, pokud mezi nimi existuje isomorfismus.c
Fakt: Mějme isomorfismus / grafů G a H. Pak platí následující
* G a H mají stejný počet hran,
* / zobrazuje na sebe vrcholy stejných stupňů, tj. dc{v) = du{f{v)). c
U nakreslených dvou grafů objevíme isomorfismus velmi snadno - podíváme se, jak si odpovídají vrcholy stejných stupňů.
Petr Hliněný, Fl MU Brno, 2013
9/20
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, 2013
10/20
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, 2013
11/20
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, 2013
12/20
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
Lema 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í v y. 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
• Pro důkaz tranzitivity si označme P cestu z x do y a Q cestu z y do z. Pak P U Q nemusí být cesta; mohou se navzájem protínat. □ Avšak pokud označíme P' C P část cesty z x do prvního vrcholu v průniku s Q, tak P' U Q už je cesta z x do z.
□
Petr Hliněný,  Fl MU Brno, 2013
13/20
Fl: IB000: Pojem grafu
Definice 7.7. Komponentami souvislosti   grafu G nazveme třídy ekvivalence výše popsané (Lema 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, 2013
14/20
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.
Petr Hliněný,  Fl MU Brno, 2013
15/20
Fl: IB000: Pojem grálu
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, 2013
16/20
Fl: IB000: Pojem grafu
Vlastnosti stromů
Lema 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 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, 2013
17/20
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 Lematu 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, 2013
18/20
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 Lematu 7.10, 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, 2013
19/20
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, 2013
20/20
Fl: IB000: Pojem grafu