Domácí úlohy z minulého týdne Toky v sítích Drsná matematika III ­ 10. demonstrovaná cvičení Toky v sítích Martin Panák Masarykova univerzita Fakulta informatiky 28.11. 2006 Domácí úlohy z minulého týdne Toky v sítích 1 Domácí úlohy z minulého týdne Příklad 1 Příklad 2. Příklad 3. 2 Toky v sítích Řezy Ford-Fulkersonův algoritmus Domácí úlohy z minulého týdne Toky v sítích Příklad 1. Kolik existuje různých koster grafu K5? Kolik různých jich existuje až na izomorfismus? Domácí úlohy z minulého týdne Toky v sítích Příklad 1. Kolik existuje různých koster grafu K5? Kolik různých jich existuje až na izomorfismus? Řešení. Existují tři navzájem neizomorfní kostry (se skóre (1, 2, 2, 2, 1), (1, 2, 3, 1, 1), (4, 1, 1, 1, 1)). Příslušné třídy isomorfních grafů mají postupně 5 4 2 2, 5 4 3 a 5 prvků, celkem 125 různých koster. 2 Domácí úlohy z minulého týdne Toky v sítích Prüferova posloupnost. Prüferovu posloupnost můžeme přiřadit kostře grafu Kn a to následujícím způsobem: označme vrcholy v grafu Kn postupně od 1 do n a odstraňujme postupně listy dané kostry (od nejmenšího) a s každým odstraněným listem zapíšme do posloupnosti souseda právě odstraněného listu. Opakujeme tak dlouho, dokud v kostře nezbubou pouze dva vrcholy. Získaná posloupnost má evidentně n - 2 členů, které mohou nabývat hodnot od 1 do n. Obráceně není těžké dokázat, že pro každou takovou posloupnost existuje právě jedna kostra grafu Kn, která se do této posloupnosti výše popsaným postupem zakóduje. Celkem dostáváme, že existuje právě nn-2 různých koster grafu Kn. Domácí úlohy z minulého týdne Toky v sítích Příklad 2. Uvažme následující postup pro určování minimální cesty mezi dvěma vrcholy v ohodnocené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. Domácí úlohy z minulého týdne Toky v sítích Příklad 2. Uvažme následující postup pro určování minimální cesty mezi dvěma vrcholy v ohodnocené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. Řešení. Postup není správný. Stačí uvážit například kružnici s hranami ohodnocenými až na jednu jedničkami, zbývající hrana ohodnocená dvojkou. 2 Domácí úlohy z minulého týdne Toky v sítích 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). Domácí úlohy z minulého týdne Toky v sítích 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). Řešení. Aplikací algoritmu na hledání minimální kostry zjistíme, že hledaná délka je 12154. (v kostře jsou hrany LPe, LP, LNY, PeT, MCNY). 2 Domácí úlohy z minulého týdne Toky v sítích 1 Domácí úlohy z minulého týdne Příklad 1 Příklad 2. Příklad 3. 2 Toky v sítích Řezy Ford-Fulkersonův algoritmus Domácí úlohy z minulého týdne Toky v sítích Různé definice řezů. Nalezněte všechny řezy v následujícím grafu: Domácí úlohy z minulého týdne Toky v sítích Najděte maximální tok v následujícím ohodnoceném orientovaném grafu: