Taneční

Řešení

Najdeme několik nesaturovaných alternujících cest v grafu reprezentujícím úlohu. Po třech krocích se podaří najít úplné párování v grafu, což je ideální řešení našeho problému.

Odpověď:

Je možné sestavit taneční páry tak, aby každý měl partnera podle svých představ!

Uf!