Sada domácích úloh k přednášce Matematika III
k odevzdání v týdnu 20 ­ 24. listopadu 2006
Příklad 1. Kolik existuje různých koster grafu K5? Kolik různých jich existuje až na izomorfismus?
Příklad 2. Uvažme následující postup pro určování minimální cesty mezi dvěma vrcholy v ohod-
noceném neorientovaném grafu: nejprve nalezneme minimální kostru grafu, za minimální cestu
pak prohlásíme jedinou cestu spojující dva dané vrcholy v minimální kostře. Dokažte, že je tento
postup správný, nebo uveďte protipříklad.
Příklad 3. Máme dánu následující tabulku vzdáleností světových metropolí: Londýna, Mexico
City, New Yorku, Paříže, Pekingu a Tokia:








L MC NY P Pe T
L 5558 3469 214 5074 5959
MC 2090 5725 7753 7035
NY 3636 6844 6757
P 5120 6053
Pe 1307








Jaká je nejmenší délka kabelu, kterým je možné propojit tato města? (předpokládáme, že délka
kabelu potřebného k propojení daných dvou měst je právě vzdálenost v tabulce).