Набор задач по графам

[jrock]

Я собираюсь порешать задачки по графам далее из домашних заданий.

Задача 4.1.
В графе с $n \geqslant 10$ вершинами степени вершин равные $d_1 \leqslant d_2 \leqslant ... \leqslant d_{n} $. При том $d_i + d_{n-i} \geqslant n$. Докажите, что в графе есть гамильтонов цикл.

Доказательство.
Воспользуемся теоремой Поше.
Пусть $G $ имеет $p \geqslant 3 $ вершин. Если для всякого $ n, 1 \leqslant n \leqslant (p-1)/2$ , число вершин со степенями, не превосходящими n, меньше чем n, и для нечетного $p$ число вершин степени $ (p-1)/2 $ не превосходит $ (p-1)/2 $, то $G$ — гамильтонов граф.
Подробнее тут: http://rain.ifmo.ru/cat/view.php/theory ... onian-2005

Попробуем опровергнуть условие задачи. Пусть есть граф $G$ для которого выполнено неравенство для степеней вершин. Сделаем граф максимально негамильтоновым (добавление любого ребра сделает его гамильтоновым). Если мы докажем, что граф будет иметь гамильтоновый цикл даже в том случае, когда мы сказали что он "максимально насыщенный", то получиться, что мы докажем противоречие. Тогда если мы добавляли какое-то ребро, предполагая что после этого граф стал насыщенный, но еще не гамильтоновый, то мы не могли добавлять ни одного ребра, а он уже был насыщенный. И опятьже, если он был изначально насыщенный, а мы доказали что он имеет г.цикл, то так и получим противотечение.

(Оффтоп)

Извиняюсь что расписываю последнее предложение, т.к. мне вот лично было не понятно док-во с http://rain.ifmo.ru/cat/view.php/theory ... onian-2005 где пользовались аналогичным рассуждением.

При том, если изначально был граф, в котором выполнялось условие задачи, а потом добавилось новое ребро, то все равно условие задачи будет выполняться: если где-то неравенство нарушилось, то мы можем всегда отсортировать последовательность, а сумма от этого не уменьшиться (мы ведь только увеличиваем степени), т.к. до добавления ребра последовательность тоже была отсортирована.
Теперь пусть $G$ - насыщенный. Еще раз, добавление любого ребра приведет к появлению г.цикла. Это гарантирует наличие г.пути между любыми двумя вершинами (иначе противоречие). Тогда если первая вершина не соединена с вершиной $n-1$ (нумеруем в порядке возрастания степени), то автоматически получится г.цикл (был г.путь между всеми парами вершин), здесь пользуюсь критерием Дирака.
Но $d(n-1) \leqslant d(n)$, значит первая вершина соединена и с вершиной $n$.
Теперь, если посмотреть на любую вершину из первой половины последовательности, то видно, что

$v_1$ - \{ v_{n-1}, v_n \}
$v_2$ - \{ v_{n-2}, v_{n-1}, v_n \}

и т.д.

Поэтому получаем аналогичными рассуждениями для всех вершин, что $d(i) \geqslant i + 1$ для всех $ i \leqslant n-2 $

Теперь в точности выполняется критерий Поше. Значит, противоречие.

Вот теперь мне не понятно почему здесь написано именно $ n \geqslant 10$

P.S. может я пишу много, да еще и неправильно или неточно. Мне такие доказательства немного непривычны.

[jrock]

Есть опечатка в тексте выше:
нужно заменить

Цитата:

Поэтому получаем аналогичными рассуждениями для всех вершин, что $d(i) \geqslant i+1 $ для всех $ i \leqslant n-2$

на

Цитата:

Поэтому получаем аналогичными рассуждениями для всех вершин, что $d(i) \geqslant i+1 $ для всех $ i \leqslant n/2$

Еще хочу добавить. Я прислал решение товарищу, и возник вопрос хороший:

Цитата:

Зачем доказывать что-то дальше, после того как мы показали, что $d(v_1) \geqslant d(v_{n-1})$

Дело в том, что нужно доказать что не найдется хотя бы одна пара несмежных вершин (для противоречия). Т.к. если бы нам было достаточно только этого неравенства, то мы таким же образом насыщали граф и приходили к противоречию, доказав, что для любых графов, где сумма степени первой и предпоследней (в порядке возрастания степеней вершины) была бы не меньше, чем кол-во вершин в графе, то граф гамильтонов. Это, очевидно, не так.

Еще одна неточность есть в том, что когда я говорил, что пользуемся критерий Дирака, то на самом деле я пользовался леммой, необходимой для его доказательства:
Если в графе с $k$ вершинами имеется гамильтонов путь, и сумма концов этого пути не меньше, чем $k$, то в нем имеется и гамильтонов цикл.
Док-во этого факта тут: https://dl.dropbox.com/u/15433464/grafin.pdf (стр. 10)

[jrock]

Задача 4.2.
Докажите, что связный граф с $2n$ нечетными вершинами можно нарисовать, оторвав от бумаги ровно $n-1$ раз и не проводя никакое ребро дважды.

Доказательство
Необходимо покрыть весь граф $n$ реберно-простыми путями.
Будем доказывать по индукции сверху вниз по кол-ву вершин. База для графа из двух нечетных вершин верна - это просто один эйлеров путь.
Теперь, если имеется граф из $2n$ вершин, то выберем две любые нечетные вершины. Проведем между ними реберно-простой путь. Ясно, что теперь кол-во нечетных вершин уменьшилось на две: степень исходной и конечной вершины уменьшились на единичку. Остальные вершины не могли изменить свою четность: мы либо не входили в какую-то вершину, либо заходили и не останавливались.
Осталось $n-2$ отрывания для отрисовки оставшегося графа.

Если новая компонента не появилась, то получился граф из $2(n-1)$ вершин. Его по предположению индукции можно нарисовать за $n-2$ отрывания. Получается, что условие выполняется.

Если появилась новая компонента, состоящая из $2p$ нечетных вершин (в любом графе четное число нечетных вершин) и оставшийся граф из $2q$ вершин, где $p+q = n-1$ , то по предположению индукции за $p-1$ отрывания нарисуем новую компоненту и за $q-1$ отрывания карандаша - правую, еще за $1$ мы оторвем карандаш от новой и перенесем на правую. В итоге получилось $(p-1)+(q-1) + 1 = (p+q) - 1 = n-2$ отрывания карандаша.

[jrock]

Есть еще один случай, который не был рассмотрен в задаче 4.2.
Что если после, как был проведен первый реберно-простой путь появилась новая компонента, у которой все вершины имеют четную степень.
Так как это компонента появилась, то значит, что до этого был путь, проходящий через одну из вершин этой новой компоненты, которая состоит только из четных вершин (иначе получилось бы, что граф был несвязный). Значит, можно было войти в какую-то вершину из новой компоненты и пройтись по ней эйлеровым циклом.


P.S. Обращение к модераторам. Что лучше: писать задачи здесь или создавать ветку новую? Если не будет ответа, то буду создавать новую ветку, а то боюсь что тут скоро будут просто рулоны текстов.