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

задан 10 Мар '14 11:54

10|600 символов нужно символов осталось
1

Разобьём все вершины графа на пары произвольным образом. Для $%i$%-й пары вершин добавим к графу новое ребро, соединяющие эти вершины. После этого получится связный граф, в котором все вершины имеют чётную валентность. Это значит, что в нём имеется эйлеров цикл. Его можно начать рисовать с любого ребра. Выберем какое-то из добавленных рёбер, и начнём рисовать граф с него. Этому соответствует процесс рисования исходного графа, если добавленные рёбра проводить "в воздухе". Отрывать карандаш от бумаги придётся $%n-1$% раз, потому что первое из добавленных рёбер мы проводим в самом начале, и этому ничего не соответствует. А для каждого из остальных дополнительных рёбер придётся отрывать карандаш от бумаги. Здесь надо заметить, что у нас был эйлеров цикл, и мы возвращаемся в исходную вершину. Это делается уже по "настоящим" рёбрам, то есть не по добавленным. И тогда ровно $%n-1$% добавленное ребро будет соответствовать отрыву карандаша от бумаги.

ссылка

отвечен 10 Мар '14 13:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×599

задан
10 Мар '14 11:54

показан
1331 раз

обновлен
10 Мар '14 13:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru