MA2BP_CDM1 Cvičeni z diskrétní matematiky 1
5. Bipartitní a hamiltonovské grafy
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
29. 11. 2017
29. 11. 2017       1 /7
1. Zadejte graf /<2,3 maticí sousednosti.
2. Nakreslete úplný bipartitní graf K33.
3. Kolik hran má úplný bipartitní graf /<4?5?
4. Určete počet všech úplných bipartitních podgrafů K13 úplného bipartitního grafu /<2,3-
5. Určete počet všech úplných bipartitních podgrafů K13 úplného bipartitního grafu K33.
MILKOVA - Cvičeni 2.1
6. Představte si, že hodláte k sobě domů na večeři pozvat 8 kamarádů (označme je a, b, c, c/, e, f,g, h). Někteří z nich se již znají. Večeři budete podávat u dvou stolů. Zjistěte, zda by bylo možné posadit své kamarády ke dvěma stolům tak, aby u každého stolu seděli jen ti, kteří se navzájem neznají (aby mohli rozšířit okruh svých známých). Níže je uveden přehled vašich kamarádů, kteří se již znají.
3 ...	d, f, g	e m   m m	c,	f
b ...	c, d, h	f...	a,	d, e
c m   m m	b, e	g ■■■	a	
d ...	a, b, f	h ...	b	
29. 11. 2017       3 /7
Pokerový turnaj - úkol k samostatnému řešení
Rozhodli jste se, že pro své známé uspořádáte pokerový turnaj. Pozvánku Vám potvrdilo 13 známých. Poker je hra pro 2 až 10 hráčů, proto jste se rozhodli rozdělit 13 příchozích do 2 skupin, z nichž do finále postoupí tři nejlepší z každé skupiny. Pro zařazení do skupiny máte jediné kritérium: hráči skupiny se neznají. Tabulka udává, kteří hráči se spolu znají.
a ...	b	h ...	b, g, 1
b ...	a, c, h	i...	e, j
c m   m m	b, d	j ...	i, k
d ...	c	k ...	g, j, 1, m
e ^■n"        m   m m	f, i	/...	k, h
f...	e, g, m	m ...	f, k
g ■■■	f, h, k		
Je možné rozdělit účastníky turnaje do dvou skupin o minimálně 5 a maximálně 8 hráčích, aby se hráči v jedné skupině neznali?
29. 11. 2017       4 /7
MILKOVA - Cvičení 2.2
1. Rozhodněte o každém z následujících grafů, zda je nebo není hamiltonovský. Své rozhodnutí odůvodněte.
MILKOVA - Cvičeni 2.2
1. Rozhodněte o každém z následujících grafů, zda je nebo není hamiltonovský. Své rozhodnutí odůvodněte.
MILKOVA - Cvičeni 2.2
1. Rozhodněte o každém z následujících grafů, zda je nebo není hamiltonovský. Své rozhodnutí odůvodněte.
MILKOVA - Cvičení 2.2
2. V grafu na následujícím obrázku (rovinná reprezentace pravidelného dvanáctistěnu) najděte hamiltonovskou kružnici.
29. 11. 2017       6 /7
MILKOVA - Cvičeni 2.2
3. Dokažte tvrzení:
Vg=(v,e) G Je hamiltonovský graf =)>vG neexistuje most.
4. Dokažte tvrzení:
Vg=(v,e) G je bipartitní graf s lichým počtem vrcholů =4> G není hamiltonovský graf.
5. Vyvraťte tvrzení:
Vg=(v,e) v G neexistuje most =4> G je hamiltonovský graf.
6. Vyvraťte tvrzení:
Vg=(v,e) G neobsahuje artikulaci =4> G je hamiltonovský graf.
29. 11. 2017       7 /7