4
Pojem grafu, ve zkratce
Tˇrebaˇze grafy jsou jen jednou z mnoha struktur v matematice a vlastnˇe pouze speci´aln´ım pˇr´ıpadem bin´arn´ıch relac´ı, vydobyly si svou uˇziteˇcnost´ı a n´azornost´ı d˚ uleˇzit´e m´ısto na slunci. Neform´alnˇe ˇreˇceno, graf se skl´ad´a z vrchol˚ u (pˇredstavme si je jako nakreslen´e punt´ıky“) ” a z hran, kter´e 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´aln´ım pˇr´ıpadem bin´arn´ıch relac´ı, vydobyly si svou uˇziteˇcnost´ı a n´azornost´ı d˚ uleˇzit´e m´ısto na slunci. Neform´alnˇe ˇreˇceno, graf se skl´ad´a z vrchol˚ u (pˇredstavme si je jako nakreslen´e punt´ıky“) ” a z hran, kter´e 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´akladn´ı pojmy. * Pˇr´ıklady bˇeˇzn´ych tˇr´ıd graf˚ u, podgrafy a isomorfismus, souvislost. * Stromy a jejich speci´aln´ı vlastnosti. Petr Hlinˇ en´ y, FI MU Brno, 2014
1 / 24
FI: IB000: Pojem grafu
4.1
Definice grafu
Definice 4.1. Graf (jednoduch´y neorient.) je uspoˇr´adan´a dvojice G = (V, E), kde V je mnoˇzina vrchol˚ u a E je mnoˇzina hran – mnoˇzina vybran´ych dvouprvkov´ych podmnoˇzin mnoˇziny vrchol˚ u. s HHH HH Hs s s
1
2
Petr Hlinˇ en´ y, FI MU Brno, 2014
3
4
2 / 24
FI: IB000: Pojem grafu
4.1
Definice grafu
Definice 4.1. Graf (jednoduch´y neorient.) je uspoˇr´adan´a dvojice G = (V, E), kde V je mnoˇzina vrchol˚ u a E je mnoˇzina hran – mnoˇzina vybran´ych dvouprvkov´ych podmnoˇzin mnoˇziny vrchol˚ u. s HHH HH Hs s s
1
2
3
4
Znaˇ cen´ı: Hranu mezi vrcholy u a v p´ıˇseme jako {u, v}, nebo zkr´acenˇe uv. Vrcholy spojen´e hranou jsou sousedn´ı a hrana uv vych´az´ı z vrchol˚ u u a v. Na mnoˇzinu vrchol˚ u grafu G odkazujeme jako na V (G), na mnoˇzinu hran E(G).
Petr Hlinˇ en´ y, FI MU Brno, 2014
2 / 24
FI: IB000: Pojem grafu
4.1
Definice grafu
Definice 4.1. Graf (jednoduch´y neorient.) je uspoˇr´adan´a dvojice G = (V, E), kde V je mnoˇzina vrchol˚ u a E je mnoˇzina hran – mnoˇzina vybran´ych dvouprvkov´ych podmnoˇzin mnoˇziny vrchol˚ u. s HHH HH Hs s s
1
2
3
4
Znaˇ cen´ı: Hranu mezi vrcholy u a v p´ıˇseme jako {u, v}, nebo zkr´acenˇe uv. Vrcholy spojen´e hranou jsou sousedn´ı a hrana uv vych´az´ı 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´avaj´ı pˇr´ımo n´azorn´ym obr´azkem, jinak je lze form´alnˇe zadat v´yˇctem vrchol˚ u a v´yˇ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´e jako na symetrickou ireflexivn´ı relaci, kde hrany tvoˇr´ı pr´avˇe dvojice prvk˚ u z t´eto relace. Petr Hlinˇ en´ y, FI MU Brno, 2014
2 / 24
FI: IB000: Pojem grafu
Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vych´azej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v).
Petr Hlinˇ en´ y, FI MU Brno, 2014
3 / 24
FI: IB000: Pojem grafu
Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vych´azej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v). Slovo vych´azej´ıc´ı“ zde nenaznaˇcuje ˇz´adn´y smˇer; je totiˇz obecnou konvenc´ı u neorien” tovan´ych graf˚ u ˇr´ıkat, ˇze hrana vych´az´ı z obou sv´ych konc˚ u z´aroveˇ n. 2 s s 3 S S S 2Ss
s2 S S S Ss 3 s2
Petr Hlinˇ en´ y, FI MU Brno, 2014
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
FI: IB000: Pojem grafu
Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vych´azej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v). Slovo vych´azej´ıc´ı“ zde nenaznaˇcuje ˇz´adn´y smˇer; je totiˇz obecnou konvenc´ı u neorien” tovan´ych graf˚ u ˇr´ıkat, ˇze hrana vych´az´ı z obou sv´ych konc˚ u z´aroveˇ n. 2 s s 3 S S S 2Ss
s2 S S S Ss 3 s2
stupnˇe
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
Definice: Graf je d-regul´arn´ı, pokud vˇsechny jeho vrcholy maj´ı stejn´y stupeˇ n d.
Petr Hlinˇ en´ y, FI MU Brno, 2014
3 / 24
FI: IB000: Pojem grafu
Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vych´azej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v). Slovo vych´azej´ıc´ı“ zde nenaznaˇcuje ˇz´adn´y smˇer; je totiˇz obecnou konvenc´ı u neorien” tovan´ych graf˚ u ˇr´ıkat, ˇze hrana vych´az´ı z obou sv´ych konc˚ u z´aroveˇ n. 2 s s 3 S S S 2Ss
s2 S S S Ss 3 s2
stupnˇe
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
Definice: Graf je d-regul´arn´ı, pokud vˇsechny jeho vrcholy maj´ı stejn´y stupeˇ n d. Znaˇ cen´ı: Nejvyˇsˇs´ı stupeˇ n v grafu G znaˇc´ıme ∆(G) a nejniˇzˇs´ı δ(G).
Petr Hlinˇ en´ y, FI MU Brno, 2014
3 / 24
FI: IB000: Pojem grafu
Stupnˇ e vrchol˚ u v grafu Definice 4.2. Stupnˇ em vrcholu v v grafu G rozum´ıme poˇcet hran vych´azej´ıc´ıch z v. Stupeˇ n v v grafu G znaˇc´ıme dG (v). Slovo vych´azej´ıc´ı“ zde nenaznaˇcuje ˇz´adn´y smˇer; je totiˇz obecnou konvenc´ı u neorien” tovan´ych graf˚ u ˇr´ıkat, ˇze hrana vych´az´ı z obou sv´ych konc˚ u z´aroveˇ n. 2 s s 3 S S S 2Ss
s2 S S S Ss 3 s2
stupnˇe
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
Definice: Graf je d-regul´arn´ı, pokud vˇsechny jeho vrcholy maj´ı stejn´y 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´y, roven dvojn´asobku poˇctu hran. Petr Hlinˇ en´ y, FI MU Brno, 2014
3 / 24
FI: IB000: Pojem grafu
Bˇ eˇ zn´ e typy graf˚ u Kruˇ znice d´ elky n m´a n ≥ 3 r˚ uzn´ych vrchol˚ u spojen´ych 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
...
Petr Hlinˇ en´ y, FI MU Brno, 2014
4 / 24
FI: IB000: Pojem grafu
Bˇ eˇ zn´ e typy graf˚ u Kruˇ znice d´ elky n m´a n ≥ 3 r˚ uzn´ych vrchol˚ u spojen´ych 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´a n+1 r˚ uzn´ych vrchol˚ u spojen´ych za sebou“ n hranami: ”
Pn
Petr Hlinˇ en´ y, FI MU Brno, 2014
s
1
s
2
s
3
4 / 24
s
4
...
s
n
s
n+1
FI: IB000: Pojem grafu
´ y graf na n ≥ 1 vrcholech m´a n r˚ Upln´ uzn´ych vrchol˚ u spojen´ych 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!
...
Petr Hlinˇ en´ y, FI MU Brno, 2014
5 / 24
FI: IB000: Pojem grafu
´ y graf na n ≥ 1 vrcholech m´a n r˚ Upln´ uzn´ych vrchol˚ u spojen´ych 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´a m + n vrchol˚ Upln´ u ve dvou skupin´ach (partit´ach), pˇriˇcemˇz hranami jsou spojeny vˇsechny m · n dvojice z r˚ uzn´ych 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
Petr Hlinˇ en´ y, FI MU Brno, 2014
3
20
5 / 24
4
30
...
...
m
n0
FI: IB000: Pojem grafu
Hvˇ ezda s n ≥ 1 rameny je zvl´aˇstn´ı n´azev pro u ´pln´y bipartitn´ı graf K1,n :
Sn
Petr Hlinˇ en´ y, FI MU Brno, 2014
4 s
s
3
s2 @ @ @ @s s s1 5 @ @ @ 6 s . . . @s n
6 / 24
FI: IB000: Pojem grafu
Zm´ınka o orientovan´ ych grafech V Lekci 9 si zavedeme tak´e takzvan´e orientovan´e grafy, kter´e kaˇzd´e hranˇe pˇriˇrazuj´ı jist´y smˇer. Form´alnˇe orientovan´e grafy budou m´ıt mnoˇzinu orientovan´ych hran A ⊆ V (G) × V (G) a zobraz´ıme je takto. . .
s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s
s
s
s
7 / 24
s
FI: IB000: Pojem grafu
4.2
Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozum´ıme libovoln´y graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), kter´y m´a 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´a inkluze (ale v´yznam je trochu jin´y).
Petr Hlinˇ en´ y, FI MU Brno, 2014
8 / 24
FI: IB000: Pojem grafu
4.2
Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozum´ıme libovoln´y graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), kter´y m´a 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´a inkluze (ale v´yznam je trochu jin´y). Na n´asleduj´ıc´ım obr´azku vid´ıme zv´yraznˇen´e podmnoˇziny vrchol˚ u hran. Proˇc se vlevo nejedn´a o podgraf? Obr´azek vpravo uˇz podgrafem je.
s
s
s
s
s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s
s
8 / 24
s
s
s
s
s
FI: IB000: Pojem grafu
4.2
Podgrafy a Isomorfismus
Definice: Podgrafem grafu G rozum´ıme libovoln´y graf H na podmnoˇzinˇe vrchol˚ u V (H) ⊆ V (G), kter´y m´a 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´a inkluze (ale v´yznam je trochu jin´y). Na n´asleduj´ıc´ım obr´azku vid´ıme zv´yraznˇen´e podmnoˇziny vrchol˚ u hran. Proˇc se vlevo nejedn´a o podgraf? Obr´azek vpravo uˇz podgrafem je.
s
s
s
s
s
s
s
s
s
s
s
s
Definice: Indukovan´ym podgrafem je podgraf H ⊆ G takov´y, kter´y obsahuje vˇsechny hrany grafu G mezi dvojicemi vrchol˚ u z V (H). Petr Hlinˇ en´ y, FI MU Brno, 2014
8 / 24
FI: IB000: Pojem grafu
Stejnost“ graf˚ u ” s
s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s
s
? =
s s @ @ @ @ s @s
9 / 24
? =
s s @ @ @ @ s @s
FI: IB000: Pojem grafu
Stejnost“ graf˚ u ” 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´e kaˇzd´a dvojice u, v ∈ V (G) je spojen´a hranou v G pr´avˇe, kdyˇz je dvojice f (u), f (v) spojen´a hranou v H. Grafy G a H jsou isomorfn´ı, G ' H, pokud mezi nimi existuje isomorfismus.
Petr Hlinˇ en´ y, FI MU Brno, 2014
9 / 24
FI: IB000: Pojem grafu
Stejnost“ graf˚ u ” 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´e kaˇzd´a dvojice u, v ∈ V (G) je spojen´a hranou v G pr´avˇe, kdyˇz je dvojice f (u), f (v) spojen´a 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´asleduj´ıc´ı ∗ G a H maj´ı stejn´y poˇcet hran, ∗ f zobrazuje na sebe vrcholy stejn´ych stupˇ n˚ u, tj. dG (v) = dH (f (v)).
Petr Hlinˇ en´ y, FI MU Brno, 2014
9 / 24
FI: IB000: Pojem grafu
Stejnost“ graf˚ u ” 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´e kaˇzd´a dvojice u, v ∈ V (G) je spojen´a hranou v G pr´avˇe, kdyˇz je dvojice f (u), f (v) spojen´a 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´asleduj´ıc´ı ∗ G a H maj´ı stejn´y poˇcet hran, ∗ f zobrazuje na sebe vrcholy stejn´ych stupˇ n˚ u, tj. dG (v) = dH (f (v)). s
s s s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s s QQ Q QQ s QQs
9 / 24
FI: IB000: Pojem grafu
Stejnost“ graf˚ u ” 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´e kaˇzd´a dvojice u, v ∈ V (G) je spojen´a hranou v G pr´avˇe, kdyˇz je dvojice f (u), f (v) spojen´a 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´asleduj´ıc´ı ∗ G a H maj´ı stejn´y poˇcet hran, ∗ f zobrazuje na sebe vrcholy stejn´ych stupˇ n˚ u, tj. dG (v) = dH (f (v)). s
s s s
s s QQ Q QQ s QQs
U nakreslen´ych dvou graf˚ u objev´ıme isomorfismus velmi snadno – pod´ıv´ame se, jak si odpov´ıdaj´ı vrcholy stejn´ych stupˇ n˚ u. Petr Hlinˇ en´ y, FI MU Brno, 2014
9 / 24
FI: IB000: Pojem grafu
Pˇr´ıklad 4.5. Jsou n´asleduj´ı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´ymi dvˇema grafy hled´ame isomorfismus, nejprve se pod´ıv´ame, zda maj´ı stejn´y poˇcet vrchol˚ u a hran.
Petr Hlinˇ en´ y, FI MU Brno, 2014
10 / 24
FI: IB000: Pojem grafu
Pˇr´ıklad 4.5. Jsou n´asleduj´ı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´ymi dvˇema grafy hled´ame isomorfismus, nejprve se pod´ıv´ame, zda u a zjist´ıme, maj´ı stejn´y poˇcet vrchol˚ u a hran. Maj´ı. Pak se pod´ıv´ame na stupnˇe vrchol˚ ˇze oba maj´ı stejnou posloupnost stupˇ n˚ u 2, 2, 2, 2, 3, 3.
Petr Hlinˇ en´ y, FI MU Brno, 2014
10 / 24
FI: IB000: Pojem grafu
Pˇr´ıklad 4.5. Jsou n´asleduj´ı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´ymi dvˇema grafy hled´ame isomorfismus, nejprve se pod´ıv´ame, zda u a zjist´ıme, maj´ı stejn´y poˇcet vrchol˚ u a hran. Maj´ı. Pak se pod´ıv´ame 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´yt isomorfn´ı. D´ale tedy nezb´yv´a, neˇz zkouˇset vˇsechny pˇr´ıpustn´e moˇznosti zobrazen´ı isomorfismu z lev´eho grafu do prav´eho.
Petr Hlinˇ en´ y, FI MU Brno, 2014
10 / 24
FI: IB000: Pojem grafu
Pˇr´ıklad 4.5. Jsou n´asleduj´ı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´ymi dvˇema grafy hled´ame isomorfismus, nejprve se pod´ıv´ame, zda u a zjist´ıme, maj´ı stejn´y poˇcet vrchol˚ u a hran. Maj´ı. Pak se pod´ıv´ame 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´yt isomorfn´ı. D´ale tedy nezb´yv´a, neˇz zkouˇset vˇsechny pˇr´ıpustn´e moˇznosti zobrazen´ı isomorfismu z lev´eho grafu do prav´eho. Na lev´em grafu si pro ulehˇcen´ı vˇsimnˇeme, ˇze oba vrcholy stupnˇe tˇri jsou si symetrick´e, proto si bez u ´jmy na obecnosti m˚ uˇzeme vybrat, ˇze vrchol oznaˇcen´y 1 se zobraz´ı na 10 . Druh´y vrchol stupnˇe tˇri, oznaˇcen´y 4, se mus´ı zobrazit na analogick´y vrchol druh´eho 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
FI: IB000: Pojem grafu
D˚ usledek: Stejnost graf˚ u jako isomorfismus!
←→
Graf G
4 s
s3
1 s
s2
Petr Hlinˇ en´ y, FI MU Brno, 2014
Cel´a tˇr´ıda isomorfismu grafu G
4 s
'
s2 @ @ @ @ @ @ @s 3 s 1
11 / 24
3 s
'
s4 @ @ @ @ @ @ @s 2 s 1
FI: IB000: Pojem grafu
D˚ usledek: Stejnost graf˚ u jako isomorfismus!
←→
Graf G
4 s
s3
1 s
s2
Cel´a tˇr´ıda isomorfismu grafu G
4 s
'
s2 @ @ @ @ @ @ @s 3 s 1
3 s
'
s4 @ @ @ @ @ @ @s 2 s 1
Je uveden´y pˇr´ıstup, tj. zamˇen ˇov´an´ı konkr´etn´ıho grafu za celou jeho tˇr´ıdu isomorfismu, v matematice neobvykl´y?
Petr Hlinˇ en´ y, FI MU Brno, 2014
11 / 24
FI: IB000: Pojem grafu
D˚ usledek: Stejnost graf˚ u jako isomorfismus!
←→
Graf G
4 s
s3
1 s
s2
Cel´a tˇr´ıda isomorfismu grafu G
4 s
'
s2 @ @ @ @ @ @ @s 3 s 1
3 s
'
s4 @ @ @ @ @ @ @s 2 s 1
Je uveden´y pˇr´ıstup, tj. zamˇen ˇov´an´ı konkr´etn´ıho grafu za celou jeho tˇr´ıdu isomorfismu, v matematice neobvykl´y? Ne, napˇr´ıklad uˇz v geometrii jste ˇr´ıkali ˇctverec o stranˇe 2“ ” ˇci jednotkov´y kruh“ a podobnˇe, aniˇz jste mˇeli na mysli konkr´etn´ı obr´azek, n´ybrˇz celou ” tˇr´ıdu vˇsech tˇechto shodn´ych objekt˚ u.
Petr Hlinˇ en´ y, FI MU Brno, 2014
11 / 24
FI: IB000: Pojem grafu
6 s
Dalˇs´ı grafov´ e pojmy
s 1 S S S S 2 Ss
Definice: Mˇejme libovoln´y graf G.
Petr Hlinˇ en´ y, FI MU Brno, 2014
12 / 24
s5 S S S S Ss 4 s3
FI: IB000: Pojem grafu
6 s
Dalˇs´ı grafov´ e pojmy
s 1 S S S S 2 Ss
Definice: Mˇejme libovoln´y graf G.
s5 S S S S Ss 4 s3
∗ Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e kruˇznici, ˇr´ık´ame kruˇznice v G. ∗ Speci´alnˇe ˇr´ık´ame troj´ uheln´ık kruˇznici d´elky 3.
Petr Hlinˇ en´ y, FI MU Brno, 2014
12 / 24
FI: IB000: Pojem grafu
6 s
Dalˇs´ı grafov´ e pojmy
s 1 S S S S 2 Ss
Definice: Mˇejme libovoln´y graf G.
s5 S S S S Ss 4 s3
∗ Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e kruˇznici, ˇr´ık´ame kruˇznice v G. ∗ Speci´alnˇe ˇr´ık´ame troj´ uheln´ık kruˇznici d´elky 3. ∗ Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e cestˇe, ˇr´ık´ame cesta v G.
Petr Hlinˇ en´ y, FI MU Brno, 2014
12 / 24
FI: IB000: Pojem grafu
6 s
Dalˇs´ı grafov´ e pojmy
s 1 S S S S 2 Ss
Definice: Mˇejme libovoln´y graf G.
s5 S S S S Ss 4 s3
∗ ∗ ∗ ∗
Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e kruˇznici, ˇr´ık´ame kruˇznice v G. Speci´alnˇe ˇr´ık´ame troj´ uheln´ık kruˇznici d´elky 3. Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e cestˇe, ˇr´ık´ame cesta v G. Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´emu u ´pln´emu grafu, ˇr´ık´ame klika v G. ∗ Podmnoˇzinˇe vrchol˚ u X ⊆ V (G), mezi kter´ymi nevedou v G v˚ ubec ˇz´adn´e hrany, ˇr´ık´ame nez´avisl´a mnoˇzina X v G.
Petr Hlinˇ en´ y, FI MU Brno, 2014
12 / 24
FI: IB000: Pojem grafu
6 s
Dalˇs´ı grafov´ e pojmy
s 1 S S S S 2 Ss
Definice: Mˇejme libovoln´y graf G.
s5 S S S S Ss 4 s3
∗ ∗ ∗ ∗
Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e kruˇznici, ˇr´ık´ame kruˇznice v G. Speci´alnˇe ˇr´ık´ame troj´ uheln´ık kruˇznici d´elky 3. Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e cestˇe, ˇr´ık´ame cesta v G. Podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´emu u ´pln´emu grafu, ˇr´ık´ame klika v G. ∗ Podmnoˇzinˇe vrchol˚ u X ⊆ V (G), mezi kter´ymi nevedou v G v˚ ubec ˇz´adn´e hrany, ˇr´ık´ame nez´avisl´a mnoˇzina X v G. ∗ Indukovan´emu podgrafu H ⊆ G, kter´y je isomorfn´ı nˇejak´e kruˇznici, ˇr´ık´ame indukovan´a kruˇznice v G. Petr Hlinˇ en´ y, FI MU Brno, 2014
12 / 24
FI: IB000: Pojem grafu
4.3
Souvislost graf˚ u, komponenty
D˚ uleˇzitou glob´aln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv pod´el jeho hran, neboli po cest´ach v grafu.
Petr Hlinˇ en´ y, FI MU Brno, 2014
13 / 24
FI: IB000: Pojem grafu
4.3
Souvislost graf˚ u, komponenty
D˚ uleˇzitou glob´aln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv pod´el jeho hran, neboli po cest´ach v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovoln´eho grafu G takovou, ˇze pro dva vrcholy x ∼ y pr´avˇe kdyˇz existuje v G cesta zaˇc´ınaj´ıc´ı v x a konˇc´ıc´ı v y. Pak ∼ je relac´ı ekvivalence.
Petr Hlinˇ en´ y, FI MU Brno, 2014
13 / 24
FI: IB000: Pojem grafu
4.3
Souvislost graf˚ u, komponenty
D˚ uleˇzitou glob´aln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv pod´el jeho hran, neboli po cest´ach v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovoln´eho grafu G takovou, ˇze pro dva vrcholy x ∼ y pr´avˇ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´y vrchol je spojen´y s´am se sebou cestou d´elky 0.
Petr Hlinˇ en´ y, FI MU Brno, 2014
13 / 24
FI: IB000: Pojem grafu
4.3
Souvislost graf˚ u, komponenty
D˚ uleˇzitou glob´aln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv pod´el jeho hran, neboli po cest´ach v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovoln´eho grafu G takovou, ˇze pro dva vrcholy x ∼ y pr´avˇ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´y vrchol je spojen´y s´am se sebou cestou d´elky 0. • Symetrick´a je tak´e, protoˇze cestu z x do y snadno v neorientovan´em grafu obr´at´ıme na cestu z y do x.
Petr Hlinˇ en´ y, FI MU Brno, 2014
13 / 24
FI: IB000: Pojem grafu
4.3
Souvislost graf˚ u, komponenty
D˚ uleˇzitou glob´aln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv pod´el jeho hran, neboli po cest´ach v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovoln´eho grafu G takovou, ˇze pro dva vrcholy x ∼ y pr´avˇ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´y vrchol je spojen´y s´am se sebou cestou d´elky 0. • Symetrick´a je tak´e, protoˇze cestu z x do y snadno v neorientovan´em grafu obr´at´ı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´yt cesta; mohou se navz´ajem prot´ınat.
Petr Hlinˇ en´ y, FI MU Brno, 2014
13 / 24
FI: IB000: Pojem grafu
4.3
Souvislost graf˚ u, komponenty
D˚ uleˇzitou glob´aln´ı vlastnost´ı graf˚ u je souvislost, tedy moˇznost se v nich pohybovat odkudkoliv kamkoliv pod´el jeho hran, neboli po cest´ach v grafu. Lema 4.6. Mˇejme relaci ∼ na mnoˇzinˇe vrchol˚ u V (G) libovoln´eho grafu G takovou, ˇze pro dva vrcholy x ∼ y pr´avˇ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´y vrchol je spojen´y s´am se sebou cestou d´elky 0. • Symetrick´a je tak´e, protoˇze cestu z x do y snadno v neorientovan´em grafu obr´at´ı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´yt cesta; mohou se navz´ajem prot´ınat. Avˇsak pokud oznaˇc´ıme P 0 ⊆ P ˇc´ast cesty z x do prvn´ıho vrcholu z v pr˚ uniku s Q a Q0 ⊆ Q zbytek druh´e 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
FI: IB000: Pojem grafu
Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence v´yˇse popsan´e (Lema 7.6) relace ∼ na V (G).
Petr Hlinˇ en´ y, FI MU Brno, 2014
14 / 24
FI: IB000: Pojem grafu
Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence v´yˇse popsan´e (Lema 7.6) relace ∼ na V (G). Jinak se tak´e komponentami souvislosti mysl´ı podgrafy indukovan´e na tˇechto tˇr´ıd´ach ekvivalence.
Petr Hlinˇ en´ y, FI MU Brno, 2014
14 / 24
FI: IB000: Pojem grafu
Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence v´yˇse popsan´e (Lema 7.6) relace ∼ na V (G). Jinak se tak´e komponentami souvislosti mysl´ı podgrafy indukovan´e na tˇechto tˇr´ıd´ach ekvivalence. Pod´ıvejte se, kolik komponent souvislosti m´a tento graf:
s
s @ @ @ @ @s
s
s
s
s
s @ @ @ @ @s
s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s
14 / 24
s s
FI: IB000: Pojem grafu
Definice 4.7. Komponentami souvislosti grafu G nazveme tˇr´ıdy ekvivalence v´yˇse popsan´e (Lema 7.6) relace ∼ na V (G). Jinak se tak´e komponentami souvislosti mysl´ı podgrafy indukovan´e na tˇechto tˇr´ıd´ach ekvivalence. Pod´ıvejte se, kolik komponent souvislosti m´a tento graf:
s
s @ @ @ @ @s
s
s
s
s
s @ @ @ @ @s
s
s
s s
Vid´ıte v obr´azku vˇsechny tˇri komponenty? Jedna z nich je izolovan´ym vrcholem, druh´a hranou (tj. grafem isomorfn´ım K2 ) a tˇret´ı je to zb´yvaj´ıc´ı.
Petr Hlinˇ en´ y, FI MU Brno, 2014
14 / 24
FI: IB000: Pojem grafu
Definice 4.8. Graf G je souvisl´ y pokud je G tvoˇren´y nejv´yˇse jednou komponentou souvislosti, tj. pokud kaˇzd´e dva vrcholy G jsou spojen´e cestou.
Petr Hlinˇ en´ y, FI MU Brno, 2014
15 / 24
FI: IB000: Pojem grafu
Definice 4.8. Graf G je souvisl´ y pokud je G tvoˇren´y nejv´yˇse jednou komponentou souvislosti, tj. pokud kaˇzd´e dva vrcholy G jsou spojen´e cestou. Kter´y z tˇechto dvou graf˚ u je souvisl´y? s s s !s QQ QQ !! ! ! QQ QQ !! !! QQ QQ ! ! Q !!! QQQ Q ! QQ Q ! QQ !! ! QQ ! QQ QQ !! ! ! Qs ! Qs s s
Petr Hlinˇ en´ y, FI MU Brno, 2014
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
FI: IB000: Pojem grafu
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´ymi znaky strom˚ u je absence kruˇznic a souvislost. . .
Petr Hlinˇ en´ y, FI MU Brno, 2014
16 / 24
FI: IB000: Pojem grafu
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´ymi znaky strom˚ u je absence kruˇznic a souvislost. . .
Definice 4.9. Strom je jednoduch´y souvisl´y graf T bez kruˇznic.
Petr Hlinˇ en´ y, FI MU Brno, 2014
16 / 24
FI: IB000: Pojem grafu
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´ymi znaky strom˚ u je absence kruˇznic a souvislost. . .
Definice 4.9. Strom je jednoduch´y souvisl´y graf T bez kruˇznic. Les je jednoduch´y graf bez kruˇznic (nemus´ı b´yt souvisl´y). Komponenty souvislosti lesa jsou stromy. Jeden vrchol bez hran a pr´azdn´y graf jsou tak´e stromy. Grafy bez kruˇznic tak´e obecnˇe naz´yv´ame acyklick´e. Petr Hlinˇ en´ y, FI MU Brno, 2014
16 / 24
FI: IB000: Pojem grafu
Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1.
Petr Hlinˇ en´ y, FI MU Brno, 2014
17 / 24
FI: IB000: Pojem grafu
Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvisl´y 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´y vrchol v.
Petr Hlinˇ en´ y, FI MU Brno, 2014
17 / 24
FI: IB000: Pojem grafu
Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvisl´y 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´y vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı cestu S v T zaˇc´ınaj´ıc´ı ve v: ∗ S zaˇcne libovolnou hranou vych´azej´ıc´ı z v;
Petr Hlinˇ en´ y, FI MU Brno, 2014
17 / 24
FI: IB000: Pojem grafu
Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvisl´y 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´y vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı cestu S v T zaˇc´ınaj´ıc´ı ve v: ∗ S zaˇcne libovolnou hranou vych´azej´ıc´ı z v; ∗ v kaˇzd´em dalˇs´ım vrcholu u, do kter´eho se dostaneme a m´a 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 `
Petr Hlinˇ en´ y, FI MU Brno, 2014
cc ccs ...
17 / 24
f s s
FI: IB000: Pojem grafu
Vlastnosti strom˚ u Lema 4.10. Strom s v´ıce neˇz jedn´ım vrcholem obsahuje vrchol stupnˇe 1. D˚ ukaz: Souvisl´y 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´y vrchol v. Sestroj´ıme nyn´ı co nejdelˇs´ı cestu S v T zaˇc´ınaj´ıc´ı ve v: ∗ S zaˇcne libovolnou hranou vych´azej´ıc´ı z v; ∗ v kaˇzd´em dalˇs´ım vrcholu u, do kter´eho se dostaneme a m´a 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´e zopakoval nˇekter´y vrchol, z´ıskali bychom kruˇznici. Proto cesta S mus´ı jednou skonˇcit v nˇejak´em vrcholu stupnˇe 1 v T . 2
Petr Hlinˇ en´ y, FI MU Brno, 2014
17 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.11. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1.
Petr Hlinˇ en´ y, FI MU Brno, 2014
18 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.11. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1. D˚ ukaz: Toto tvrzen´ı dok´aˇzeme indukc´ı podle n. ∗ Strom s jedn´ım vrcholem m´a n − 1 = 0 hran.
Petr Hlinˇ en´ y, FI MU Brno, 2014
18 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.11. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1. D˚ ukaz: Toto tvrzen´ı dok´aˇzeme indukc´ı podle n. ∗ Strom s jedn´ım vrcholem m´a n − 1 = 0 hran.
∗ 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´a T vrchol v stupnˇe 1. Oznaˇcme T 0 = T − v graf vznikl´y z T odebr´an´ım vrcholu v.
Petr Hlinˇ en´ y, FI MU Brno, 2014
18 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.11. Strom na n vrcholech m´a pˇresnˇe n − 1 hran pro n ≥ 1. D˚ ukaz: Toto tvrzen´ı dok´aˇzeme indukc´ı podle n. ∗ Strom s jedn´ım vrcholem m´a n − 1 = 0 hran.
∗ 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´a T vrchol v stupnˇe 1. Oznaˇcme T 0 = T − v graf vznikl´y z T odebr´an´ım vrcholu v. Pak T 0 je tak´e souvisl´y bez kruˇznic, tud´ıˇz strom na n − 1 vrcholech. Dle indukˇcn´ıho pˇredpokladu T 0 m´a n − 1 − 1 2 hran, a proto T m´a n − 1 − 1 + 1 = n − 1 hran.
Petr Hlinˇ en´ y, FI MU Brno, 2014
18 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.12. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta.
Petr Hlinˇ en´ y, FI MU Brno, 2014
19 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.12. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta.
D˚ ukaz: Jelikoˇz strom T je souvisl´y dle definice, mezi libovoln´ymi dvˇema vrcholy u, v vede nˇejak´a cesta.
Petr Hlinˇ en´ y, FI MU Brno, 2014
19 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.12. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta.
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´y dle definice, mezi libovoln´ymi dvˇema vrcholy u, v vede nˇejak´a cesta. Pokud by existovaly dvˇe r˚ uzn´e cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrick´y rozd´ıl, podgraf H = P1 ∆P2 s nepr´azdnou mnoˇzinou hran, kde H zˇrejmˇe m´a vˇsechny stupnˇe sud´e.
Petr Hlinˇ en´ y, FI MU Brno, 2014
19 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.12. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta.
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´y dle definice, mezi libovoln´ymi dvˇema vrcholy u, v vede nˇejak´a cesta. Pokud by existovaly dvˇe r˚ uzn´e cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrick´y rozd´ıl, podgraf H = P1 ∆P2 s nepr´azdnou mnoˇzinou hran, kde H zˇrejmˇe m´a vˇsechny stupnˇe sud´e. Na druhou stranu se vˇsak podgraf stromu mus´ı opˇet skl´adat z komponent strom˚ u, a tud´ıˇz obsahovat vrchol stupnˇe 1 podle Lematu 7.10, spor.
Petr Hlinˇ en´ y, FI MU Brno, 2014
19 / 24
FI: IB000: Pojem grafu
Vˇ eta 4.12. Mezi kaˇzd´ymi dvˇema vrcholy stromu vede pr´avˇe jedin´a cesta.
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´y dle definice, mezi libovoln´ymi dvˇema vrcholy u, v vede nˇejak´a cesta. Pokud by existovaly dvˇe r˚ uzn´e cesty P1 , P2 mezi u, v, tak bychom vzali jejich symetrick´y rozd´ıl, podgraf H = P1 ∆P2 s nepr´azdnou mnoˇzinou hran, kde H zˇrejmˇe m´a vˇsechny stupnˇe sud´e. Na druhou stranu se vˇsak podgraf stromu mus´ı opˇet skl´adat z komponent strom˚ u, a tud´ıˇz obsahovat vrchol stupnˇe 1 2 podle Lematu 7.10, spor. D˚ usledek 4.13. Pˇrid´an´ım jedn´e hrany do stromu vznikne pr´avˇe jedna kruˇznice.
Petr Hlinˇ en´ y, FI MU Brno, 2014
19 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s
s
s
s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s s
20 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s " " "" "" " " s""
s
s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s s
20 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s " " "" "" " " " s" s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s
s s
20 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s " " "" "" " " " s" s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s D D D D D D D D D D Ds
20 / 24
s
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s " " "" "" " " " s" s
Petr Hlinˇ en´ y, FI MU Brno, 2014
s D s D D % D % D % D % D D %% D D % Ds%
20 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s "``````` " ````s " "" " D s "" D D s"" % D % D % D % D D %% D D % Ds% s
Petr Hlinˇ en´ y, FI MU Brno, 2014
20 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s "``````` " ````s " "" " D s "" D D s"" % D % D % D % D D %% D D % Ds% s
Petr Hlinˇ en´ y, FI MU Brno, 2014
20 / 24
FI: IB000: Pojem grafu
Alternativn´ı charakterizace strom˚ u Na dan´e mnoˇzinˇe vrchol˚ u je (vzhledem k inkluzi mnoˇzin hran) strom • minim´aln´ı souvisl´y graf (plyne z Vˇety 7.12) • a z´aroveˇ n maxim´aln´ı acyklick´y graf (plyne z D˚ usledku 7.13). s "``````` " ````s " "" " D s "" D D s"" % D % D % D % D D %% D D % Ds% s
Petr Hlinˇ en´ y, FI MU Brno, 2014
20 / 24
FI: IB000: Pojem grafu
4.5
Jedn´ım tahem – Eulerovsk´ e grafy
Pravd. nejstarˇs´ı zaznamenan´y v´ysledek teorie graf˚ u poch´az´ı od L. Eulera – jedn´a se o slavn´ych 7 most˚ u v Kr´alovci / K¨ onigsbergu / dneˇsn´ım Kaliningradˇe.
O jak´y probl´em se tehdy jednalo? Mˇestˇst´ı radn´ı chtˇeli vˇedˇet, zda mohou suchou nohou pˇrej´ıt po kaˇzd´em ze sedmi vyznaˇcen´ych most˚ u pr´avˇe jednou. Petr Hlinˇ en´ y, FI MU Brno, 2014
21 / 24
FI: IB000: Pojem grafu
Sled a tah v grafu Definice: Sledem d´elky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn )
Petr Hlinˇ en´ y, FI MU Brno, 2014
22 / 24
FI: IB000: Pojem grafu
Sled a tah v grafu Definice: Sledem d´elky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn ) , ve kter´e vˇzdy hrana ei m´a koncov´e vrcholy vi−1 , vi . Sled je vlastnˇe proch´azka po hran´ach grafu z u do v. Pˇr´ıkladem sledu m˚ uˇze b´yt pr˚ uchod IP paketu internetem (vˇcetnˇe cyklen´ı).
Petr Hlinˇ en´ y, FI MU Brno, 2014
22 / 24
FI: IB000: Pojem grafu
Sled a tah v grafu Definice: Sledem d´elky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn ) , ve kter´e vˇzdy hrana ei m´a koncov´e vrcholy vi−1 , vi . Sled je vlastnˇe proch´azka po hran´ach grafu z u do v. Pˇr´ıkladem sledu m˚ uˇze b´yt pr˚ uchod IP paketu internetem (vˇcetnˇe cyklen´ı).
Definice: Tah je sled v grafu bez opakov´an´ı hran.
Petr Hlinˇ en´ y, FI MU Brno, 2014
22 / 24
FI: IB000: Pojem grafu
Sled a tah v grafu Definice: Sledem d´elky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn ) , ve kter´e vˇzdy hrana ei m´a koncov´e vrcholy vi−1 , vi . Sled je vlastnˇe proch´azka po hran´ach grafu z u do v. Pˇr´ıkladem sledu m˚ uˇze b´yt pr˚ uchod IP paketu internetem (vˇcetnˇe cyklen´ı).
Definice: Tah je sled v grafu bez opakov´an´ı hran. Uzavˇren´y tah je tahem, kter´y konˇc´ı ve vrcholu, ve kter´em zaˇcal. Otevˇren´y tah je tahem, kter´y konˇc´ı v jin´em vrcholu, neˇz ve kter´em zaˇcal. Zn´ate dˇetsk´e kreslen´ı jedn´ım tahem“? Ano, to je v podstatˇe i n´aˇs tah (v nakresl. grafu). ”
Petr Hlinˇ en´ y, FI MU Brno, 2014
22 / 24
FI: IB000: Pojem grafu
Sled a tah v grafu Definice: Sledem d´elky n v grafu G rozum´ıme posloupnost vrchol˚ u a hran (v0 , e1 , v1 , e2 , v2 , . . . , en , vn ) , ve kter´e vˇzdy hrana ei m´a koncov´e vrcholy vi−1 , vi . Sled je vlastnˇe proch´azka po hran´ach grafu z u do v. Pˇr´ıkladem sledu m˚ uˇze b´yt pr˚ uchod IP paketu internetem (vˇcetnˇe cyklen´ı).
Definice: Tah je sled v grafu bez opakov´an´ı hran. Uzavˇren´y tah je tahem, kter´y konˇc´ı ve vrcholu, ve kter´em zaˇcal. Otevˇren´y tah je tahem, kter´y konˇc´ı v jin´em vrcholu, neˇz ve kter´em zaˇcal. Zn´ate dˇetsk´e kreslen´ı jedn´ım tahem“? Ano, to je v podstatˇe i n´aˇs tah (v nakresl. grafu). ”
Fakt: Cesta je pr´avˇe otevˇren´y tah bez opakov´an´ı vrchol˚ u. Kruˇznice je pr´avˇe uzavˇren´y tah bez opakov´an´ı vrchol˚ u. Petr Hlinˇ en´ y, FI MU Brno, 2014
22 / 24
FI: IB000: Pojem grafu
Eulerova charakterizace Onen slavn´y v´ysledek teorie graf˚ u od Leonharda Eulera pot´e zn´ı n´asledovnˇe. h h @ @ @ @ @ @ @h h @ @ @ @ @h @h
s s @ @ @ @ @s s @ @ @ @ @ @s @s
Petr Hlinˇ en´ y, FI MU Brno, 2014
23 / 24
FI: IB000: Pojem grafu
Eulerova charakterizace Onen slavn´y v´ysledek teorie graf˚ u od Leonharda Eulera pot´e zn´ı n´asledovnˇe. h h @ @ @ @ @ @ @h h @ @ @ @ @h @h
s s @ @ @ @ @s s @ @ @ @ @ @s @s
Vˇ eta 4.14. Graf G lze nakreslit jedn´ım uzavˇren´ym tahem pr´avˇe kdyˇz G je souvisl´y a vˇsechny vrcholy v G jsou sud´eho stupnˇe.
Petr Hlinˇ en´ y, FI MU Brno, 2014
23 / 24
FI: IB000: Pojem grafu
Eulerova charakterizace Onen slavn´y v´ysledek teorie graf˚ u od Leonharda Eulera pot´e zn´ı n´asledovnˇe. h h @ @ @ @ @ @ @h h @ @ @ @ @h @h
s s @ @ @ @ @s s @ @ @ @ @ @s @s
Vˇ eta 4.14. Graf G lze nakreslit jedn´ım uzavˇren´ym tahem pr´avˇe kdyˇz G je souvisl´y a vˇsechny vrcholy v G jsou sud´eho stupnˇe. D˚ usledek 4.15. Graf G lze nakreslit jedn´ım otevˇren´ym tahem pr´avˇe kdyˇz G je souvisl´y a vˇsechny vrcholy v G aˇz na dva jsou sud´eho stupnˇe.
Petr Hlinˇ en´ y, FI MU Brno, 2014
23 / 24
FI: IB000: Pojem grafu
D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇren´ym tahem, tak je zˇrejmˇe souvisl´y a nav´ıc m´a kaˇzd´y stupeˇ n sud´y, nebot’ uzavˇren´y tah kaˇzd´ym pr˚ uchodem vrcholem ubere“ dvˇe hrany. ”
Petr Hlinˇ en´ y, FI MU Brno, 2014
24 / 24
FI: IB000: Pojem grafu
D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇren´ym tahem, tak je zˇrejmˇe souvisl´y a nav´ıc m´a kaˇzd´y stupeˇ n sud´y, nebot’ uzavˇren´y tah kaˇzd´ym pr˚ uchodem vrcholem ubere“ dvˇe hrany. ” Naopak zvol´ıme mezi vˇsemi uzavˇren´ymi 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´em pˇredpokl´adejme, ˇze je nepr´azdn´y. Jelikoˇz G0 m´a takt´eˇz vˇsechny stupnˇe sud´e, je (z indukˇcn´ıho pˇredpokladu) libovoln´a jeho komponenta C ⊆ G0 nakreslen´a jedn´ım uzavˇren´ym tahem TC .
Petr Hlinˇ en´ y, FI MU Brno, 2014
24 / 24
FI: IB000: Pojem grafu
D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇren´ym tahem, tak je zˇrejmˇe souvisl´y a nav´ıc m´a kaˇzd´y stupeˇ n sud´y, nebot’ uzavˇren´y tah kaˇzd´ym pr˚ uchodem vrcholem ubere“ dvˇe hrany. ” Naopak zvol´ıme mezi vˇsemi uzavˇren´ymi 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´em pˇredpokl´adejme, ˇze je nepr´azdn´y. Jelikoˇz G0 m´a takt´eˇz vˇsechny stupnˇe sud´e, je (z indukˇcn´ıho pˇredpokladu) libovoln´a jeho komponenta C ⊆ G0 nakreslen´a jedn´ım uzavˇren´ym tahem TC . – Vzhledem k souvislosti grafu G kaˇzd´a komponenta C ⊆ G0 prot´ın´a n´aˇs tah T v nˇekter´em 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´eho T .
Petr Hlinˇ en´ y, FI MU Brno, 2014
24 / 24
FI: IB000: Pojem grafu
D˚ ukaz: Dokazujeme oba smˇery ekvivalence. Pokud lze G nakreslit jedn´ım uzavˇren´ym tahem, tak je zˇrejmˇe souvisl´y a nav´ıc m´a kaˇzd´y stupeˇ n sud´y, nebot’ uzavˇren´y tah kaˇzd´ym pr˚ uchodem vrcholem ubere“ dvˇe hrany. ” Naopak zvol´ıme mezi vˇsemi uzavˇren´ymi 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´em pˇredpokl´adejme, ˇze je nepr´azdn´y. Jelikoˇz G0 m´a takt´eˇz vˇsechny stupnˇe sud´e, je (z indukˇcn´ıho pˇredpokladu) libovoln´a jeho komponenta C ⊆ G0 nakreslen´a jedn´ım uzavˇren´ym tahem TC . – Vzhledem k souvislosti grafu G kaˇzd´a komponenta C ⊆ G0 prot´ın´a n´aˇs tah T v nˇekter´em 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´eho T . 2 D˚ ukaz d˚ usledku: Necht’ u, v jsou dva vrcholy grafu G maj´ıc´ı lich´y stupeˇ n, neboli dva (pˇredpokl´adan´e) konce otevˇren´eho tahu pro G. Do G nyn´ı pˇrid´ame nov´y vrchol w spojen´y hranami s u a v. T´ım jsme n´aˇs pˇr´ıpad pˇrevedli na pˇredchoz´ı pˇr´ıpad grafu se vˇsemi sud´ymi stupni. 2 Petr Hlinˇ en´ y, FI MU Brno, 2014
24 / 24
FI: IB000: Pojem grafu
