Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
Описание алгоритма
Алгоритм находит Гамильтонов цикл в неориентированном графе , если выполняются условия Теоремы Оре или выполнена Теорема Дирака. Рассмотрим перестановку вершин . Если между каждой парой соседних вершин в перестановке существует ребро, то мы получили Гамильтонов цикл. В противном случае начнем последовательно рассматривать пары соседних вершин , начиная с пары .
Если между ними есть ребро, то переходим к следующей паре вершин
.Если же ребра нет, то найдем такую вершину
, что , и существуют ребра и . После чего перевернем часть перестановки от до (считаем, что наша перестановка зациклиный список). Например, если , где , то и поменяются местами, а останется на месте.
Псевдокод
for(int i = 1; i < n; i++) //перебираем все пары соседних вершин в перестановке if () //если есть ребро continue; //переходим к следующей паре else //иначе while( ) //перебираем все вершины if ( ) //если есть ребра swap( ); //разворачиваем нужную часть перестановки continue; //переходим к следующей паре вершин |
Доказательство алгоритма
Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары
. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем что обязательно найдется вершина , такая что .Пусть теоремы Оре или теоремы Дирака, в зависимости от наших начальных условий. А значит , следовательно искомая вершина обязательно найдется. Поскольку каждый раз когда у нас нет ребра между двумя обрабатываемыми вершинами мы переворачиваем нашу последовательность так, чтобы после переворота и становились связанными ребром, то рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин будут связаны ребром, а это и значит что мы нашли цикл.
{ } и { } . Тогда , откуда . Но по условию