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

Проект МЦНМО
при участии
школы 57
Задача 30809
Темы:    [ Обход графов ]
[ Степень вершины ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

Докажите, что связный граф с 2n нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно  n –1  раз и не проводя никакое ребро дважды.


Решение

Разобьём нечётные вершины на пары и каждую пару соединим новым ребром. Согласно задаче 30806 полученный граф можно обойти по циклу. Удалив новые рёбра, мы разобьём цикл на n частей.

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

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

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

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