Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре — различия между версиями
Ak57 (обсуждение | вклад) (→Описание алгоритма) |
Ak57 (обсуждение | вклад) м (→Доказательство алгоритма) |
||
Строка 26: | Строка 26: | ||
Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары <tex>\mathrm{v}_i \mathrm{v}_{i+1}</tex>. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина <tex> \mathrm{v}_j \in \mathbb{V} \setminus \{\mathrm{v}_1, \mathrm{v}_{2}\}</tex>, такая что <tex>\mathrm{v}_1 \mathrm{v}_j,\ \mathrm{v}_2 \mathrm{v}_{j+1} \in \mathbb{E} </tex>. | Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары <tex>\mathrm{v}_i \mathrm{v}_{i+1}</tex>. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина <tex> \mathrm{v}_j \in \mathbb{V} \setminus \{\mathrm{v}_1, \mathrm{v}_{2}\}</tex>, такая что <tex>\mathrm{v}_1 \mathrm{v}_j,\ \mathrm{v}_2 \mathrm{v}_{j+1} \in \mathbb{E} </tex>. | ||
− | Пусть <tex>S= | + | Пусть <tex>S= \{ i| \mathrm{e}_i = \mathrm{v}_1 \mathrm{v}_i \in \mathbb{E}\} |
− | + | \subset \{3, 4, ...,n\}</tex> и <tex>T = \{ i| f_i=\mathrm{v}_2 \mathrm{v}_{i+1} \in \mathbb{E} \} | |
− | + | \subset \{2, 3, ...,n-1\}</tex>. | |
− | Тогда <tex>S \cup T \subset \{2,3,...,n\}</tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = deg\ v_1 + deg\ v_2 | + | Тогда <tex>S \cup T \subset \{2,3,...,n\}</tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = \operatorname{deg}\ v_1 + \operatorname{deg}\ v_2 \ge n</tex> по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], в зависимости от наших начальных условий. А значит <tex>S \cap T \ne \varnothing</tex>, следовательно искомая вершина обязательно найдется. |
Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> и <tex>\mathrm{v}_j, \mathrm{v}_{j+1}</tex> становились связанными ребром, то, рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> будут связаны ребром, а это и значит что мы нашли цикл. | Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> и <tex>\mathrm{v}_j, \mathrm{v}_{j+1}</tex> становились связанными ребром, то, рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> будут связаны ребром, а это и значит что мы нашли цикл. |
Версия 18:57, 6 ноября 2013
Описание алгоритма
Алгоритм находит гамильтонов цикл в неориентированном графе , если выполняются условия теоремы Оре или выполнена теорема Дирака. Рассмотрим перестановку вершин , где . Если между каждой парой соседних вершин в перестановке существует ребро, то мы получили Гамильтонов цикл. В противном случае, начиная с пары , начнем последовательно рассматривать пары соседних вершин , пока .
- Если между ними есть ребро, то переходим к следующей паре вершин .
- Если же ребра нет, то найдем такую вершину
- Если то перевернем часть перестановки от до (включительно).
- Если обменяем в перестановке элементы на позициях и , где . Например, если , то и поменяются местами, а останется на месте.
(то, что она всегда существует, будет показано ниже), что , и существуют ребра и (Если , то за считаем ).
Псевдокод
for//перебираем все вершины перестановки if //если нет ребра между for //перебираем все остальные вершины if && //если есть ребра reverse_subsequence( ) //разворачиваем часть перестановки от i+1 позиции до j break //переходим к следующей итерации внешнего for |
Доказательство алгоритма
Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары
. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина , такая что .Пусть теоремы Оре или теоремы Дирака, в зависимости от наших начальных условий. А значит , следовательно искомая вершина обязательно найдется. Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота и становились связанными ребром, то, рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин будут связаны ребром, а это и значит что мы нашли цикл.
и . Тогда , откуда . Но по условию