Чему равно максимальное число попарно не пересекающихся по ребрам Гамильтоновых циклов в графе K11 ?

задан 29 Сен '17 0:29

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

Полный граф на n вершинах имеет n(n-1)/2 рёбер. В гамильтонов цикл входит n из них. Поэтому независимых циклов имеется не более [(n-1)/2]. Известно, что эта оценка является точной.

В случае, когда n является простым, такие циклы легко строятся вручную. При n=11 их надо построить 5. Это делается так: в первом цикле прибавляем по 1 к номерам вершин: 1-2-3-...-10-11-1. Во втором -- по 2 (по модулю 11). И так далее, и в пятом цикле идёт прибавление по 5. Это даёт 1-6-11-5-10-4-9-3-8-2-7-1. Простота числа n гарантирует, что мы вернёмся в 1, не получая "малый" цикл в случае делителя числа n.

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

ссылка

отвечен 29 Сен '17 1:35

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

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

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

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

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

отмечен:

×1,479

задан
29 Сен '17 0:29

показан
340 раз

обновлен
29 Сен '17 1:35

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

по почте:

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

по RSS:

Ответы

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

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