Добрый вечер! Прошу помощи в проверке решения задачи (опять по дискретке).
Вершины неориентированного графа (`n` штук) расположены на окружности и соединены через одну и через `3` (соседние вершины не соединены). При каких `n` в этом графе существует эйлеров цикл?
Сразу оговорим признак наличия эйлерова цикла: 1)граф связен 2) отсутствуют вершины нечетной степени. Про степени: во всех случаях (кроме `n=2` и `n=4`) для всех вершин степени будут четными, так для для каждой вершины однозначно поставлены в соответствие 4 вершины: две вершины "через три" (назад и вперед) и еще две "через одну" (вперед и назад). Теперь про связность: здесь будут проблемы, так как иногда у нас будет происходить зацикливание. Итак, выпишем в ряд подряд натуральные числа: `1 2 3 4 5 6 7 8 9 10 11 12.....n 1 2 3 4...n 1 2 3......n..... `(где 1-первая вершина, 2-вторая и тд) будем формировать эту цепь для конкретных `n`, например для `n=6`: `1 2 3 4 5 6 1 2 3 4 5 6 1 ....`. Итак, эта цепь нужна для того, чтобы показать алгоритм соединения вершин через 1 и через 3. Вершины соединенные через одну образуют арифм. прогрессию: `a_1=1, d=2` (например 1 соединена с 3, 3 с 5 и тд). Вершины соединенные через 3 образуют арифметическую прогрессию `a_1=1, d=4` (например, 1 переходит в 5, 5 в 9 и тд). Идя с начала нашего ряда нам нужно чтобы наши прогрессии на двоих прошли через каждое числа (от 1 до `n`, можно чтобы они были разными, главное чтобы наш алгоритм прошел через каждую-это и будет связностью графа) и при этом, чтобы они пересеклись (или одна из них пройдет все числа, при этом она, бузесловно, пересечется со второй). Так вот, если `n` четное, то у нас проблема возникает-в первой прогрессии только нечетные числа, а во второй только четные=> они никогда не пересекутся и ни одна из них не пройдет всех значений (одна не пройдет нечетные числа, другая-четные). Значит для четных `n` не будет граф связен. Теперь для нечетных `n`: тут достаточно доказать, что только при проходе "через один" будут охвачены все вершины: в первом проходе будут охвачены все нечетные числа: `1-3-5-7...-n` дальше произойдет смена четности (так как подряд в нашем ряду будет идти `n 1` и оба этих числа нечетны) и цикл пройдет через все четные числа: `2-4-6....n-1` и из `n-1` мы опять попадем в `1`. Итак, граф будет связен. Итого: только для нечетных.
Скорее всего, я не очень понятно выразил свою идею, но все же, кто попробует взяться за задачу-спасибо!)
Вершины неориентированного графа (`n` штук) расположены на окружности и соединены через одну и через `3` (соседние вершины не соединены). При каких `n` в этом графе существует эйлеров цикл?
Сразу оговорим признак наличия эйлерова цикла: 1)граф связен 2) отсутствуют вершины нечетной степени. Про степени: во всех случаях (кроме `n=2` и `n=4`) для всех вершин степени будут четными, так для для каждой вершины однозначно поставлены в соответствие 4 вершины: две вершины "через три" (назад и вперед) и еще две "через одну" (вперед и назад). Теперь про связность: здесь будут проблемы, так как иногда у нас будет происходить зацикливание. Итак, выпишем в ряд подряд натуральные числа: `1 2 3 4 5 6 7 8 9 10 11 12.....n 1 2 3 4...n 1 2 3......n..... `(где 1-первая вершина, 2-вторая и тд) будем формировать эту цепь для конкретных `n`, например для `n=6`: `1 2 3 4 5 6 1 2 3 4 5 6 1 ....`. Итак, эта цепь нужна для того, чтобы показать алгоритм соединения вершин через 1 и через 3. Вершины соединенные через одну образуют арифм. прогрессию: `a_1=1, d=2` (например 1 соединена с 3, 3 с 5 и тд). Вершины соединенные через 3 образуют арифметическую прогрессию `a_1=1, d=4` (например, 1 переходит в 5, 5 в 9 и тд). Идя с начала нашего ряда нам нужно чтобы наши прогрессии на двоих прошли через каждое числа (от 1 до `n`, можно чтобы они были разными, главное чтобы наш алгоритм прошел через каждую-это и будет связностью графа) и при этом, чтобы они пересеклись (или одна из них пройдет все числа, при этом она, бузесловно, пересечется со второй). Так вот, если `n` четное, то у нас проблема возникает-в первой прогрессии только нечетные числа, а во второй только четные=> они никогда не пересекутся и ни одна из них не пройдет всех значений (одна не пройдет нечетные числа, другая-четные). Значит для четных `n` не будет граф связен. Теперь для нечетных `n`: тут достаточно доказать, что только при проходе "через один" будут охвачены все вершины: в первом проходе будут охвачены все нечетные числа: `1-3-5-7...-n` дальше произойдет смена четности (так как подряд в нашем ряду будет идти `n 1` и оба этих числа нечетны) и цикл пройдет через все четные числа: `2-4-6....n-1` и из `n-1` мы опять попадем в `1`. Итак, граф будет связен. Итого: только для нечетных.
Скорее всего, я не очень понятно выразил свою идею, но все же, кто попробует взяться за задачу-спасибо!)
-
-
29.01.2014 в 22:56Для нечетных n вы показали, что существует эйлеров цикл.
Для четных n с помощью соединения через 1 мы получаем два цикла, не пересекающихся по вершинам, т.е. две компоненты связности. У них, в свою очередь, может быть четное и нечетное число вершин.
Теперь заметим, что проход через 3 вершины всегда оставляет нас в той же компоненте связности и соответствует в ней проходу через 1 (если рассматривать каждую компоненту отдельно).
Если n/2 нечетно, то попадаем в условия, которые мы уже рассмотрели. Получаем две компоненты связности, в каждой из которых есть эйлеров цикл, но в графе целиком нет.
Если же n/2 четно, проход через 3 снова в каждой компоненте создаст циклы, не пересекающиеся по вершинам. Такая рекурсивная процедура... Дальше ее рассматривать не обязательно — главный вывод, что при четном n и вершины, соединенные через 1, и вершины, соединенные через 3 находятся в одной из двух компонент связности.
Так вот, если n четное, то у нас проблема возникает-в первой прогрессии только нечетные числа, а во второй только четные=> они никогда не пересекутся и ни одна из них не пройдет всех значений (одна не пройдет нечетные числа, другая-четные).
Вот этот момент неясен (точнее, плохо написан). Что такое здесь вторая прогрессия? Если та, которую вы выписали: с a_1=1, d=4, то это не так. Если вы имели в виду не это, то нужно как-то по-другому написать.
-
-
29.01.2014 в 23:07-
-
29.01.2014 в 23:47-
-
30.01.2014 в 11:07-
-
30.01.2014 в 11:19-
-
30.01.2014 в 12:15