demo8-tabule. notebook
November 18, 2010
Príklad 52, Uvedie Floydúv algoritmus pro nalezení riejkratších cest mezi všemi dvojicemi vrcholů. Tento algoritmus použijte na orientovaný graf na, obrázku. Jednotlivé mezivýpočty zapisujte do matic. Uveďte, jak se v průběhu výpočtu detekují cykly záporné délky. -—m—.		
		
	-EH-	IV /
	A m m	m / / ^
		
11 18-16:55
t 9 "o s) f^V^f^^
11 18-17:06
Příklad 53. Rozhodněte, zda jsou následující grafy eulerovské. Pokud nejsou, doplňte je přidáním hran na eulerovské (je-li to možné). Nalezněte eulerovské tahy pomocí
1. algoritmu prodlužování cyklů;
2. Fleuryho algoritmu (prodlužování tahů i (Očíslujte vrcholy a j
"'''uháním, se mostům), dodržujte.)
11 18-16:56
11 18-17:37
■--e^      a *
11 18-16:58
11 18-17:37
1
demo8-tabule. notebook
November 18, 2010
Príklad 54. Problém čínského pošiáka v hranové ohodnoceném •neorientovaném grafu je problémem nalezení ti ejk nit šib o uzavřeného sledu, který obsahuje každou hranu v grafu. XaJ.ezn.ete řešení tohoto problému pro graf na obrázku.
Příklad 55 (Nutná podmínka toho. aby graf mohl být hamilTo-novský). Je-li G — (V. E) hamiltonovský a, 0 ^ W C V, pak G \ W má nejvýše \ W\ komponent souvislosti.
Ukažte na konkrétním, príkladu grafu, že opak obecně neplatí.
11 18-16:56
11 18-16:56
Příklad 58 (Postačující podmínky pro to. aby graf byl hamiltonovský) .
Dirac: stupeň každého vrcholu je aspoň \V\j2.
Oře: součet stupňů libovolných dvou nesousedních vrcholů je aspoň
\V\.
Bondy-Chvátal: G je hamiltonovský právě když G + uv je hamiltonovský (u, v jsou nesousední vrcholy, jejichž součet stupňů je aspoň \'\ - opakování/]:, přidáváním takových hran. dokud to jde. získáme tzv. uzávěr grafu cl(G)).
1. Dokažte, že z Bondy-Chvátalovy věty plyne Oreho a z ní Diracova.
2. Udejte příklad hamiltonovského grafu, který splňuje podmínku Oreho věty ale ne věty Diracovy.
3- Udejte přiklad hamiltonovského grafu, jehož uzáver není úplný ■imf.
11 18-16:56
11 18-18:04
Příklad. 57. Rozhodněte (a zdůvodněte), zda v Petersenové grafu existuje vnjuíV- ^"-n
L hamiltonovská cesta.
2. hamiltonovská kružnice.
Příklad 58. Rozhodněte, zdaje daný graf Aj. ^0\j^\\>^\
rovinný. Zdůvodněte. * ^    ^ l
•v,
11 18-16:57
11 18-16:57
demo8-tabule. notebook
November 18, 2010
Příklad 59. Rozhodněte, zri n p.Tí.ttn^c.jirn. f rnnnr.í skóre (6, S. 6, 7. 7, 7, 7, 8.8.8). Pokud ano, existuje i rovinný graf daného skóre?      ^ * ?0
11 18-16:57
Príklad 60. Rozhodněte, zda. je daný rovinný graf mazimálm. Doplňte co nejvíce, hran vři zachování rovinnosti. ,»
W
11 18-16:57
Příklad 61. Každé z následujících, tvrzení, dokažte nebo ukažde vhodný protipříklad.
(a) Každý graf s méně než 9 hranami je rovinný.
(b) Graf, který není rovinný, není hamiltonovský.
(c) Graf, který není rovinný, je hamiltonovský.
(d) Graf, který není rovinný, není eulerovský.
(e) Graf, který není rovinný, je eulerovský.
(f) Každý hamiltonovský graf je rovinný.
(g) Žádný hamiltonovský graf není rovinný.
(h) Každý eulerovský graf je rovinný.
(i) Žádný eulerovský graf není rovinný.
11 18-16:57
3