Domácí úlohy z minulého týdne Toky v sítích Drsná matematika III – 11. demonstrovaná cvičení Toky v sítích Martin Panák Masarykova univerzita Fakulta informatiky 29.11. 2011 Domácí úlohy z minulého týdne Toky v sítích Plán přednáky 1 Domácí úlohy z minulého týdne 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. Uvažme graf o 256 vrcholech. Vrcholy očíslujme postupně všemi dvojcifernými čísly v šestnáctkové soustavě (před jednociferná čísla píšeme cifru 0, je tedy A=0A). Hranou jsou spojeny každé dva vrcholy, které jsou označeny čísly se stejnou první cifrou, dále pak každé dva vrcholy, které jsou označeny číslem sestávajícím ze dvou stejných cifer. Žádné jiné dva vrcholy nejsou spojeny hranou. Kolik má tento graf koster? Řešení. 1614·17. 2 Domácí úlohy z minulého týdne Toky v sítích Příklad. 2. Dokažte nebo vyvraťte: dva stromy se stejným skóre jsou izomorfní. Řešení. Nejsou. 2 Domácí úlohy z minulého týdne Toky v sítích Příklad. 3. Na základě uvedené tabulky, udávající vzdálenosti měst v km, určete minimální délku silniční sítě, propojující uvedená města. Domácí úlohy z minulého týdne Toky v sítích Domácí úlohy z minulého týdne Toky v sítích Plán přednáky 1 Domácí úlohy z minulého týdne 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: