Пусть в связном графе $%G$% ровно $%2k$% вершин имеют нечетную степень. Доказать, что в этом графе можно построить $%k$% таких путей, что каждое ребро графа $%G$% будет принадлежать только одному из этих путей.

задан 26 Окт '15 2:20

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

Разобьём $%2k$% вершин произвольным образом на пары. Вершины $%i$%-й пары соединим новым ребром $%e_i$%. Получится граф с чётными степенями вершин. В нём есть эйлеров цикл. Рассмотрим этот цикл в виде окружности, и удалим из него $%k$% рёбер вида $%e_i$%, которые попарно не имеют общих вершин. Окружность распадётся на $%k$% дуг, которые и образуют искомые $%k$% путей.

ссылка

отвечен 26 Окт '15 2:40

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

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

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

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

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

отмечен:

×477
×260
×156
×142

задан
26 Окт '15 2:20

показан
645 раз

обновлен
26 Окт '15 2:40

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

по почте:

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

по RSS:

Ответы

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

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