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

задан 14 Ноя '17 16:15

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

Индукция по числу вершин. Для двух вершин это очевидно. Пусть для графа с n вершинами путь v(1)->...->v(n) уже найден. Добавляем новую (n+1)-ю вершину v. Если v->v(1), то есть имеется ориентированное ребро из v в v(1), то всё просто. То же самое, если v(n)->v. Значит, рассматриваем случай v(1)->v, v->v(n).

Раскрасим вершины пути v(1)->...->v(n) в два цвета. Если v(i)->v, то i-я вершина будет красная. Если v->v(i), то синяя. У нас первая вершина красная, последняя синяя. Тогда можно найти момент самой первой смены красного цвета на синий, то есть найти такое i, для которого v(i)->v (красная), но v->v(i+1) (синяя). Этот фрагмент надо подставить в путь, получая v(1)->...->v(i)->v->v(i+1)->...->v(n).

Это теорема из теории графов, доказанная в 30-х годах прошлого века.

ссылка

отвечен 14 Ноя '17 17:21

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

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

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

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

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

отмечен:

×696
×151

задан
14 Ноя '17 16:15

показан
875 раз

обновлен
14 Ноя '17 17:21

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

по почте:

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

по RSS:

Ответы

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

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