 |
|
 |
 |
 | Карта сайта |
 | Недавние изменения |
 | Поиск |
 | Вы посетили |
 | История страницы |
 | Вход |
Различия
Здесь показаны различия между двумя версиями данной страницы.
|
marathon:problem_50 [2016/05/31 11:33] letsko создано |
marathon:problem_50 [2016/05/31 11:47] (текущий) letsko |
||
|---|---|---|---|
| Строка 6: | Строка 6: | ||
| Зададим на множестве V = {1,2,3,...,n} структуру графа, полагая, что вершины x и y из V смежны тогда и только тогда, когда | Зададим на множестве V = {1,2,3,...,n} структуру графа, полагая, что вершины x и y из V смежны тогда и только тогда, когда | ||
| - | |x-y|=u или |x-y|=v, где u и v - некоторые фиксированные (для данного графа) натуральные числа (u меньше v). Полученный граф обозначим G(u,v,n). | + | ¦x-y¦ = u или ¦x-y¦ = v, где u и v - некоторые фиксированные (для данного графа) натуральные числа (u меньше v). Полученный граф обозначим G(u,v,n). |
| 1. Найти необходимые и достаточные условия для того, чтобы граф G(u,v,n) был:\\ | 1. Найти необходимые и достаточные условия для того, чтобы граф G(u,v,n) был:\\ | ||
| Строка 23: | Строка 23: | ||
| Ребро, инцидентное вершинам x и x+u, будем называть u-ребром. Аналогично вводится понятие v-ребра. | Ребро, инцидентное вершинам x и x+u, будем называть u-ребром. Аналогично вводится понятие v-ребра. | ||
| - | Лемма 1. При n ≤ u+v-1 количество ребер графа G(u,v,n) равно 2n-u-v.\\ | + | //Лемма 1//. При n ≤ u+v-1 количество ребер графа G(u,v,n) равно 2n-u-v.\\ |
| Доказательство.\\ | Доказательство.\\ | ||
| Очевидно, что в G(u,v,n) будет n-u u-ребер и n-v v-ребер. | Очевидно, что в G(u,v,n) будет n-u u-ребер и n-v v-ребер. | ||
| - | Лемма 2. Граф G(u,v,n) связен тогда и только тогда, когда u и v взаимно просты и n ≤ u+v-1 или u = 1.\\ | + | //Лемма 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) очевидна) и поэтому он не может быть связен.\\ | При n < u+v-1 число ребер графа меньше n-1 (за исключением случая u = 1, для которого связность G(u,v,n) очевидна) и поэтому он не может быть связен.\\ | ||
| Строка 33: | Строка 33: | ||
| Пусть 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-ребер) в некоторую из вершин данной цепи. Тем самым доказана связность графа. | Пусть 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) является циклом.\\ | + | //Лемма 3//. При (u,v) = 1 граф G(u,v,u+v) является циклом.\\ |
| Доказательство.\\ | Доказательство.\\ | ||
| Заметим, что вершина u+v смежна концам цепи, описанной в Лемме 2. | Заметим, что вершина u+v смежна концам цепи, описанной в Лемме 2. | ||
| Строка 47: | Строка 47: | ||
| Доказательство утверждения из второго пункта проведем при слегка более слабых ограничениях (2u ≤ v вместо 2u < v). | Доказательство утверждения из второго пункта проведем при слегка более слабых ограничениях (2u ≤ v вместо 2u < v). | ||
| - | Лемма 4. При 2u ≤ v граф G(u,v,3u+v) гамильтонов.\\ | + | //Лемма 4//. При 2u ≤ v граф G(u,v,3u+v) гамильтонов.\\ |
| Доказательство.\\ | Доказательство.\\ | ||
| Граф G(u,v,3u+v) имеет 3u v-ребер и v+2u u-ребер. Удалим из него 2u u-ребер:\\ | Граф G(u,v,3u+v) имеет 3u v-ребер и v+2u u-ребер. Удалим из него 2u u-ребер:\\ | ||
| Строка 56: | Строка 56: | ||
| Окончательно получим, что для этого цикла k<sub>1</sub> = v, k<sub>2</sub> = 0, m<sub>1</sub> = u, m<sub>2</sub> = 2u. Таким образом, граф G' является циклом и граф G(u,v,3u+v) гамильтонов. | Окончательно получим, что для этого цикла k<sub>1</sub> = v, k<sub>2</sub> = 0, m<sub>1</sub> = u, m<sub>2</sub> = 2u. Таким образом, граф G' является циклом и граф G(u,v,3u+v) гамильтонов. | ||
| - | Лемма 5 (о "склейке"). Если граф G(u,v,n) гамильтонов, то графы G(u,v,u+v+n) и G(u,v,3u+v+n) также гамильтоновы.\\ | + | //Лемма 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}.\\ | Так как степень вершины 1 графа G(u,v,n) равна 2, гамильтонов цикл этого графа обязательно содержит ребро a = {1, 1+u}. По той же причине гамильтонов цикл графа G(u,v,u+v) содержит ребро b = {u+1, 2u+1}.\\ | ||
| Строка 65: | Строка 65: | ||
| Наконец, если 3u = v, то, в силу взаимной простоты u и v, u = 1 и v = 3. В этом случае в графе G(1,3,6), кроме гамильтонова цикла, существование которого обосновано в Лемме 4, есть еще один (тривиальный) гамильтонов цикл: [1, 2, 3, 6, 5, 4]. Тогда замене на 3-ребра подлежат ребра {4, 5} и {7, 8} этого цикла. | Наконец, если 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. Тогда:\\ | Пусть 2u ≤ v. Тогда:\\ | ||
| 1) если u и v взаимно простые числа разной четности, то, начиная с некоторого количества вершин n<sub>0</sub>, зависящего от u и v, все графы будут гамильтоновы;\\ | 1) если u и v взаимно простые числа разной четности, то, начиная с некоторого количества вершин n<sub>0</sub>, зависящего от u и v, все графы будут гамильтоновы;\\ | ||
| Строка 94: | Строка 94: | ||
| 4) 3u > 2v и a = [u/(v-u)] - четно. В этом случае гамильтоновым будет граф G(u,v,(a+1)u+(a+3)v);\\ | 4) 3u > 2v и a = [u/(v-u)] - четно. В этом случае гамильтоновым будет граф G(u,v,(a+1)u+(a+3)v);\\ | ||
| Во всех случаях количество вершин указанных графов взаимно просто с u+v и имеется возможность "склеивать" циклы. | Во всех случаях количество вершин указанных графов взаимно просто с u+v и имеется возможность "склеивать" циклы. | ||
| + | |||
| + | Подробнее, с этими идеями можно познакомиться {{:marathon:mm50.pdf|здесь}}. | ||
| **Награды** | **Награды** | ||