Задача
В кружке у каждого члена имеется один друг и один враг. Доказать, что
а) число членов чётно.
б) кружок можно разделить на два нейтральных кружка.
Решение
а) Весь кружок разбивается на пары друзей. б) Поскольку степень каждой вершины соответствующего графа равна 2, то он разбивается на циклы. В каждом цикле рёбра "дружбы" и "вражды" чередуются, значит, тех и других поровну. Поместив в один кружок членов каждого цикла, взятых через одного, мы получим кружок, где нет ни друзей, ни врагов. Оставшиеся члены образуют второй нейтральный кружок.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет