Задача 31070

Темы:    [ Степень вершины ] [ Разбиения на пары и группы; биекции ] [ Четность и нечетность ]

Сложность: 3+ Классы: 6,7,8

Условие

В кружке у каждого члена имеется один друг и один враг. Доказать, что
  а) число членов чётно.
  б) кружок можно разделить на два нейтральных кружка.

Решение

  а) Весь кружок разбивается на пары друзей.

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

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	02