4 Pojem grafu, ve zkratce

4

Pojem grafu, ve zkratce

Tˇrebaˇze grafy jsou jen jednou z mnoha struktur v matematice a vlastnˇe pouze speciáln´ım pˇr´ıpadem binárn´ıch relac´ı, vydobyly si svou uˇziteˇcnost´ı a názornost´ı d˚ uleˇzité m´ısto na slunci. Neformálnˇe ˇreˇceno, graf se skládá z vrchol˚ u (pˇredstavme si je jako nakreslené punt´ıky“) ” a z hran, které spojuj´ı dvojice vrchol˚ u mezi sebou. s s s s A """ S S A "" S A Ss " s" A s s bb A "" S " b A" S bb" A S Ss s""bbAs s

Petr Hlinˇ en´ y, FI MU Brno, 2014

1 / 24

FI: IB000: Pojem grafu

4

Pojem grafu, ve zkratce

Tˇrebaˇze grafy jsou jen jednou z mnoha struktur v matematice a vlastnˇe pouze speciáln´ım pˇr´ıpadem binárn´ıch relac´ı, vydobyly si svou uˇziteˇcnost´ı a názornost´ı d˚ uleˇzité m´ısto na slunci. Neformálnˇe ˇreˇceno, graf se skládá z vrchol˚ u (pˇredstavme si je jako nakreslené punt´ıky“) ” a z hran, které spojuj´ı dvojice vrchol˚ u mezi sebou. s s s s A """ S S A "" S A Ss " s" A s s bb A "" S " b A" S bb" A S Ss s""bbAs s

Struˇ cn´ y pˇrehled lekce * Zaveden´ı a pochopen´ı graf˚ u, jejich základn´ı pojmy. * Pˇr´ıklady bˇeˇzných tˇr´ıd graf˚ u, podgrafy a isomorfismus, souvislost. * Stromy a jejich speciáln´ı vlastnosti. Petr Hlinˇ en´ y, FI MU Brno, 2014

1 / 24


4.1

Definice grafu

Definice 4.1. Graf (jednoduchý neorient.) je uspoˇrádaná dvojice G = (V, E), kde V je mnoˇzina vrchol˚ u a E je mnoˇzina hran – mnoˇzina vybraných dvouprvkových podmnoˇzin mnoˇziny vrchol˚ u. s HHH HH Hs s s

1

2


3

4

2 / 24


4.1

Definice grafu


1

2

3

4

Znaˇ cen´ı: Hranu mezi vrcholy u a v p´ıˇseme jako {u, v}, nebo zkrácenˇe uv. Vrcholy spojené hranou jsou sousedn´ı a hrana uv vycház´ı z vrchol˚ u u a v. Na mnoˇzinu vrchol˚ u grafu G odkazujeme jako na V (G), na mnoˇzinu hran E(G).


2 / 24


4.1

Definice grafu


1

2

3

4

Znaˇ cen´ı: Hranu mezi vrcholy u a v p´ıˇseme jako {u, v}, nebo zkrácenˇe uv. Vrcholy spojené hranou jsou sousedn´ı a hrana uv vycház´ı z vrchol˚ u u a v. Na mnoˇzinu vrchol˚ u grafu G odkazujeme jako na V (G), na mnoˇzinu hran E(G). Grafy se ˇcasto zadávaj´ı pˇr´ımo názorným obrázkem, jinak je lze formálnˇe zadat výˇctem vrchol˚ u a výˇctem hran. Napˇr´ıklad: n o V = {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ˇr´ı právˇe dvojice prvk˚ u z této relace. Petr Hlinˇ en´ y, FI MU Brno, 2014

2 / 24


Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vycházej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v).


3 / 24


Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vycházej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v). Slovo vycházej´ıc´ı“ zde nenaznaˇcuje ˇzádný smˇer; je totiˇz obecnou konvenc´ı u neorien” tovaných graf˚ u ˇr´ıkat, ˇze hrana vycház´ı z obou svých konc˚ u zároveˇ n. 2 s s 3 S S S 2Ss

s2 S S S Ss 3 s2


stupnˇe

3 / 24

s3 3 s A S A S S A Ss 3 s A 4 b Sbb A S bb A A S b 2Ss bAs5



s2 S S S Ss 3 s2

stupnˇe


Definice: Graf je d-regulárn´ı, pokud vˇsechny jeho vrcholy maj´ı stejný stupeˇ n d.


3 / 24



s2 S S S Ss 3 s2

stupnˇe


Definice: Graf je d-regulárn´ı, pokud vˇsechny jeho vrcholy maj´ı stejný stupeˇ n d. Znaˇ cen´ı: Nejvyˇsˇs´ı stupeˇ n v grafu G znaˇc´ıme ∆(G) a nejniˇzˇs´ı δ(G).


3 / 24



s2 S S S Ss 3 s2

stupnˇe


Definice: Graf je d-regulárn´ı, pokud vˇsechny jeho vrcholy maj´ı stejný stupeˇ n d. Znaˇ cen´ı: Nejvyˇsˇs´ı stupeˇ n v grafu G znaˇc´ıme ∆(G) a nejniˇzˇs´ı δ(G). Vˇ eta 4.3. Souˇcet stupˇ n˚ u v grafu je vˇzdy sudý, roven dvojnásobku poˇctu hran. Petr Hlinˇ en´ y, FI MU Brno, 2014

3 / 24


Bˇ eˇ zn´ e typy graf˚ u Kruˇ znice d´ elky n má n ≥ 3 r˚ uzných vrchol˚ u spojených do jednoho cyklu“ ” n hranami: s PPPPs 4 s 2 B B B s Bs 1 5 B B B s n 6 Bs

3

Cn

...


4 / 24


Bˇ eˇ zn´ e typy graf˚ u Kruˇ znice d´ elky n má n ≥ 3 r˚ uzných vrchol˚ u spojených do jednoho cyklu“ ” n hranami: s PPPPs 4 s 2 B B B s Bs 1 5 B B B s n 6 Bs

3

Cn

...

Cesta d´ elky n ≥ 0 má n+1 r˚ uzných vrchol˚ u spojených za sebou“ n hranami: ”

Pn


s

1

s

2

s

3

4 / 24

s

4

...

s

n

s

n+1


´ y graf na n ≥ 1 vrcholech má n r˚ Upln´ uzných vrchol˚ u spojených po vˇsech n dvojic´ıch (tj. celkem 2 hran): 3 sP

Kn

s @ L PPP 4 a !s 2 L@ !! B @aaa ! L a ! @ @ !aa La @B !!!! L aa B @ s ! @Bs L a @ 5 aa L !! 1 B a aa @!!! B a !@ LL a aa @ B !!!! L a@ s aLs n 6 B!

...


5 / 24


´ y graf na n ≥ 1 vrcholech má n r˚ Upln´ uzných vrchol˚ u spojených po vˇsech n dvojic´ıch (tj. celkem 2 hran): 3 sP

Kn

s @ L PPP 4 a !s 2 L@ !! B @aaa ! L a ! @ @ !aa La @B !!!! L aa B @ s ! @Bs L a @ 5 aa L !! 1 B a aa @!!! B a !@ LL a aa @ B !!!! L a@ s aLs n 6 B!

...

´ y bipartitn´ı graf na m ≥ 1 a n ≥ 1 vrcholech má m + n vrchol˚ Upln´ u ve dvou skupinách (partitách), pˇriˇcemˇz hranami jsou spojeny vˇsechny m · n dvojice z r˚ uzných skupin: s s s s s Q , e A AE lEe %A % E Q l , Q E Ae Q E A l E % e A ,% A,% A l El e E Ae E Q % , E A eE AQ Q E l e A% % , E %A EQQ , E A e le%A leA A, E, Q % E A%E e leA E % A E e ,A E % QQ l l s eAEs% Q eAs E% s AE,

1

Km,n

2

10


3

20

5 / 24

4

30

...

...

m

n0


Hvˇ ezda s n ≥ 1 rameny je zvláˇstn´ı název pro u ´plný bipartitn´ı graf K1,n :

Sn


4 s

s

3

s2 @ @ @ @s s s1 5 @ @ @ 6 s . . . @s n

6 / 24


Zm´ınka o orientovan´ ych grafech V Lekci 9 si zavedeme také takzvané orientované grafy, které kaˇzdé hranˇe pˇriˇrazuj´ı jistý smˇer. Formálnˇe orientované grafy budou m´ıt mnoˇzinu orientovaných hran A ⊆ V (G) × V (G) a zobraz´ıme je takto. . .

s


s

s

s

s

7 / 24

s


4.2

Podgrafy a Isomorfismus

Definice: Podgrafem grafu G rozum´ıme libovolný graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), který má za hrany libovolnou podmnoˇzinu hran grafu G maj´ıc´ıch oba vrcholy ve V (H). P´ıˇseme H ⊆ G, tj. stejnˇe jako mnoˇzinová inkluze (ale význam je trochu jiný).


8 / 24


4.2


Definice: Podgrafem grafu G rozum´ıme libovolný graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), který má za hrany libovolnou podmnoˇzinu hran grafu G maj´ıc´ıch oba vrcholy ve V (H). P´ıˇseme H ⊆ G, tj. stejnˇe jako mnoˇzinová inkluze (ale význam je trochu jiný). Na následuj´ıc´ım obrázku vid´ıme zvýraznˇené podmnoˇziny vrchol˚ u hran. Proˇc se vlevo nejedná o podgraf? Obrázek vpravo uˇz podgrafem je.

s

s

s

s

s


s

s

8 / 24

s

s

s

s

s


4.2


Definice: Podgrafem grafu G rozum´ıme libovolný graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), který má za hrany libovolnou podmnoˇzinu hran grafu G maj´ıc´ıch oba vrcholy ve V (H). P´ıˇseme H ⊆ G, tj. stejnˇe jako mnoˇzinová inkluze (ale význam je trochu jiný). Na následuj´ıc´ım obrázku vid´ıme zvýraznˇené podmnoˇziny vrchol˚ u hran. Proˇc se vlevo nejedná o podgraf? Obrázek vpravo uˇz podgrafem je.

s

s

s

s

s

s

s

s

s

s

s

s

Definice: Indukovaným podgrafem je podgraf H ⊆ G takový, který obsahuje vˇsechny hrany grafu G mezi dvojicemi vrchol˚ u z V (H). Petr Hlinˇ en´ y, FI MU Brno, 2014

8 / 24


Stejnost“ graf˚ u ” s

s


s

s

? =

s s @ @ @ @ s @s

9 / 24

? =

s s @ @ @ @ s @s



s

s

s

? =

s s @ @ @ @ s @s

? =

s s @ @ @ @ s @s

Definice 4.4. Isomorfismus ' graf˚ uGaH je bijektivn´ı zobrazen´ı f : V (G) → V (H), pro které kaˇzdá dvojice u, v ∈ V (G) je spojená hranou v G právˇe, kdyˇz je dvojice f (u), f (v) spojená hranou v H. Grafy G a H jsou isomorfn´ı, G ' H, pokud mezi nimi existuje isomorfismus.


9 / 24



s

s

s

? =

s s @ @ @ @ s @s

? =

s s @ @ @ @ s @s

Definice 4.4. Isomorfismus ' graf˚ uGaH je bijektivn´ı zobrazen´ı f : V (G) → V (H), pro které kaˇzdá dvojice u, v ∈ V (G) je spojená hranou v G právˇe, kdyˇz je dvojice f (u), f (v) spojená hranou v H. Grafy G a H jsou isomorfn´ı, G ' H, pokud mezi nimi existuje isomorfismus. Fakt: Mˇejme isomorfismus f graf˚ u G a H. Pak plat´ı následuj´ıc´ı ∗ G a H maj´ı stejný poˇcet hran, ∗ f zobrazuje na sebe vrcholy stejných stupˇ n˚ u, tj. dG (v) = dH (f (v)).


9 / 24



s

s

? =

s

s s @ @ @ @ s @s

? =

s s @ @ @ @ s @s

Definice 4.4. Isomorfismus ' graf˚ uGaH je bijektivn´ı zobrazen´ı f : V (G) → V (H), pro které kaˇzdá dvojice u, v ∈ V (G) je spojená hranou v G právˇe, kdyˇz je dvojice f (u), f (v) spojená hranou v H. Grafy G a H jsou isomorfn´ı, G ' H, pokud mezi nimi existuje isomorfismus. Fakt: Mˇejme isomorfismus f graf˚ u G a H. Pak plat´ı následuj´ıc´ı ∗ G a H maj´ı stejný poˇcet hran, ∗ f zobrazuje na sebe vrcholy stejných stupˇ n˚ u, tj. dG (v) = dH (f (v)). s

s s s


s s QQ Q QQ s QQs

9 / 24



s

s

? =

s

s s @ @ @ @ s @s

? =

s s @ @ @ @ s @s

Definice 4.4. Isomorfismus ' graf˚ uGaH je bijektivn´ı zobrazen´ı f : V (G) → V (H), pro které kaˇzdá dvojice u, v ∈ V (G) je spojená hranou v G právˇe, kdyˇz je dvojice f (u), f (v) spojená hranou v H. Grafy G a H jsou isomorfn´ı, G ' H, pokud mezi nimi existuje isomorfismus. Fakt: Mˇejme isomorfismus f graf˚ u G a H. Pak plat´ı následuj´ıc´ı ∗ G a H maj´ı stejný poˇcet hran, ∗ f zobrazuje na sebe vrcholy stejných stupˇ n˚ u, tj. dG (v) = dH (f (v)). s

s s s

s s QQ Q QQ s QQs

U nakreslených dvou graf˚ u objev´ıme isomorfismus velmi snadno – pod´ıváme se, jak si odpov´ıdaj´ı vrcholy stejných stupˇ n˚ u. Petr Hlinˇ en´ y, FI MU Brno, 2014

9 / 24


Pˇr´ıklad 4.5. Jsou následuj´ıc´ı dva grafy isomorfn´ı? s s S S S Ss

s S S S Ss s

s s A """ A "" A s" A s " " bb A bb A""" b"A s""bbAs

Pokud mezi nakreslenými dvˇema grafy hledáme isomorfismus, nejprve se pod´ıváme, zda maj´ı stejný poˇcet vrchol˚ u a hran.


10 / 24



s S S S Ss s


Pokud mezi nakreslenými dvˇema grafy hledáme isomorfismus, nejprve se pod´ıváme, zda u a zjist´ıme, maj´ı stejný poˇcet vrchol˚ u a hran. Maj´ı. Pak se pod´ıváme na stupnˇe vrchol˚ ˇze oba maj´ı stejnou posloupnost stupˇ n˚ u 2, 2, 2, 2, 3, 3.


10 / 24



s S S S Ss s


Pokud mezi nakreslenými dvˇema grafy hledáme isomorfismus, nejprve se pod´ıváme, zda u a zjist´ıme, maj´ı stejný poˇcet vrchol˚ u a hran. Maj´ı. Pak se pod´ıváme na stupnˇe vrchol˚ ˇze oba maj´ı stejnou posloupnost stupˇ n˚ u 2, 2, 2, 2, 3, 3. Takˇze ani takto jsme mezi nimi nerozliˇsili a mohou (nemusej´ı!) být isomorfn´ı. Dále tedy nezbývá, neˇz zkouˇset vˇsechny pˇr´ıpustné moˇznosti zobrazen´ı isomorfismu z levého grafu do pravého.


10 / 24



s S S S Ss s


Pokud mezi nakreslenými dvˇema grafy hledáme isomorfismus, nejprve se pod´ıváme, zda u a zjist´ıme, maj´ı stejný poˇcet vrchol˚ u a hran. Maj´ı. Pak se pod´ıváme na stupnˇe vrchol˚ ˇze oba maj´ı stejnou posloupnost stupˇ n˚ u 2, 2, 2, 2, 3, 3. Takˇze ani takto jsme mezi nimi nerozliˇsili a mohou (nemusej´ı!) být isomorfn´ı. Dále tedy nezbývá, neˇz zkouˇset vˇsechny pˇr´ıpustné moˇznosti zobrazen´ı isomorfismu z levého grafu do pravého. Na levém grafu si pro ulehˇcen´ı vˇsimnˇeme, ˇze oba vrcholy stupnˇe tˇri jsou si symetrické, proto si bez u ´jmy na obecnosti m˚ uˇzeme vybrat, ˇze vrchol oznaˇcený 1 se zobraz´ı na 10 . Druhý vrchol stupnˇe tˇri, oznaˇcený 4, se mus´ı zobrazit na analogický vrchol druhého grafu 40 . A zbytek jiˇz plyne snadno: s5 6 s 5’ s "s 6’ A" S " Ss 4 s " AA s s 1 1’ " bb " 2’ " S A bb "" s3 2Ss 3’ s"bAs 4’ 2 Petr Hlinˇ en´ y, FI MU Brno, 2014

10 / 24


D˚ usledek: Stejnost graf˚ u jako isomorfismus!

←→

Graf G

4 s

s3

1 s

s2


Celá tˇr´ıda isomorfismu grafu G

4 s

'

s2 @ @ @ @ @ @ @s 3 s 1

11 / 24

3 s

'

s4 @ @ @ @ @ @ @s 2 s 1



←→

Graf G

4 s

s3

1 s

s2


4 s

'

s2 @ @ @ @ @ @ @s 3 s 1

3 s

'

s4 @ @ @ @ @ @ @s 2 s 1

Je uvedený pˇr´ıstup, tj. zamˇen ˇován´ı konkrétn´ıho grafu za celou jeho tˇr´ıdu isomorfismu, v matematice neobvyklý?


11 / 24



←→

Graf G

4 s

s3

1 s

s2


4 s

'

s2 @ @ @ @ @ @ @s 3 s 1

3 s

'

s4 @ @ @ @ @ @ @s 2 s 1

Je uvedený pˇr´ıstup, tj. zamˇen ˇován´ı konkrétn´ıho grafu za celou jeho tˇr´ıdu isomorfismu, v matematice neobvyklý? Ne, napˇr´ıklad uˇz v geometrii jste ˇr´ıkali ˇctverec o stranˇe 2“ ” ˇci jednotkový kruh“ a podobnˇe, aniˇz jste mˇeli na mysli konkrétn´ı obrázek, nýbrˇz celou ” tˇr´ıdu vˇsech tˇechto shodných objekt˚ u.


11 / 24


6 s

Dalˇs´ı grafov´ e pojmy

s 1 S S S S 2 Ss

Definice: Mˇejme libovolný graf G.


12 / 24

s5 S S S S Ss 4 s3


6 s


s 1 S S S S 2 Ss


s5 S S S S Ss 4 s3

∗ Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké kruˇznici, ˇr´ıkáme kruˇznice v G. ∗ Speciálnˇe ˇr´ıkáme troj´ uheln´ık kruˇznici délky 3.


12 / 24


6 s


s 1 S S S S 2 Ss


s5 S S S S Ss 4 s3

∗ Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké kruˇznici, ˇr´ıkáme kruˇznice v G. ∗ Speciálnˇe ˇr´ıkáme troj´ uheln´ık kruˇznici délky 3. ∗ Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké cestˇe, ˇr´ıkáme cesta v G.


12 / 24


6 s


s 1 S S S S 2 Ss


s5 S S S S Ss 4 s3

∗ ∗ ∗ ∗

Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké kruˇznici, ˇr´ıkáme kruˇznice v G. Speciálnˇe ˇr´ıkáme troj´ uheln´ık kruˇznici délky 3. Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké cestˇe, ˇr´ıkáme cesta v G. Podgrafu H ⊆ G, který je isomorfn´ı nˇejakému u ´plnému grafu, ˇr´ıkáme klika v G. ∗ Podmnoˇzinˇe vrchol˚ u X ⊆ V (G), mezi kterými nevedou v G v˚ ubec ˇzádné hrany, ˇr´ıkáme nezávislá mnoˇzina X v G.


12 / 24


6 s


s 1 S S S S 2 Ss


s5 S S S S Ss 4 s3

∗ ∗ ∗ ∗

Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké kruˇznici, ˇr´ıkáme kruˇznice v G. Speciálnˇe ˇr´ıkáme troj´ uheln´ık kruˇznici délky 3. Podgrafu H ⊆ G, který je isomorfn´ı nˇejaké cestˇe, ˇr´ıkáme cesta v G. Podgrafu H ⊆ G, který je isomorfn´ı nˇejakému u ´plnému grafu, ˇr´ıkáme klika v G. ∗ Podmnoˇzinˇe vrchol˚ u X ⊆ V (G), mezi kterými nevedou v G v˚ ubec ˇzádné hrany, ˇr´ıkáme nezávislá mnoˇzina X v G. ∗ Indukovanému podgrafu H ⊆ G, který je isomorfn´ı nˇejaké kruˇznici, ˇr´ıkáme indukovaná kruˇznice v G. Petr Hlinˇ en´ y, FI MU Brno, 2014

12 / 24


4.3

Souvislost graf˚ u, komponenty

D˚ uleˇzitou globáln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu.


13 / 24


4.3


D˚ uleˇzitou globáln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovolného grafu G takovou, ˇze pro dva vrcholy x ∼ y právˇe kdyˇz existuje v G cesta zaˇc´ınaj´ıc´ı v x a konˇc´ıc´ı v y. Pak ∼ je relac´ı ekvivalence.


13 / 24


4.3


D˚ uleˇzitou globáln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovolného grafu G takovou, ˇze pro dva vrcholy x ∼ y právˇe kdyˇz existuje v G cesta zaˇc´ınaj´ıc´ı v x a konˇc´ıc´ı v y. Pak ∼ je relac´ı ekvivalence. D˚ ukaz. • Relace ∼ je reflexivn´ı, nebot’ kaˇzdý vrchol je spojený sám se sebou cestou délky 0.


13 / 24


4.3


D˚ uleˇzitou globáln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovolného grafu G takovou, ˇze pro dva vrcholy x ∼ y právˇe kdyˇz existuje v G cesta zaˇc´ınaj´ıc´ı v x a konˇc´ıc´ı v y. Pak ∼ je relac´ı ekvivalence. D˚ ukaz. • Relace ∼ je reflexivn´ı, nebot’ kaˇzdý vrchol je spojený sám se sebou cestou délky 0. • Symetrická je také, protoˇze cestu z x do y snadno v neorientovaném grafu obrát´ıme na cestu z y do x.


13 / 24


4.3


D˚ uleˇzitou globáln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovolného grafu G takovou, ˇze pro dva vrcholy x ∼ y právˇe kdyˇz existuje v G cesta zaˇc´ınaj´ıc´ı v x a konˇc´ıc´ı v y. Pak ∼ je relac´ı ekvivalence. D˚ ukaz. • Relace ∼ je reflexivn´ı, nebot’ kaˇzdý vrchol je spojený sám se sebou cestou délky 0. • Symetrická je také, protoˇze cestu z x do y snadno v neorientovaném grafu obrát´ıme na cestu z y do x. • Pro d˚ ukaz tranzitivity si oznaˇcme P cestu z x do y a Q cestu z y do z. Pak P ∪ Q nemus´ı být cesta; mohou se navzájem prot´ınat.


13 / 24


4.3


D˚ uleˇzitou globáln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv podél jeho hran, neboli po cestách v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovolného grafu G takovou, ˇze pro dva vrcholy x ∼ y právˇe kdyˇz existuje v G cesta zaˇc´ınaj´ıc´ı v x a konˇc´ıc´ı v y. Pak ∼ je relac´ı ekvivalence. D˚ ukaz. • Relace ∼ je reflexivn´ı, nebot’ kaˇzdý vrchol je spojený sám se sebou cestou délky 0. • Symetrická je také, protoˇze cestu z x do y snadno v neorientovaném grafu obrát´ıme na cestu z y do x. • Pro d˚ ukaz tranzitivity si oznaˇcme P cestu z x do y a Q cestu z y do z. Pak P ∪ Q nemus´ı být cesta; mohou se navzájem prot´ınat. Avˇsak pokud oznaˇc´ıme P 0 ⊆ P ˇcást cesty z x do prvn´ıho vrcholu z v pr˚ uniku s Q a Q0 ⊆ Q zbytek druhé cesty od z, tak P 0 ∪ Q0 uˇz je cesta z x do z. 2 Petr Hlinˇ en´ y, FI MU Brno, 2014

13 / 24


Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence výˇse popsané (Lema 7.6) relace ∼ na V (G).


14 / 24


Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence výˇse popsané (Lema 7.6) relace ∼ na V (G). Jinak se také komponentami souvislosti mysl´ı podgrafy indukované na tˇechto tˇr´ıdách ekvivalence.


14 / 24


Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence výˇse popsané (Lema 7.6) relace ∼ na V (G). Jinak se také komponentami souvislosti mysl´ı podgrafy indukované na tˇechto tˇr´ıdách ekvivalence. Pod´ıvejte se, kolik komponent souvislosti má tento graf:

s

s @ @ @ @ @s

s

s

s

s

s @ @ @ @ @s

s


s

14 / 24

s s


Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence výˇse popsané (Lema 7.6) relace ∼ na V (G). Jinak se také komponentami souvislosti mysl´ı podgrafy indukované na tˇechto tˇr´ıdách ekvivalence. Pod´ıvejte se, kolik komponent souvislosti má tento graf:

s

s @ @ @ @ @s

s

s

s

s

s @ @ @ @ @s

s

s

s s

Vid´ıte v obrázku vˇsechny tˇri komponenty? Jedna z nich je izolovaným vrcholem, druhá hranou (tj. grafem isomorfn´ım K2 ) a tˇret´ı je to zbývaj´ıc´ı.


14 / 24


Definice 4.8. Graf G je souvisl´ y pokud je G tvoˇrený nejvýˇse jednou komponentou souvislosti, tj. pokud kaˇzdé dva vrcholy G jsou spojené cestou.


15 / 24


Definice 4.8. Graf G je souvisl´ y pokud je G tvoˇrený nejvýˇse jednou komponentou souvislosti, tj. pokud kaˇzdé dva vrcholy G jsou spojené cestou. Který z tˇechto dvou graf˚ u je souvislý? s s s !s QQ QQ !! ! ! QQ QQ !! !! QQ QQ ! ! Q !!! QQQ Q ! QQ Q ! QQ !! ! QQ ! QQ QQ !! ! ! Qs ! Qs s s


s s s s b bb " !! ! b " \ ! bb " ! \bb bb !!!! bb \"" ! \ ! ! b bb""" \ ! bb b !!\ bb b "" ! ! b " bb bb\\ "!!! " bb bb "!! \ ! " ! s! " s \s bs b

15 / 24


4.4

Stromy – grafy bez kruˇ znic s s s s J E % s J E % J E % J E % s JE% s s B B B B Bs s J J J J Js

s

B

B

B

B

Bs s B B B B B B B B Bs Bs s

Be

Be

Be s

B e s s Bs es

Charakteristickými znaky strom˚ u je absence kruˇznic a souvislost. . .


16 / 24


4.4


s

B

B

B

B


Be

Be

Be s

B e s s Bs es


Definice 4.9. Strom je jednoduchý souvislý graf T bez kruˇznic.


16 / 24


4.4


s

B

B

B

B


Be

Be

Be s

B e s s Bs es


Definice 4.9. Strom je jednoduchý souvislý graf T bez kruˇznic. Les je jednoduchý graf bez kruˇznic (nemus´ı být souvislý). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a prázdný graf jsou také stromy. Grafy bez kruˇznic také obecnˇe nazýváme acyklické. Petr Hlinˇ en´ y, FI MU Brno, 2014

16 / 24


Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1.


17 / 24


Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvislý graf s v´ıce neˇz jedn´ım vrcholem nem˚ uˇze m´ıt vrchol stupnˇe 0. Proto vezmeme strom T a v nˇem libovolný vrchol v.


17 / 24


Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvislý graf s v´ıce neˇz jedn´ım vrcholem nem˚ uˇze m´ıt vrchol stupnˇe 0. Proto vezmeme strom T a v nˇem libovolný vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı cestu S v T zaˇc´ınaj´ıc´ı ve v: ∗ S zaˇcne libovolnou hranou vycházej´ıc´ı z v;


17 / 24


Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvislý graf s v´ıce neˇz jedn´ım vrcholem nem˚ uˇze m´ıt vrchol stupnˇe 0. Proto vezmeme strom T a v nˇem libovolný vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı cestu S v T zaˇc´ınaj´ıc´ı ve v: ∗ S zaˇcne libovolnou hranou vycházej´ıc´ı z v; ∗ v kaˇzdém dalˇs´ım vrcholu u, do kterého se dostaneme a má stupeˇ n vˇetˇs´ı neˇz 1, lze pak pokraˇcovat cestu S dalˇs´ı novou hranou. S s hhhhs

s `` ` v f s `


cc ccs ...

17 / 24

f s s


Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvislý graf s v´ıce neˇz jedn´ım vrcholem nem˚ uˇze m´ıt vrchol stupnˇe 0. Proto vezmeme strom T a v nˇem libovolný vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı cestu S v T zaˇc´ınaj´ıc´ı ve v: ∗ S zaˇcne libovolnou hranou vycházej´ıc´ı z v; ∗ v kaˇzdém dalˇs´ım vrcholu u, do kterého se dostaneme a má stupeˇ n vˇetˇs´ı neˇz 1, lze pak pokraˇcovat cestu S dalˇs´ı novou hranou. S s hhhhs

s `` ` v f s `

cc ccs ...

f s s

Pokud by se v S poprvé zopakoval nˇekterý vrchol, z´ıskali bychom kruˇznici. Proto cesta S mus´ı jednou skonˇcit v nˇejakém vrcholu stupnˇe 1 v T . 2


17 / 24


Vˇ eta 4.11. Strom na n vrcholech má pˇresnˇe n − 1 hran pro n ≥ 1.


18 / 24


Vˇ eta 4.11. Strom na n vrcholech má pˇresnˇe n − 1 hran pro n ≥ 1. D˚ ukaz: Toto tvrzen´ı dokáˇzeme indukc´ı podle n. ∗ Strom s jedn´ım vrcholem má n − 1 = 0 hran.


18 / 24



∗ Necht’ T je strom na n > 1 vrcholech.

s A A A A A A A 0 T A A A A

T :

v s

Podle Lematu 7.10 má T vrchol v stupnˇe 1. Oznaˇcme T 0 = T − v graf vzniklý z T odebrán´ım vrcholu v.


18 / 24



∗ Necht’ T je strom na n > 1 vrcholech.

s A A A A A A A 0 T A A A A

T :

v s

Podle Lematu 7.10 má T vrchol v stupnˇe 1. Oznaˇcme T 0 = T − v graf vzniklý z T odebrán´ım vrcholu v. Pak T 0 je také souvislý bez kruˇznic, tud´ıˇz strom na n − 1 vrcholech. Dle indukˇcn´ıho pˇredpokladu T 0 má n − 1 − 1 2 hran, a proto T má n − 1 − 1 + 1 = n − 1 hran.


18 / 24


Vˇ eta 4.12. Mezi kaˇzdými dvˇema vrcholy stromu vede právˇe jediná cesta.


19 / 24



D˚ ukaz: Jelikoˇz strom T je souvislý dle definice, mezi libovolnými dvˇema vrcholy u, v vede nˇejaká cesta.


19 / 24



s u f

P1 s

s s @ H H HH @ @ HHs @ s s Z cc ZZ cc Zs s c s

P2

s

sv f

D˚ ukaz: Jelikoˇz strom T je souvislý dle definice, mezi libovolnými dvˇema vrcholy u, v vede nˇejaká cesta. Pokud by existovaly dvˇe r˚ uzné cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrický rozd´ıl, podgraf H = P1 ∆P2 s neprázdnou mnoˇzinou hran, kde H zˇrejmˇe má vˇsechny stupnˇe sudé.


19 / 24



s u f

P1 s


P2

s

sv f

D˚ ukaz: Jelikoˇz strom T je souvislý dle definice, mezi libovolnými dvˇema vrcholy u, v vede nˇejaká cesta. Pokud by existovaly dvˇe r˚ uzné cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrický rozd´ıl, podgraf H = P1 ∆P2 s neprázdnou mnoˇzinou hran, kde H zˇrejmˇe má vˇsechny stupnˇe sudé. Na druhou stranu se vˇsak podgraf stromu mus´ı opˇet skládat z komponent strom˚ u, a tud´ıˇz obsahovat vrchol stupnˇe 1 podle Lematu 7.10, spor.


19 / 24



s u f

P1 s


P2

s

sv f

D˚ ukaz: Jelikoˇz strom T je souvislý dle definice, mezi libovolnými dvˇema vrcholy u, v vede nˇejaká cesta. Pokud by existovaly dvˇe r˚ uzné cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrický rozd´ıl, podgraf H = P1 ∆P2 s neprázdnou mnoˇzinou hran, kde H zˇrejmˇe má vˇsechny stupnˇe sudé. Na druhou stranu se vˇsak podgraf stromu mus´ı opˇet skládat z komponent strom˚ u, a tud´ıˇz obsahovat vrchol stupnˇe 1 2 podle Lematu 7.10, spor. D˚ usledek 4.13. Pˇridán´ım jedné hrany do stromu vznikne právˇe jedna kruˇznice.


19 / 24


Alternativn´ı charakterizace strom˚ u Na dané mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minimáln´ı souvislý graf (plyne z Vˇety 7.12) • a zároveˇ n maximáln´ı acyklický graf (plyne z D˚ usledku 7.13). s

s

s

s


s s

20 / 24


Alternativn´ı charakterizace strom˚ u Na dané mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minimáln´ı souvislý graf (plyne z Vˇety 7.12) • a zároveˇ n maximáln´ı acyklický graf (plyne z D˚ usledku 7.13). s " " "" "" " " s""

s

s


s s

20 / 24


Alternativn´ı charakterizace strom˚ u Na dané mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minimáln´ı souvislý graf (plyne z Vˇety 7.12) • a zároveˇ n maximáln´ı acyklický graf (plyne z D˚ usledku 7.13). s " " "" "" " " " s" s


s

s s

20 / 24




s D D D D D D D D D D Ds

20 / 24

s




s D s D D % D % D % D % D D %% D D % Ds%

20 / 24


Alternativn´ı charakterizace strom˚ u Na dané mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minimáln´ı souvislý graf (plyne z Vˇety 7.12) • a zároveˇ n maximáln´ı acyklický graf (plyne z D˚ usledku 7.13). s "``````` " ````s " "" " D s "" D D s"" % D % D % D % D D %% D D % Ds% s


20 / 24




20 / 24




20 / 24


4.5

Jedn´ım tahem – Eulerovsk´ e grafy

Pravd. nejstarˇs´ı zaznamenaný výsledek teorie graf˚ u pocház´ı od L. Eulera – jedná se o slavných 7 most˚ u v Královci / K¨ onigsbergu / dneˇsn´ım Kaliningradˇe.

O jaký problém se tehdy jednalo? Mˇestˇst´ı radn´ı chtˇeli vˇedˇet, zda mohou suchou nohou pˇrej´ıt po kaˇzdém ze sedmi vyznaˇcených most˚ u právˇe jednou. Petr Hlinˇ en´ y, FI MU Brno, 2014

21 / 24


Sled a tah v grafu Definice: Sledem délky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn )


22 / 24


Sled a tah v grafu Definice: Sledem délky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn ) , ve které vˇzdy hrana ei má koncové vrcholy vi−1 , vi . Sled je vlastnˇe procházka po hranách grafu z u do v. Pˇr´ıkladem sledu m˚ uˇze být pr˚ uchod IP paketu internetem (vˇcetnˇe cyklen´ı).


22 / 24



Definice: Tah je sled v grafu bez opakován´ı hran.


22 / 24



Definice: Tah je sled v grafu bez opakován´ı hran. Uzavˇrený tah je tahem, který konˇc´ı ve vrcholu, ve kterém zaˇcal. Otevˇrený tah je tahem, který konˇc´ı v jiném vrcholu, neˇz ve kterém zaˇcal. Znáte dˇetské kreslen´ı jedn´ım tahem“? Ano, to je v podstatˇe i náˇs tah (v nakresl. grafu). ”


22 / 24



Definice: Tah je sled v grafu bez opakován´ı hran. Uzavˇrený tah je tahem, který konˇc´ı ve vrcholu, ve kterém zaˇcal. Otevˇrený tah je tahem, který konˇc´ı v jiném vrcholu, neˇz ve kterém zaˇcal. Znáte dˇetské kreslen´ı jedn´ım tahem“? Ano, to je v podstatˇe i náˇs tah (v nakresl. grafu). ”

Fakt: Cesta je právˇe otevˇrený tah bez opakován´ı vrchol˚ u. Kruˇznice je právˇe uzavˇrený tah bez opakován´ı vrchol˚ u. Petr Hlinˇ en´ y, FI MU Brno, 2014

22 / 24


Eulerova charakterizace Onen slavný výsledek teorie graf˚ u od Leonharda Eulera poté zn´ı následovnˇe. h h @ @ @ @ @ @ @h h @ @ @ @ @h @h

s s @ @ @ @ @s s @ @ @ @ @ @s @s


23 / 24



s s @ @ @ @ @s s @ @ @ @ @ @s @s

Vˇ eta 4.14. Graf G lze nakreslit jedn´ım uzavˇreným tahem právˇe kdyˇz G je souvislý a vˇsechny vrcholy v G jsou sudého stupnˇe.


23 / 24



s s @ @ @ @ @s s @ @ @ @ @ @s @s

Vˇ eta 4.14. Graf G lze nakreslit jedn´ım uzavˇreným tahem právˇe kdyˇz G je souvislý a vˇsechny vrcholy v G jsou sudého stupnˇe. D˚ usledek 4.15. Graf G lze nakreslit jedn´ım otevˇreným tahem právˇe kdyˇz G je souvislý a vˇsechny vrcholy v G aˇz na dva jsou sudého stupnˇe.


23 / 24


D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇreným tahem, tak je zˇrejmˇe souvislý a nav´ıc má kaˇzdý stupeˇ n sudý, nebot’ uzavˇrený tah kaˇzdým pr˚ uchodem vrcholem ubere“ dvˇe hrany. ”


24 / 24


D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇreným tahem, tak je zˇrejmˇe souvislý a nav´ıc má kaˇzdý stupeˇ n sudý, nebot’ uzavˇrený tah kaˇzdým pr˚ uchodem vrcholem ubere“ dvˇe hrany. ” Naopak zvol´ıme mezi vˇsemi uzavˇrenými tahy T v G ten (jeden z) nejdelˇs´ı. Tvrd´ıme, ˇze T obsahuje vˇsechny hrany grafu G. – Pro spor vezmˇeme graf G0 = G − E(T ), o kterém pˇredpokládejme, ˇze je neprázdný. Jelikoˇz G0 má taktéˇz vˇsechny stupnˇe sudé, je (z indukˇcn´ıho pˇredpokladu) libovolná jeho komponenta C ⊆ G0 nakreslená jedn´ım uzavˇreným tahem TC .


24 / 24


D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇreným tahem, tak je zˇrejmˇe souvislý a nav´ıc má kaˇzdý stupeˇ n sudý, nebot’ uzavˇrený tah kaˇzdým pr˚ uchodem vrcholem ubere“ dvˇe hrany. ” Naopak zvol´ıme mezi vˇsemi uzavˇrenými tahy T v G ten (jeden z) nejdelˇs´ı. Tvrd´ıme, ˇze T obsahuje vˇsechny hrany grafu G. – Pro spor vezmˇeme graf G0 = G − E(T ), o kterém pˇredpokládejme, ˇze je neprázdný. Jelikoˇz G0 má taktéˇz vˇsechny stupnˇe sudé, je (z indukˇcn´ıho pˇredpokladu) libovolná jeho komponenta C ⊆ G0 nakreslená jedn´ım uzavˇreným tahem TC . – Vzhledem k souvislosti grafu G kaˇzdá komponenta C ⊆ G0 prot´ıná náˇs tah T v nˇekterém vrchole w, a tud´ıˇz lze oba tahy TC a T propojit ” pˇres w“. To je spor s naˇs´ım pˇredpokladem nejdelˇs´ıho moˇzného T .


24 / 24


D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇreným tahem, tak je zˇrejmˇe souvislý a nav´ıc má kaˇzdý stupeˇ n sudý, nebot’ uzavˇrený tah kaˇzdým pr˚ uchodem vrcholem ubere“ dvˇe hrany. ” Naopak zvol´ıme mezi vˇsemi uzavˇrenými tahy T v G ten (jeden z) nejdelˇs´ı. Tvrd´ıme, ˇze T obsahuje vˇsechny hrany grafu G. – Pro spor vezmˇeme graf G0 = G − E(T ), o kterém pˇredpokládejme, ˇze je neprázdný. Jelikoˇz G0 má taktéˇz vˇsechny stupnˇe sudé, je (z indukˇcn´ıho pˇredpokladu) libovolná jeho komponenta C ⊆ G0 nakreslená jedn´ım uzavˇreným tahem TC . – Vzhledem k souvislosti grafu G kaˇzdá komponenta C ⊆ G0 prot´ıná náˇs tah T v nˇekterém vrchole w, a tud´ıˇz lze oba tahy TC a T propojit ” pˇres w“. To je spor s naˇs´ım pˇredpokladem nejdelˇs´ıho moˇzného T . 2 D˚ ukaz d˚ usledku: Necht’ u, v jsou dva vrcholy grafu G maj´ıc´ı lichý stupeˇ n, neboli dva (pˇredpokládané) konce otevˇreného tahu pro G. Do G nyn´ı pˇridáme nový vrchol w spojený hranami s u a v. T´ım jsme náˇs pˇr´ıpad pˇrevedli na pˇredchoz´ı pˇr´ıpad grafu se vˇsemi sudými stupni. 2 Petr Hlinˇ en´ y, FI MU Brno, 2014

24 / 24


4 Pojem grafu, ve zkratce

Recommend Documents