Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ158

Задача ММ158 предложена Олегом Полубасовым

Конкурсная задача ММ158 (ТГ-4) (7 баллов)

I. Города занумерованы от 1 до N. Дорога, непосредственно соединяющая города i и j, существует, если и только если |i-j| - простое число. Длина дороги равна |i-j|. Найти зависимость длины кратчайшего гамильтонова цикла от величины N.
II. Заменим в I |i-j| нат i+j. Найти зависимость длины кратчайшего гамильтонова цикла от величины N, при условии, что полученный граф гамильтонов.

Решение

Решение: I. При малых N кратчайший гамильтонов цикл находим прямым перебором:
При N < 5 гамильтоновых циклов нет.
При N = 5 минимальным будет цикл 1-3-5-2-4-1, длина 12 (цикл единственен с точностью до направления обхода).
При N = 6 минимальным будет цикл 1-3-5-2-4-6-1, длина 16 (цикл единственен с точностью до направления обхода).
При N = 7 минимальным будет цикл 1-3-5-7-2-4-6-1, длина 20 (цикл единственен с точностью до направления обхода).
При N = 8 минимальным будет цикл 1-3-6-8-5-7-2-4-1, длина 22 (цикл единственен с точностью до направления обхода).
При N = 9 минимальным будет цикл 1-3-8-6-9-7-5-2-4-1 или 1-3-5-8-6-9-7-2-4-1, длина 24 (минимальных циклов ровно два, с точностью до направления обхода).
При N > 9 построим цикл длины следующим способом:

:marathon:mm158.jpg

Для четных N «защелка» выглядит аналогично.

Докажем теперь, что этот гамильтонов путь минимален.
а) Длина пути от вершины i до вершины j не меньше |j-i|, при этом равенство достигается тогда и только тогда, когда в пути номера вершин строго монотонны, это следует из неравенства треугольника. б) Длина пути из 1 в 2 не меньше 5, при этом равенство достигается только в случае пути 1-4-2. Доказательство очевидно - напрямую из 1 в 2 попасть нельзя, следовательно в пути не меньше двух ребер, длиной не менее 2. Но два ребра длины 2 не меняют четность вершин, следовательно длина по крайней мере одного ребра не меньше 3. в) Аналогично, длина пути из N в N-1 не меньше 5, при этом равенство достигается только в случае пути N - (N-3) - (N-1). В гамильтоновом цикле есть три возможных порядка обхода вершин с номерами 1, 2, N-1, N (с точностью до направления обхода): 1. 1 - 2 - (N-1) - N. При этом длина пути не меньше 2N+6. (1)
2. 1 - 2 - N - (N-1). При этом длина пути не меньше 2N+6. (2)
3. 1 - N - 2 - (N-1). При этом длина пути не меньше 4N-8. (3)
При N > 9 путь в (3) заведомо длиннее: 4N-8 > 2N+6.

II. Длина гамильтонова пути a1-a2-a3-…-aN-1-aN-a1 в таком графе равна (a1+a2) + (a2+a3) + … + (aN-1+aN) + (aN+a1) = 2( 1 + 2 + … N-1 + N) = N(N+1).

Обсуждение

Обсуждение

Легко видеть, что в пункте II граф получается двудольным (смежные вершины могут быть только разной четности). Поскольку при нечетных N число вершин в долях получается разным, гамильтонова цикла в этом случае быть не может. При четных N > 2 гамильтоновы циклы для малых значений N легко строятся. Поскольку с ростом N число гпмильтоновых циклов лавинообразно возрастает, очевидно (хотя и не доказано строго никем из участников :-D), что гамильтоновы циклы есть при всех четных N > 2.

Можно показать, что в пункте I при N > 9 для четных N в кратчайшем гамильтоновом цикле реализуется только схема обхода (1), а для нечетных - схема обхода (2). Поэтому при N > 9 кратчайший гамильтонов цикл определен однозначно. Таким образом, случай N = 9 является особенным. Только для него существует два различных кратчайших гамильтоновых цикла.

Алексей Волошин задался вопросом о нахождении не кратчайших, а наоборот длиннейших гамильтоновых циклов для пункта (1). Очевидно, что эта длина не превосходит [N2/2] - длины наибольшего гамильтонова цикла в полном графе, в котором длина ребра из i в j равна |j-i| (см. A007590 в OEIS). При 4 < N < 12 эта оценка точна. Однако, при N = 12 наибольшая длина гамильтонова цикла в графе из I равна 70, а не 72.

Сергей Половинкин рассмотрел графы, возникающие при комбинировании условий пунктов I и II: дорога из i в j существует, i+j - просто, но ее длина равна |j-i|. Вот таблица зависимости длины кратчайшего гамильтонова цикла от N для этого типа графов.

Nd(N)
46
614
818
1020
1228
1448
1640
1852
2058

Бросается в глаза отсутствие монотонности. Общую формулу Сергею получить не удалось.

Награды

За правильное решение и некоторое обобщение задачи ММ158 Алексей Волошин и Сергей Половинкин получают по 8 призовых баллов. За верное решение задачи Виктор Филимоненков и Анатолий Казмерчук получают по 7 призовых баллов. Николай Дерюгин (допустивший ошибку для случая N=8) получает 6 призовых баллов. Автор задачи Олег Полубасов получает 7 призовых баллов.

Эстетическая оценка задачи - 4.9 балла.

Разбор задачи ММ158 подготовил Владимир Лецко


 

 


Страница: [[marathon:problem_158]]

marathon/problem_158.txt · Последние изменения: 2012/03/20 18:55 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006