Гуглите "Игры на графах" — получаете теорию. Пробуете решать. Если не получится, то в строку поиска следует добавить "журнал Квант" — тогда найдёте теоретический материал, где подробно описаны способы решения подобного класса задач. Удачи!

решение в первой правке. если кто-нибудь знает что-то более общее, или как притянуть сюда НИМ, прошу дать ссылку, а не отсылать к гуглу.