Teoňe grafů
Matematika III, 8. cvičení
Pojmy k zopakování
• Graf, stupeň vrcholu, kružnice, cesta, cyklický žebřík
• Úplný graf, bipartitní graf, úplný bipartitní graf
• Izomorfismus grafů
• Skóre grafu
• Souvislost grafu, hranová a vrcholová souvislost
• Prohledávání grafu do hloubky, do šířky
Příklad 136. Určete, kolik hran mají následující grafy: Kq, #5,6, Cs-Výsledek. #g má 15 hran, #5^ má 30 hran, Cs má 8 hran.
Příklad 137. Určete, kolik hran musíme přidat do kružnice o n vrcholech, abychom dostali úplný graf.
Výsledek. n^"2 ^ — n
Příklad 138. Určete, kolik hran musíme přidat do úplného bipartitního grafu #m,n, abychom dostali úplný graf.
Výsledek. (m+")0"+" 1) _ m . n_
Příklad 139. Definujme úplný tripartitní graf následovně. Uvažujme tři po dvou disjunktní množiny vrcholů V\,V2,Vs- Hranou spojme každé dva vrcholy, pokud neleží oba dva ve Ví pro nějaké i G {1,2,3}. Pokud \V±\ = r, |V21 = s, |V*j| = t, označme úplný tripartitní graf symbolem Kr^t. Nakreslete #1,2,3> #2,2,2, #2,3,3'
Příklad 140. Určete, kolik existuje navzájem neizomorfních úplných bipartitních grafů s 1001 hranami.
Výsledek. 4
Příklad 141. Určete, kolik vrcholů má cyklický žebřík s 2010 hranami. Výsledek. 1340
Příklad 142. Zadejte následující graf maticí sousednosti.
Výsledek.
23
Jeden z možných výsledků:
/ 0   1 1   1 0   0 0 1 \
10 10 0   10 0
1   1 0   1 0   0 0 0
10 10 10 0 0
0   0 0   1 0   1 1 0
0   10   0 10 10
0   0 0   0 1   0 1 1
Vioooooio/
Příklad 143. Dostanete orientovaný graf reprezentovaný maticí sousednosti A. Určete, jaký graf bude zadávat transponovaná matice této matice.
Příklad 144. Dokazte, že součet stupňů všech vrcholu v libovolném jednoduchém grafu je sudý. Příklad 145. Kolik je všech cyklů v grafu Kq?
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 potřáslo rukou. Dokažte, že mezi nimi existují dva matematici, kteří si potřásli rukama se stejným počtem lidí.
Nápověda: Využijte předchozí příklad.
Příklad 148. Sešlo se 5 lidí. Je možné, že se každý z nich zná s právě třemi ostatními (předpokládejte, že známost je symetrická)?
Výsledek. Ne
Příklad 149. Určete, který z následujících grafů je bipartitní. Své tvrzení dokažte.
Výsledek. První ne, další dva ano.
Příklad 150. Uveďte příklad dvou neizomorfních grafů o šesti vrcholech, každý stupně 2. Příklad 151. Dokažte, že neexistují dva neizomorfní grafy o pěti vrcholech, každý stupně 2. Příklad 152. Dokažte, že dva grafy jsou izomorfní, jsou-li izomorfní jejich doplňky. Příklad 153. Určete všechny dvojice izomorfních grafů.
Výsledek. (3) + 3 • (J) + 24 g) + 120©.
24
Výsledek. Druhý, třetí a čtvrtý graf jsou navzájem izomorfní.
Příklad 154. Rozhodněte, které dva z uvedených grafů jsou izomorfní. Daný izomorfismus popište.
Výsledek. Poslední dva grafy jsou izomorfní
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ů.
Výsledek. 3,9,6,16
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 stupně 3? Nápověda: Uvažujte doplňky grafů.
Výsledek. 2
Příklad 158. Dokažte, že pro každé přirozené čí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. Určete všechna nezáporná celá čísla a pro která existuje graf se skórem 1. (1,5,5,6,6,7,8,9,9,11,11,«)
25
2. (4,6,6,9,9,9,9,10,11,11,11,«)
Příklad 160. Uveďte přiklad grafu, který má stejné skóre jako graf na obrázku a přesto není s tímto grafem izomorfní.
Příklad 161. Nakreslete všechny navzájem neizomorfní grafy se skórem (3,3,3,3,3,3,6). Výsledek. 2
Příklad 162. Určete, kolik podgrafů izomorfních c3 obsahuje následující graf.
Výsledek. 3
Příklad 163. Určete, kolik podgrafů izomorfních C3 obsahuje graf Kn. Výsledek. Q)
Příklad 164. Kolik podgrafů úplného grafu Kw je izomorfních kružnici C4? Výsledek. 3 • (4)
Příklad 165. Určete, kolik nejvíce komponent souvislosti může mít graf s 2010 vrcholy, každým stupně 4.
Výsledek. 402
Příklad 166. Určete, kolik nejméně hran musí mít graf na 12 vrcholech, aby jeho stupeň (vrcholové) souvislosti byl 3.
Výsledek. 18
Příklad 167. Určete, kolik nejvíce hran může mít graf na 10 vrcholech, který se skládá ze tří
komponent souvislosti.
Výsledek. 28
Příklad 168. Určete vrcholovou i hranovou souvislost následujících grafů:
26
Výsledek.
1. 3,3
2. 3,3
3. 1,3
Příklad 169. Určete, v jakém pořadí vrcholů byste prohledávali tento graf do šířky a v jakém pořadí vrcholů do hloubky, prohledáváte-li z vrcholu a.
Výsledek.
1. šířka: a,b, f,j,c,d,e,h,i,g
2. hloubka: a, b, c, d, g, e, j, i, h, f
Příklad 170. Určete, v jakém pořadí vrcholů byste prohledávali tento graf zadaný seznamem následníků do šířky a v jakém pořadí vrcholů do hloubky, prohledáváte-li z vrcholu a.
a	b	c	d
b	a	e	f
c	a	9	h
d	a		
e	b	i	
f	b	i	
g	b	c	h
h	c	9	
i	e	f	
Výsledek.
1. šířka: a, b, c, d, e, /, g, h, i
2. hloubka: a, b, e, i, f, g, c, h
27
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 můžete vybrat z několika vrcholů, tak si vždy vyberte ten abecedně nejmenší z nich.
Výsledek.
1. a,b,d,e,c,g,f,h
2. a,b,c,d,h,k,l,e,i,f,g,j
28