MA2BP_PDM1 Diskrétní matematika 1
2. Souvislost, izomorfismus
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
26. 9. 2017
4 ^ >■   <      ► 4
Program prezentace
H Sled, tah, cesta
Q Souvislost grafu
Q Artikulace, most
□ 2-souvislost grafu
H Izomorfismus grafů
26. 9. 2017       2 / 46
Sled, tah, cesta
Definice 1.8 (MILKOVA)
H Sled délky /c, k > 0, v grafu G je posloupnost (vq, ei, vi,..., e/c, v/c), kde e,- = v,-}, / = 1,..., k.
B Tah délky /c, /c > 0, v grafu G je sled délky /c s navzájem různými hranami, tj. pro / ^ j platí e,- 7^ e/.
B Cesta délky /c,/c > 0, v grafu G je sled délky k s navzájem různými vrcholy, tj. pro / 7^ j platí 17 7^ vj.
□ Uzavřený sled délky /c, k > 0, v grafu G je sled délky /c, ve kterém H Uzavřený tah délky /c, k > 0, v grafu G je tah délky /c, ve kterém
□ Kružnice délky /c, /c > 3, v grafu G je posloupnost
(vo, ei? VU - - - -> ek> vo), kde €i = {17-1, v/}, / = 1,..., /c - 1, e/c = v0} a pro / ^7 platí v, ^ vj.
26. 9. 2017       3 / 46
Sled, tah, cesta (2)
Poznámka:
■ Sled jakéhokoliv typu budeme zapisovat jen jako posloupnost vrcholů.
■ Tah je sled, kde se neopakují hrany. Cesta je sled, kde se neopakují vrcholy.
■ Kružnice je uzavřený sled, v němž se neopakují "vnitřní" vrcholy.
■ Kružnice C3 se nazývá trojúhelník.
26. 9. 2017       4 / 46
Příklad
V následujícím grafu G určete libovolný H sled délky 8
Q tah délky 6, který není cestou & cestu délky 5 □ kružnici délky 5
26. 9. 2017       5 / 46
Souvislý graf
Definice 1.9 (MILKOVA)
□ Souvislý graf je graf, ve kterém mezi každými dvěma vrcholy existuje cesta.
B Komponenta grafu G je každý maximální souvislý podgraf grafu G, tj. souvislý podgraf, který není podgrafem žádného jiného souvislého podgraf u.
Příklad: Existují dva různé grafy se skóre (2, 2, 2, 2, 2, 2), jeden je souvislý (kružnice Q), druhý nesouvislý se dvěma komponentami (dvě kružnice C3), viz obrázek.
26. 9. 2017       6 / 46
Odebrání vrcholu, hrany
Definice 1.10 (MILKOVA): Nechť je dán graf G = {V, E), vrchol v G V a hrana e £ E.
□ Graf G — v je graf, který dostaneme z grafu G odebráním vrcholu v a všech hran s ním incidentních, tj. G — v = (V\{v},{E £ E \ v £ e}).
B Graf G — e je graf získaný z grafu G odebráním hrany e, tj. G-e = (V,E\{e}).
26. 9. 2017       7 / 46
Odebrání vrcholu, hrany
Definice 1.10 (MILKOVA): Nechť je dán graf G = {V, E), vrchol v G V a hrana e £ E.
□ Graf G — v je graf, který dostaneme z grafu G odebráním vrcholu v a všech hran s ním incidentních, tj. G — v = (V\{v},{E G E \ v £ e}).
B Graf G — e je graf získaný z grafu G odebráním hrany e, tj.
G-e = (V,E\{e})._
Příklad: Z grafu na obrázku postupně odeberte vrchol 2 a hranu {3,5}.
G:
Odebrání vrcholu, hrany (řešení příkladu)
Řešení příkladu: Odebrání vrcholu 2.
Odebrání vrcholu, hrany (řešení příkladu)
Řešení příkladu: Odebrání hrany {3,5}.
G:
26. 9. 2017       9 / 46
Odebrání vrcholu, hrany (řešení příkladu)
Řešení příkladu: Výsledný graf.
G:
26. 9. 2017       10 / 46
Artikulace, most
Definice 1.11 (MILKOVA): Nechť je dán graf G = (V, E), vrchol v E V
a hrana e £ E.
□ Hrana e je most grafu G, jestliže graf G — e má více komponent než
graf G.
B Vrchol v je artikulace grafu G, jestliže graf G — v má více komponent než graf G.
Poznámka:
■ Vrcholy grafu stupně 1 či 0 nemohou být artikulacemi.
■ Nechť {u, v} je most grafu G. Pokud dc(u) > 1 (resp. dc(v) > 1), pak vrchol u (resp. vrchol v) je artikulace.
■ Vrchol, který je artikulací, nemusí být koncovým vrcholem mostu.
■ Vyjmutím mostu zvětšíme počet komponent právě o jednu.
■ Vyjmutím artikulace u grafu G zvětšíme počet komponent minimálně o jednu, max. o číslo rovnající se dc(u) — 1.
v   7 ^)c\o
26. 9. 2017       11 / 46
Procvičení pojmů
Příklad 1: V grafu G určete všechny komponenty, mosty a artikulace.
Příklad 2: Nakreslete souvislý graf G se šesti vrcholy včetně artikulace u takový, že G — u bude obsahovat pět komponent.
26. 9. 2017       12 / 46
Řešení příkladu 1 - komponenty
Komponenty grafu G\ dva podgrafy indukované množinami
26. 9. 2017       13 / 46
Řešení příkladu 1 - mosty
Odebráním hrany {c/, h} vznikají tři komponenty (namísto dvou) - {c/, h} je most.
g: ® ©
Řešení příkladu 1 - mosty
Odebráním hrany {dj} vznikají znovu tři komponenty - {dj} je most.
26. 9. 2017       15 / 46
Řešení příkladu 1 - mosty
Odebráním hrany {/, /} vznikají opět tři komponenty - {/, /} je most.
□    g ► < -e ► < =
26. 9. 2017       16 / 46
Řešení příkladu 1 - artikulace
Odebráním vrcholu c a jeho hran vznikají tři komponenty - c je artikulace.
26. 9. 2017       17 / 46
Řešení příkladu 1 - artikulace
Odebráním vrcholu d a jeho hran vznikají čtyři komponenty artikulace.
□ i3i
Řešení příkladu 1 - artikulace
Odebráním vrcholu j a jeho hran vznikají tři komponenty — j je artikulace.
26. 9. 2017       19 / 46
Řešení Příkladu 1:
Komponenty grafu G\ dva podgrafy indukované množinami
■ {a,b,c,d,e,f,h,ij}
■ {g}
Mosty grafu G: {d,h},{dj},{j,i} Artikulace grafu G\ c,dj
Řešení příkladu 2: souvislý graf s pěti vrcholy a artikulací u, jejímž odebráním vznikne nesouvislý graf G — u o pěti komponentách.
Řešení příkladů
Řešení Příkladu 1:
Komponenty grafu G\ dva podgrafy indukované množinami
■ {a,b,c,d,e,f,h,ij}
■ {g}
Mosty grafu G\ {d, h},{dj},{j, /} Artikulace grafu G\ c,dj
Řešení příkladu 2: souvislý graf s pěti vrcholy a artikulací u, jejímž odebráním vznikne nesouvislý graf G — u o pěti komponentách.
(MILKOVA, Tvrzení 1.2)
Nechť souvislý graf G obsahuje kružnici C a e je libovolná hrana C. Pak též G — e je souvislý.
(MILKOVA, Tvrzení 1.3)
Nechť je dán graf G = (\/, E) a hrana e = {v, w} £ E. Pak platí: Je-li G — e souvislý, pak v G existuje kružnice obsahující hranu e.
(MILKOVA, Důsledek 1.2)
Hrana grafu je buď most nebo leží na nějaké kružnici grafu.
2-souvislost grafu
Definice 1.12 (MILKOVA):
□ 2-souvislý graf je graf, který neobsahuje artikulaci.
B Blok grafu G (2-souvislá komponenta) je každý maximální 2-souvislý podgraf grafu G, tj. 2-souvislý podgraf G, který není podgrafem žádného jiného 2-souvislého podgrafu.
Poznámka: Graf G = (\/, E) je 2-souvislý, právě když pro libovolný vrchol v G V zůstane graf G — v souvislý.
Příklad: Každý úplný graf je 2-souvislý.
26. 9. 2017       22 / 46
Vysvětlení definice bloku
Příklad: Uvažujme graf na obrázku a příklady podgrafů indukovaných různými množinami vrcholů. Určete, zdá se jedná o bloky.
Bi je podgraf indukovaný množinou vrcholů {/7, dj, /}.
26. 9. 2017       23 / 46
Vysvětlení definice bloku
Příklad: Uvažujme graf na obrázku a příklady podgrafů indukovaných různými množinami vrcholů. Určete, zdá se jedná o bloky.
Bi je podgraf indukovaný množinou vrcholů {/7, dj, /}.
Odpověď: Ne, nejedná se o blok, protože např. B\ — d má více komponent než B\.
26. 9. 2017       23 / 46
Vysvětlení definice bloku
Příklad: Uvažujme graf na obrázku a příklady podgrafů indukovaných různými množinami vrcholů. Určete, zdá se jedná o bloky.
62 je podgraf indukovaný množinou vrcholů {a, b, c, d}.
26. 9. 2017       24 / 46
Vysvětlení definice bloku
Příklad: Uvažujme graf na obrázku a příklady podgrafů indukovaných různými množinami vrcholů. Určete, zdá se jedná o bloky.
62 je podgraf indukovaný množinou vrcholů {a, b, c, d}.
Odpověď: Ano, jedná se o blok, odebráním libovolného z těchto čtyř vrcholů zůstane podgraf indukovaný zbylými uzly souvislý.
26. 9. 2017       24 / 46
Vysvětlení definice bloku
Příklad: Uvažujme graf na obrázku a příklady podgrafů indukovaných různými množinami vrcholů. Určete, zdá se jedná o bloky.
63 je podgraf indukovaný množinou vrcholů {a, c, d}.
26. 9. 2017       25 / 46
Vysvětlení definice bloku
Příklad: Uvažujme graf na obrázku a příklady podgrafů indukovaných různými množinami vrcholů. Určete, zdá se jedná o bloky.
63 je podgraf indukovaný množinou vrcholů {a, c, d}.
Odpověď: Ne, nejedná se o blok. Sice je splněna podmínka 2-souvislosti podgrafů, avšak podgraf indukovaný vrcholy {a, c, d} není maximální, je podgrafem bloku {a, b,c,d}. 4 a > ,   = ,
26. 9. 2017       25 / 46
Důležitá vlastnost bloku
Tvrzení 1.4 (MILKOVA): Nechť G je souvislý graf. Pak platí: Jestliže B\ — (Vi, E\) a 62 = (^2, £2) jsou dva různé bloky grafu G, pak V± H V2 je buď prázdná množina, nebo jednoprvková množina {v}, kde v je artikulace grafu G.
26. 9. 2017       26 / 46
Důležitá vlastnost bloku
Tvrzení 1.4 (MILKOVA): Nechť G je souvislý graf. Pak platí:
Jestliže B\ — (Vi, E\) a 62 = (^2, £2) jsou dva různé bloky grafu G, pak
V± H V2 je buď prázdná množina, nebo jednoprvková množina {v}, kde
v je artikulace grafu G.
•
Důkaz: Sporem předpokládejme, že \ Vi n V21 > 2. Nechť v, w e Vi n V2.
26. 9. 2017       26 / 46
Důležitá vlastnost bloku
Tvrzení 1.4 (MILKOVA): Nechť G je souvislý graf. Pak platí: Jestliže B\ — (Vi, E\) a 62 = (V2, £2) jsou dva různé bloky grafu G, pak Vi H V2 je buď prázdná množina, nebo jednoprvková množina {v}, kde v je artikulace grafu G.
Důkaz: Sporem předpokládejme, že |Vi n V21 > 2.
Nechť v, w e Vi n V2. □ Protože v, w £ 61, zůstane 61 — v (resp. 61 — w) souvislý. B Protože v, w £ 62» zůstane 62 — v (resp. 62 — w) souvislý.
26. 9. 2017       26 / 46
Důležitá vlastnost bloku
Tvrzení 1.4 (MILKOVA): Nechť G je souvislý graf. Pak platí: Jestliže B\ — (Vi, E\) a 62 = (V2, £2) jsou dva různé bloky grafu G, pak Vi H V2 je buď prázdná množina, nebo jednoprvková množina {v}, kde v je artikulace grafu G.
Důkaz: Sporem předpokládejme, že |Vi n V21 > 2.
Nechť v, w e Vi n V2.
H Protože v, w G 61, zůstane 61 — v (resp. 61 — w) souvislý.
B Protože v, w G 62» zůstane 62 — v (resp. 62 — w) souvislý.
Celkem tedy (61 U 62) — v, resp. (61 U 62) — w zůstávají souvislé, tudíž 61 U 62 je také blok. 61, 62 tedy nemohou být bloky - spor. Proč?
26. 9. 2017       26 / 46
Důležitá vlastnost bloku
Tvrzení 1.4 (MILKOVA): Nechť G je souvislý graf. Pak platí: Jestliže B\ — (Vi, E\) a B2 = (V2, £2) jsou dva různé bloky grafu G, pak Vi H V2 je buď prázdná množina, nebo jednoprvková množina {v}, kde v je artikulace grafu G.
Důkaz: Sporem předpokládejme, že |Vi n V21 > 2.
Nechť v, w e Vi n V2.
□ Protože v, w £ 61, zůstane 61 — v (resp. 61 — w) souvislý.
B Protože v, w £ 62» zůstane 62 — v (resp. 62 — w) souvislý.
Celkem tedy (61 U 62) — v, resp. (61 U 62) — w zůstávají souvislé, tudíž 61 U 62 je také blok. 61, 62 tedy nemohou být bloky - spor. Proč?
Závěr: |Vi n V2\ < 2, tj. buď \ Vľ n V2| = 0, nebo |Vi n V2\ = 1
(i/ini/2 = M).
•fy <\ (y
26. 9. 2017       26 / 46
Pokračování důkazu
Zbývá ukázat, že pro případ
26. 9. 2017       27 / 46
Vi n V2 = 1 je {v} = Vi n \/2 artikulace.
Pokračování důkazu
Zbývá ukázat, že pro případ | V\ n V21 = 1 je {v} = V\ n V2 artikulace
Sporem předpokládejme, že v není artikulace. Pak nutně G — v je souvislý graf.
26. 9. 2017       27 / 46
Pokračovaní důkazu
Zbývá ukázat, že pro případ | V\ n V21 = 1 je {v} = V\ n V2 artikulace.
Sporem předpokládejme, že v není artikulace. Pak nutně G — v je souvislý graf.
Uvažujme nyní libovolný podgraf P souvislého grafu G — v, který je cestou z vrcholu množiny V\ do vrcholu množiny V2.
26. 9. 2017       27 / 46
Pokračovaní důkazu
Zbývá ukázat, že pro případ | V\ n V21 = 1 je {v} = V\ n V2 artikulace.
Sporem předpokládejme, že v není artikulace. Pak nutně G — v je souvislý graf.
Uvažujme nyní libovolný podgraf P souvislého grafu G — v, který je cestou z vrcholu množiny V\ do vrcholu množiny V2. Pak ovšem P U B\ U 62 je 2-souvislý. 61, 62 nemohou být bloky - spor. Proč?
26. 9. 2017       27 / 46
Zbývá ukázat, že pro případ
Vin v2
= 1 je {v} = Vi n V2 artikulace.
Sporem předpokládejme, že v není artikulace. Pak nutně G — v je souvislý graf.
Uvažujme nyní libovolný podgraf P souvislého grafu G — v, který je cestou z vrcholu množiny V\ do vrcholu množiny V2. Pak ovšem P U B\ U 62 je 2-souvislý. 61, 62 nemohou být bloky - spor. Proč?
Závěr: Pro případ
Vin V2
= 1 je tedy {v} = 61 n 62 artikulace.
Procvičení pojmů
Příklad: V následujícím grafu G určete všechny bloky.
G:
©
J
Řešení příkladu
Blok B\ - podgraf indukovaný vrcholy {c
Řešení příkladu
Blok 62 _ podgraf indukovaný vrcholy {a, b, c, d}
26. 9. 2017       30 / 46
Řešení příkladu
Blok 63 - podgraf indukovaný vrcholy {c/, h}
26. 9. 2017       31 / 46
Řešení příkladu
Blok 64 - podgraf indukovaný vrcholy {dj}
Řešení příkladu
Blok 65 - podgraf indukovaný vrcholy {/, /}
26. 9. 2017       33 / 46
Řešení příkladu
Blok     - podgraf indukovaný vrcholem {g}
Detektivní kancelář
Detektivové Fousek a Micumiši zkoumali sedmičlennou skupinu osob a v grafu (každý ve svém) propojili dvojice osob, které se znají (nepropojené dvojice osob se neznají). Fousek označil osoby písmeny, Micumiši čísly (viz obrázek). Zjistěte, která písmena a čísla odpovídají stejným osobám.
26. 9. 2017       35 / 46
Izomorfní grafy
Definice 1.13 (MILKOVA): Graf G = (\/, E) je izomorfní s grafem G' — (V7, Ef), jestliže existuje vzájemně jednoznačné zobrazení f : V -> V takové, že platí {v, w} G E & {f(v), f(w)} G E'.
Poznámka: Fakticky to znamená, že dva izomorfní grafy jsou stejné až na pojmenování vrcholů.
Pro grafy o malém počtu vrcholů jsme schopni zjistit, zda jsou či nejsou izomorfní. Neexistuje však žádný "zaručený" a efektivní algoritmus pro zjištění izomorfismu dvou grafů. "Hrubou silou" bychom museli zkoušet všech n\ možností! (r? je počet vrcholů obou grafů)
26. 9. 2017       36 / 46
Jak vyšetřit izomorfnost?
Dva izomorfní grafy mají naprosto stejné vlastnosti, tedy zejména
■ mají stejný počet vrcholů i hran,
■ mají stejné skóre,
■ mají stejný počet kružnic dané délky,
■ mají stejné doplňky,
■ mají stejné podgrafy indukované množinami vrcholů stejného stupně.
26. 9. 2017       37 / 46
Problém detektivní kanceláře
Nejprve si zapíšeme skóre obou grafů. Fousek i Micumiši mají stejné: (5,2,4,4,2,3,2)^(2,2,2,3,4,4,5).
Hledejme nyní izomorfismus h. V obou grafech je jediný vrchol stupně 3. Musí tedy být h(f) = 4.
26. 9. 2017       38 / 46
Problém detektivní kanceláře (2)
Označili jsme si vrcholy ŕ, 4 stejnou barvou a vyznačili si incidentní hrany. Je patrné, že tyto vrcholy stupně 3 v obou grafech sousedí s jedním vrcholem stupně 2, jedním vrcholem stupně 4 a jedním vrcholem stupně 5.
Je tedy zřejmé, že h(e) = 7 (vrcholy stupně 2), h(c) = 6 (vrcholy stupně 4), h(a) = 3 (vrcholy stupně 5).
26. 9. 2017       39 / 46
Problém detektivní kanceláře (3)
Fousek
Micumiši
V obou grafech zbývá jediný vrchol stupně 4, totiž d, resp. 1. Platí tedy, že h(d) = 1.
26. 9. 2017       40 / 46
Problém detektivní kanceláře (4)
Vrcholy a, c tvoří trojúhelník s vrcholem b {d{b) — 2) v 1. grafu. Vrcholy 3, 6 tvoří trojúhelník s vrcholem 5 (c/(5) = 2) ve 2. grafu. Platí tedy h{b) = 5.
26. 9. 2017       41 / 46
Problém detektivní kanceláře - řešení
Zbývá jediný vrchol v každém grafu. Je tedy patrné, že h(g)
Grafy jsou izomorfní, hledané zobrazení:
a    3, b ^ 5, c ^> 6, cř     1, e ^> 7, ŕ ^> 4, g" ^> 2.
Izomorfismus - ještě jeden příklad
Příklad: Vyšetřete, zda jsou grafy Gi, G2 izomorfní.
Řešení příkladu
Prozkoumejme doplňky obou grafů na obrázku.
26. 9. 2017       44 / 46
Řešení příkladu
Prozkoumejme doplňky obou grafů na obrázku.
Všimněte si, že -G2 není souvislý, kdežto -G\ ano. Proto grafy Gi, G2 nejsou izomorfní.
26. 9. 2017       44 / 46
□ Kolik existuje navzájem neizomorfních grafů na třech vrcholech? Q Kolik existuje navzájem neizomorfních grafů na čtyřech vrcholech
Řešení příkladu
H Kolik existuje navzájem neizomorfních grafů na třech vrcholech?
2
26. 9. 2017       46 / 46
Řešení příkladu
□ Kolik existuje navzájem neizomorfních grafů na třech vrcholech? • • • •
2
26. 9. 2017       46 / 46
Řešení příkladu
H Kolik existuje navzájem neizomorfních grafů na třech vrcholech? 4. • • • •
Q Kolik existuje navzájem neizomorfních grafů na čtyřech vrcholech?
26. 9. 2017       46 / 46
Řešení příkladu
□ Kolik existuje navzájem neizomorfních grafů na třech vrcholech? 4.
• • • •
• •     •   • •—•
B Kolik existuje navzájem neizomorfních grafů na čtyřech vrcholech? 11.
T\T KT TvT 1^4 i^i i£l
26. 9. 2017       46 / 46