Викиконспекты - Вклад участника [ru]

Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

2013-12-06T18:08:36Z

188.162.64.100: /* Описание алгоритма */

__TOC__
== Описание алгоритма ==
Пусть у нас есть граф <tex>\mathbb{G} = \left \langle \mathbb{V, E} \right \rangle</tex>, удовлетворяющий условию [[Теорема Дирака|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь <tex>n = \left | \mathbb{V}\right |</tex> раз будем делать следующую операцию:

* Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе <tex>\mathbb{G}</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
* Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j < i - j</tex> (то есть <tex>j</tex> пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>-й позиции), а также, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

Таким образом после <tex>n</tex> итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

== Псевдокод ==
{| width = 100%
|-
|
Queue queue; // создаем очередь
for i = 0 to n - 1 //
queue.pushback(v[i]) // добавляем в очередь все вершины графа
for k = 0 to n - 1 // пока не проделано нужное количество итераций
if !exist(queue.at(0), queue.at(1)) // проверяем существования ребра между первой и второй вершинами очереди
queue.swapSubQueue(2, find_vertex()) // если, не существует, то меняем порядок вершин в очереди, со второй до
// найденной, удовлетворяющей нас позиции

|width = "310px" |
|}

== Доказательство алгоритма ==
Для доказательства корректности алгоритма достаточно показать:

* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.
* После <tex>n</tex> итераций между каждой парой соседних вершин очереди существует ребро.

Докажем первое. Рассмотрим множество <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}</tex>, состоящее из вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}</tex>, вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4,...,n\}</tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует.

Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_2</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), а таких пар изначально не более <tex>n</tex>. Откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.

== Сложность алгоритма ==
Алгоритм работает за <tex>O(n^2)</tex>. Действительно, количество итераций внешнего цикла <tex>\mathrm{for}</tex> всегда равно <tex>n</tex>. Поиск вершины, удовлетворяющей заданному условию тоже работает за <tex>O(n)</tex>, итого время работы <tex>O(n^2)</tex>.

== См.также ==
*[[Гамильтоновы графы]]
*[[Теорема Оре]]
*[[теорема Дирака|Теорема Дирака]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

2013-12-06T18:08:03Z

188.162.64.100: /* Доказательство алгоритма */

__TOC__
== Описание алгоритма ==
Пусть у нас есть граф <tex>\mathbb{G} = \left \langle \mathbb{V, E} \right \rangle</tex>, удовлетворяющий условию [[Теорема Дирака|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь <tex>n = \left | \mathbb{V}\right |</tex> раз будем делать следующую операцию:

* Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе <tex>\mathbb{G}</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
* Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j < i - j</tex> (то есть <tex>j</tex> пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>-й позиции), а так же, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

Таким образом после <tex>n</tex> итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а так же существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

== Псевдокод ==
{| width = 100%
|-
|
Queue queue; // создаем очередь
for i = 0 to n - 1 //
queue.pushback(v[i]) // добавляем в очередь все вершины графа
for k = 0 to n - 1 // пока не проделано нужное количество итераций
if !exist(queue.at(0), queue.at(1)) // проверяем существования ребра между первой и второй вершинами очереди
queue.swapSubQueue(2, find_vertex()) // если, не существует, то меняем порядок вершин в очереди, со второй до
// найденной, удовлетворяющей нас позиции

|width = "310px" |
|}

== Доказательство алгоритма ==
Для доказательства корректности алгоритма достаточно показать:

* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.
* После <tex>n</tex> итераций между каждой парой соседних вершин очереди существует ребро.

Докажем первое. Рассмотрим множество <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}</tex>, состоящее из вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}</tex>, вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4,...,n\}</tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует.

Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_2</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), а таких пар изначально не более <tex>n</tex>. Откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.

== Сложность алгоритма ==
Алгоритм работает за <tex>O(n^2)</tex>. Действительно, количество итераций внешнего цикла <tex>\mathrm{for}</tex> всегда равно <tex>n</tex>. Поиск вершины, удовлетворяющей заданному условию тоже работает за <tex>O(n)</tex>, итого время работы <tex>O(n^2)</tex>.

== См.также ==
*[[Гамильтоновы графы]]
*[[Теорема Оре]]
*[[теорема Дирака|Теорема Дирака]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

2013-12-06T18:07:22Z

188.162.64.100: /* Доказательство алгоритма */

__TOC__
== Описание алгоритма ==
Пусть у нас есть граф <tex>\mathbb{G} = \left \langle \mathbb{V, E} \right \rangle</tex>, удовлетворяющий условию [[Теорема Дирака|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь <tex>n = \left | \mathbb{V}\right |</tex> раз будем делать следующую операцию:

* Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе <tex>\mathbb{G}</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
* Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j < i - j</tex> (то есть <tex>j</tex> пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>-й позиции), а так же, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

Таким образом после <tex>n</tex> итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а так же существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

== Псевдокод ==
{| width = 100%
|-
|
Queue queue; // создаем очередь
for i = 0 to n - 1 //
queue.pushback(v[i]) // добавляем в очередь все вершины графа
for k = 0 to n - 1 // пока не проделано нужное количество итераций
if !exist(queue.at(0), queue.at(1)) // проверяем существования ребра между первой и второй вершинами очереди
queue.swapSubQueue(2, find_vertex()) // если, не существует, то меняем порядок вершин в очереди, со второй до
// найденной, удовлетворяющей нас позиции

|width = "310px" |
|}

== Доказательство алгоритма ==
Для доказательства корректности алгоритма достаточно показать:

* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.
* После <tex>n</tex> итераций между каждой парой соседних вершин очереди существует ребро.

Докажем первое. Рассмотрим множество <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}</tex>, состоящее из вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}</tex>, вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4,...,n\}</tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует.

Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_2</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), а такие пар изначально не более <tex>n</tex>. Откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.

== Сложность алгоритма ==
Алгоритм работает за <tex>O(n^2)</tex>. Действительно, количество итераций внешнего цикла <tex>\mathrm{for}</tex> всегда равно <tex>n</tex>. Поиск вершины, удовлетворяющей заданному условию тоже работает за <tex>O(n)</tex>, итого время работы <tex>O(n^2)</tex>.

== См.также ==
*[[Гамильтоновы графы]]
*[[Теорема Оре]]
*[[теорема Дирака|Теорема Дирака]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]