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


Содержание

ММ50

Задача ММ50 является прямым продолжением и обобщением задачи ММ13

Конкурсная задача ММ50 (13 баллов)

Зададим на множестве V = {1,2,3,…,n} структуру графа, полагая, что вершины x и y из V смежны тогда и только тогда, когда ¦x-y¦ = u или ¦x-y¦ = v, где u и v - некоторые фиксированные (для данного графа) натуральные числа (u меньше v). Полученный граф обозначим G(u,v,n).

1. Найти необходимые и достаточные условия для того, чтобы граф G(u,v,n) был:
1.1) связен;
1.2) цепью;
1.3) циклом;
(3 балла)

2. Пусть 2u < v, НОД(u,v) = 1, u+v - нечетно. Доказать, что найдется такое n0, что для всех n > n0 граф G(u,v,n) - гамильтонов (т.е. в нем есть простой цикл, содержащий все вершины). (10 баллов)

Замечание.
Я убежден, что условие «2u меньше v» в пункте 2 является избыточным. Однако на момент опубликования задачи я не умел доказывать утверждение пункта 2 без этого ограничения.

Решение

Ребро, инцидентное вершинам x и x+u, будем называть u-ребром. Аналогично вводится понятие v-ребра.

Лемма 1. При n ≤ u+v-1 количество ребер графа G(u,v,n) равно 2n-u-v.
Доказательство.
Очевидно, что в G(u,v,n) будет n-u u-ребер и n-v v-ребер.

Лемма 2. Граф G(u,v,n) связен тогда и только тогда, когда u и v взаимно просты и n ≤ u+v-1 или u = 1.
Доказательство.
При n < u+v-1 число ребер графа меньше n-1 (за исключением случая u = 1, для которого связность G(u,v,n) очевидна) и поэтому он не может быть связен.
Пусть (u, v) = d. Очевидно, что при d > 1 вершины, принадлежащие разным классам вычетов по модулю d, лежат в разных компонентах связности графа G(u,v,n).
Пусть d = 1 и n ≤ u+v-1. Обозначим m = u+v, тогда (u, m) = (u, u+v) = (u, v) = 1 и числа u, 2u, 3u,…, mu образуют полную систему вычетов по модулю m. Заменим каждое из этих чисел его остатком от деления на m. Тогда, удалив последнее число (равное 0), мы получим в графе G(u,v,n) цепь с концами в вершинах u и v, содержащую все вершины с номерами от 1 до u+v-1. Легко видеть, что для любой вершины графа существует путь (например, из u-ребер) в некоторую из вершин данной цепи. Тем самым доказана связность графа.

Лемма 3. При (u,v) = 1 граф G(u,v,u+v) является циклом.
Доказательство.
Заметим, что вершина u+v смежна концам цепи, описанной в Лемме 2.

Ясно, что при n, большем u+v, граф G(u,v,n) не может быть ни цепью, ни циклом, так как в этом случае число его вершин меньше числа ребер.
Леммы 1-3 дают ответы на вопросы первого пункта задачи. А именно:
1) G(u,v,n) связен тогда и только тогда, когда (u,v) = 1 и n ≤ u+v-1 или u = 1;
2) G(u,v,n) - цепь тогда и только тогда, когда (u,v) = 1 и n = u+v-1 или u = 1 и n < v;
3) G(u,v,n) - цикл тогда и только тогда, когда (u,v) = 1 и n = u+v.

В дальнейшем всегда будем полагать, что числа u и v взаимно просты.

Доказательство утверждения из второго пункта проведем при слегка более слабых ограничениях (2u ≤ v вместо 2u < v).

Лемма 4. При 2u ≤ v граф G(u,v,3u+v) гамильтонов.
Доказательство.
Граф G(u,v,3u+v) имеет 3u v-ребер и v+2u u-ребер. Удалим из него 2u u-ребер:
{u+1, 2u+1}, {u+2, 2u+2},:, {2u, 3u}, {v+1, v+1+u},{v+2, v+2+u},…, {v+u, v+2u}.
Оставшийся граф (обозначим его G') имеет v u-ребер и 3u v-ребер. Степени всех вершин этого графа равны 2 (в этом месте используется ограничение 2u ≤ v). Поэтому G' является объединением циклов.
Зададим в каждом цикле направление обхода вершин. Будем называть ребро «положительным», если вторая (при заданном направлении обхода) вершина ребра больше первой и «отрицательным» в противном случае. Пусть цикл содержит k1 положительных u-ребер, k2 отрицательных u-ребер, m1 положительных v-ребер и m2 отрицательных v-ребер. Ясно, что суммарный баланс (k1-k2)u+(m1-m2)v должен быть равен 0. Назовем цикл тривиальным, если k1 = k2 и m1 = m2.
Поскольку среди чисел 3u и v есть хотя бы одно нечетное, по крайней мере, один из циклов должен быть нетривиальным, т.е. линейная комбинация чисел u и v должна обратиться нуль при ненулевых коэффициентах. Но u и v взаимно просты, поэтому их линейная комбинация не может обратиться в нуль, если коэффициент при u (который, не нарушая общности рассуждений, можно считать положительным) будет меньше v. Поэтому все v u-ребер графа G' войдут в один нетривиальный цикл. Но цикл, очевидно, не может состоять из одних только v-ребер. Поэтому и все v-ребра войдут в тот же самый цикл.
Окончательно получим, что для этого цикла k1 = v, k2 = 0, m1 = u, m2 = 2u. Таким образом, граф G' является циклом и граф G(u,v,3u+v) гамильтонов.

Лемма 5 (о «склейке»). Если граф G(u,v,n) гамильтонов, то графы G(u,v,u+v+n) и G(u,v,3u+v+n) также гамильтоновы.
Доказательство.
Так как степень вершины 1 графа G(u,v,n) равна 2, гамильтонов цикл этого графа обязательно содержит ребро a = {1, 1+u}. По той же причине гамильтонов цикл графа G(u,v,u+v) содержит ребро b = {u+1, 2u+1}.
Прибавим ко всем вершинам графа G(u,v,n) по u+v. При этом гамильтонов цикл графа G(u,v,n) перейдет в некоторый цикл графа G(u,v,u+v+n), содержащий вершины с u+v+1 по u+v+n, ребро a перейдет в ребро a' = {u+v+1, 2u+v+1}.
Таким образом, в графе G(u,v,u+v+n) есть два цикла, один из которых содержит вершины с 1 по u+v, а другой вершины с u+v+1 по u+v+n. Удалим из первого цикла u-ребро b, а из второго u-ребро a', а вместо них добавим v-ребра {u+1, u+v+1} и {2u+1, 2u+v+1}. В результате получим гамильтонов цикл графа G(u,v,u+v+n).
Доказательство гамильтоновости графа G(u,v,3u+v+n) проводится аналогично. При этом в случае, когда 3u < v, замене на v-ребра подлежат u-ребра {3u+1, 4u+1} и {3u+v+1, 4u+v+1}.
Если же 3u > v, то можно заменить на v-ребра {u+v+1, u+2v+1}, {2u+v+1, 2u+2v+1} u-ребра {u+v+1, 2u+v+1} и {u+2v+1, 2u+2v+1}. Наконец, если 3u = v, то, в силу взаимной простоты u и v, u = 1 и v = 3. В этом случае в графе G(1,3,6), кроме гамильтонова цикла, существование которого обосновано в Лемме 4, есть еще один (тривиальный) гамильтонов цикл: [1, 2, 3, 6, 5, 4]. Тогда замене на 3-ребра подлежат ребра {4, 5} и {7, 8} этого цикла.

Основная теорема.
Пусть 2u ≤ v. Тогда:
1) если u и v взаимно простые числа разной четности, то, начиная с некоторого количества вершин n0, зависящего от u и v, все графы будут гамильтоновы;
2) если u и v взаимно простые числа одной четности, то, начиная с некоторого количества вершин n0, зависящего от u и v, для любого четного n больше n0, все графы будут гамильтоновы.
Доказательство.
Если числа u и v разной честности, то (3u+v, u+v) = 1. Поэтому, начиная с n0 = (3u+v-1)(u+v-1), любое натуральное число представимо в виде линейной комбинации чисел 3u+v и u+v с целыми неотрицательными коэффициентами (см. обсуждение марафонской задачи №37). Следовательно, на основании Лемм 3, 4, 5, все графы G(u,v,n), где n ≤ n0, будут гамильтоновы.
Если же числа u и v нечетны, то (3u+v,u+v) = 2 и, начиная с n0 = 2((3u+v)/2-1)(u+v)/2-1), все графы G(u,v,n), где n - четно и n ≤ n0, будут гамильтоновы.

Oбсуждение

Значение (3u+v-1)(u+v-1), полученное в основной теореме является верхней границей для n0. Однако, для большинства значений u и v все графы G(u,v,n) являются гамильтоновыми, начиная с некоторого значения n1, меньшего n0. Это объясняется тем, что гамильтоновы циклы в графах G(u,v,n) могут возникать не только в результате «склейки» циклов для графов с меньшим числом вершин. Аналогичная ситуация возникает и для оценки n0 во втором пункте основной теоремы.

Дмитрий Милосердов и Олег Полубасов предложили более простое (чем приведенное в решении) доказательство гамильтоновости графа G(u,v,3u+v). Более того, оно проясняет появление в решении числа 3u+v:
Возьмем цикл G(u,v,u+v) и заменим каждое из u-ребер {u+k, 2u+k} тройкой ребер {u+k, u+k+v}, {u+k+v, 2u+k+v}, {2u+k+v, 2u+v}. В результате получим гамильтонов цикл в G(u,v,3u+v).

Легко видеть, что в случае, когда все три числа u, v, n - нечетны, граф G(u,v,n) не может быть гамильтоновым.

Ограничение 2u ≤ v существенно для приведенного доказательства основной теоремы. Но я изначально предполагал, что оно избыточно. Так и оказалось.

Андрей Винокуров доказал, что все графы G(u,u+1,n) будут гамильтоновы, начиная с некоторого n0.

Олег Полубасов смог полностью избавиться от ограничения 2u ≤ v, доказав, что и в случае u < v < 2u все графы G(u,v,n) со взаимно простыми u и v и нечетным u+v будут гамильтоновы, начиная с некоторого n0.

Он разбил случай u < v < 2u на четыре подслучая:
1) v = u+1. В этом случае гамильтоновым будет граф G(u,v,u(u+v)+1);
2) 3u < 2v. В этом случае гамильтоновым будет граф G(u,v,u+3v) (тем самым восстанавливается некая симметрия случаю 2u < v);
3) 3u > 2v и a = [u/(v-u)] - нечетно. В этом случае гамильтоновым будет граф G(u,v,au+(a+2)v) (зачечу, что пункт 2 есть частный случай пункта 3);
4) 3u > 2v и a = [u/(v-u)] - четно. В этом случае гамильтоновым будет граф G(u,v,(a+1)u+(a+3)v);
Во всех случаях количество вершин указанных графов взаимно просто с u+v и имеется возможность «склеивать» циклы.

Подробнее, с этими идеями можно познакомиться здесь.

Награды

За правильное решение задачи MM50 Дмитрий Милосердов получает 14 призовых баллов (один поощрительный балл добавлен за более изящное, чем авторское, доказательство гамильтоновости G(u,v,3u+v).
Андрей Винокуров (который, как обычно, рассмотрел ряд смежных вопросов) получает 16 призовых баллов.
Олег Полубасов, снявший ограничение 2u < v, получает 20 призовых баллов.
Влад Франк (решивший MM50.2 лишь частично) получает 7 призовых баллов.

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


 

 


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

marathon/problem_50.txt · Последние изменения: 2016/05/31 12:47 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006