teorie grafů
Matematika III, 8. cvičení
Pojmy k zopakování:
• Graf, stupeň vrcholu, kružnice, cesta, cyklický žebřík
• Uplný graf, bipartitní graf, Úplný bipartitní graf
• Ižomorfismus grafU
• Skore grafu
• Souvislost grafu, hranova a vrcholový souvislost
• Prohledavúní grafu do hloubky, do sírky
Příklad 136. Určete, kolik hran mají následující grafy: K6, K5>6, C8. Výsledek. K6 ma 15 hran, K5)6 mý 30 hran, C8 ma 8 hran.
Příklad 137. Určete, kolik hran musíme pridat do kružnice o n vrcholech, abychom dostali Uplný graf.
Výsledek. n(n-1 — n
Příklad 138. Určete, kolik hran musíme pridat do áplneho bipartitního grafu Kmn, abychom dostali uýplnýy graf.
Výsledek. (m+n)(!m+n~1) — m • n.
Příklad 139. Definujme uplný tripartitní graf nasledovne. Uvazujme tri po dvou disjunktní množiny vrcholu V1,V2,V3. Hranou spojme každé dva vrcholy, pokud neleží oba dva ve Ví pro nějaké i G {1,2,3}. Pokud |V1| = r, |V2| = s, \V3\ = t, označme uplný tripartitní graf symbolem Kr,s,t. Nakreslete Ki,2)3, K2,2,2, K2-&-&.
Příklad 140. Určete, kolik existuje navzajem neizomorfních íplnych bipartitních grafu s 1001 hranami.
Výsledek. 4
Příklad 141. Určete, kolik vrcholU ma cyklický Zebrík s 2010 hranami.
Vyísledek. 1340
Příklad 142. Zadejte nasledující graf maticí sousednosti.
Příklad 143. Dostanete orientovaný graf reprezentovaný maticí sousednosti A. Určete, jaký graf bude zadaívat transponovanía matice tíeto matice.
23
Příklad 144. Dokažte, že součet stupňů všech vrcholů v libovolném jednoduchém grafu je sudý.
Příklad 145. Kolík je všech cyklů v grafu Kq? Kolík v Kn? Výsledek. (3) + (4) + (5) + (q).
n
(3) + G) + (5) ••• + O =2™ - 1 - n.
Příklad 146. Dokažte, že v každém jednoduchém grafu o více než jednom vrcholu existuje dvojice vrcholů se stejným stupněm.
Příklad 147. Na konferenci se sešlo n matematiků a několik z nich si navzájem potréslo rukou. Dokažte, že mezi nimi existuje, dva matematici, které si potrasli rukama se stejným počtem lidé.
Napoveda: Využijte predchozé préklad.
Příklad 148. Sešlo se 5 lidé. Je možné, ze se kazdý z nich zna s pravě tremi ostatnémi (predpoklédejte, ze znémost je sýmetricka)?
Vésledek. Ne
Příklad 149. Určete, který z nésledujécéch grafu je bipartitní. Sve tvrzeni dokazte.
Vésledek. První ne, další dva ano.
Příklad 150. Uveďte príklad dvou neizomorfnéch grafů o šesti vrcholech, kazdý stupne 2. Příklad 151. Dokazte, ze neexistujé dva neizomorfné grafý o peti vrcholech, každý stupne 2. Příklad 152. Dokažte, ze dva grafý jsou izomorfné, jsou-li izomorfné jejich doplnký. Příklad 153. Dokažte, ze kazde dva z uvedených grafů jsou izomorfní.
Příklad 154. Rozhodnete, ktere dva z uvedených grafu jsou izomorfní. Daný izomorfismus popi ste.
24
Příklad 155. Určete, kolik navzájem neizomorfních grafů můžeme dostat přidáním jedné hrany do následujících grafů.
Příklad 156. Nakreslete všechny neizomorfní grafy na
1. 2 vrcholech
2. 3 vrcholech
3. 4 vrcholech
4. 5 vrcholech
Příklad 157. Kolik existuje neizomorfních grafů s 6 vrcholy, všemi stupne 3? Napovedá: UvaZujte doplnky grafů.
Příklad 158. Dokašte, Ze pro kašde pnrozené číslo n existuje graf se skórem
(0,1,1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4,..., n,..., n). Příklad 159. Urcete všechna nezaporna cela císla a pro ktera existuje graf se skorem
1. (1, 5, 5, 6, 6, 7, 8, 9, 9,11,11, a)
2. (4, 6, 6, 9, 9, 9, 9,10,11,11,11, a)
Příklad 160. Uveďte príklad grafu, ktery ma stejné skóre jako graf na obmzku a presto není s tímto grafem izomorfní.
Příklad 161. Nakreslete všechny navzajem neizomorfní grafy se skórem (3,3,3,3, 3, 3, 6). Příklad 162. Urcete, kolik podgrafů izomorfních C3 obsahuje nesledující graf.
Vísledek. 3
25
Příklad 163. Určete, kolik podgrafů izomorfních C3 obsahuje graf Kn. Výsledek. (3)
Příklad 164. Kolik podgrafu Úplného grafu K10 je izomorfních kruZnici C4? Výsledek. 3 • (140)
Příklad 165. Určete, kolik nejvíce komponent souvislosti muZe mít graf s 2010 vrcholy, kaZdym stupně 4.
Výsledek. 402
Příklad 166. Určete, kolik nejmene hran musí mít graf na 12 vrcholech, aby jeho stupen (vrcholovej souvislosti byl 3.
Výsledek. 18
Příklad 167. Určete, kolik nejvíce hran muZe mít graf na 10 vrcholech, který se sklada ze trí komponent souvislosti.
Výsledek. 28
Příklad 168. Určete vrcholovou i hranovou souvislost nasledujýcých grafu:
Příklad 169. Určete, v jakem poradí vrcholu byste prohledavali tento graf do šířky a v jakem poradý vrcholu do hloubky, prohledavíte-li z vrcholu a.
Příklad 170. Určete, v jakem poradí vrcholu byste prohledívali tento graf zadaný seznamem, nasledníku do číčky a v jakem poradí vrcholu do hloubky, prohledaváte-li z vrcholu a.
a b c
d
e f
g h
i
b
a
ag
a
bi bi bc cg
ef
c e
d
fg
h
26
h
Příklad 171. Oba orientované grafy na následujících obrázcích projděte pomocí průchodu do hloubky. Pokud si v některém kroku mUěete vybrat z několika vrcholů, tak si vědy vyberte ten abecedne nejmensí z nich.
27