Версия для печати
Убрать все задачи

---

Квадрат 4×4 разделён на 16 клеток. Раскрасьте эти клетки в чёрный и белый цвета так, чтобы у каждой чёрной клетки было три белых соседа, а у каждой белой клетки был ровно один чёрный сосед. (Соседними считаются клетки, имеющие общую сторону.)

   Решение

Темы:    [ Обход графов ] [ Деревья ] [ Четность и нечетность ] [ Индукция (прочее) ]

Сложность: 4 Классы: 8,9

Прислать комментарий

Условие

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

Решение

  Разберём случай, когда граф не имеет нечётных вершин. Индукцией по числу рёбер графа докажем, что его можно обойти по циклу. База (граф без рёбер) очевидна.
  Шаг индукции. Рассмотрим произвольный связный граф, степени всех вершин которого чётны. Поскольку в этом графе нет висячих вершин, то он не является деревом, и, следовательно, в нём есть простой цикл. Временно удалим из графа рёбра этого цикла. При этом граф распадётся на несколько компонент связности, имеющих общие вершины с выкинутым циклом. В каждой компоненте все вершины чётны, и по предположению индукции каждую из этих компонент связности можно обойти по циклу. Теперь ясно как обойти требуемым образом исходный граф: обходим цикл и попадая в вершину, относящуюся к какой-то компоненте, обходим её, в конце возвращаясь в ту же вершину, после чего продолжаем движение по циклу.
  Доказательство для случая графа с двумя нечётными вершинами аналогично (нужно временно удалить путь, соединяющий две нечётные вершины).

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