ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 30806
Темы:    [ Обход графов ]
[ Деревья ]
[ Четность и нечетность ]
[ Индукция (прочее) ]
Сложность: 4
Классы: 8,9
В корзину
Прислать комментарий

Условие

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


Решение

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

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

книга
Автор Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания 1994
Название Ленинградские математические кружки
Издательство Киров: "АСА"
Издание 1
глава
Номер 13
Название Графы-2
Тема Теория графов
задача
Номер 028

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .