Лекции по "Развитию операционных систем"

Лекция 10.

 

п.10.  Эйлеровы и гамильтоновы циклы.

 

10.1.  Пути и циклы Эйлера.

 

Выше были введены понятия «путь» и «цикл» для связного графа. Особый интерес для математиков представляют так называемые два цикла, имеющие практическое применение - эйлеров цикл и гамильтонов цикл.

 

Определение 10.1.  Пусть G(V, E) – граф. Цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом. Граф, в котором существует эйлеров цикл называется эйлеровым.

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

 

Теорема 10.1.  Связный граф является эйлеровым тогда и только тогда, когда степень каждой его вершины четная.

Доказательство.  Необходимость.  Пусть G – связный эйлеров граф. Эйлеров цикл этого графа, проходя через каждую его вершину, входит в нее по одному ребру, а выходит по другому. Это означает, что каждое прохождение вершины по циклу вносит слагаемое 2 в ее степень. Поскольку цикл содержит все ребра графа, то степени всех вершин будут четными.

Достаточность.  Предположим, что степени всех вершин связного графа G четные. Начнем цепь G1 из произвольной вершины v1, и будем продлевать ее, выбирая каждый раз новое ребро. Так как степени вершин четная, то, попав в некоторую вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Таким образом, построение цепи P1 обязательно закончится в вершине v1, и P1 будет циклом. Если P1 содержит все ребра графа G, то построен эйлеров цикл.

В противном случае, удалив из графа G ребра графа P1, получим граф G2. Так как степень всех вершин графов G и P1 были четными, то и G2 будет обладать этим свойством. В силу связности G графы P1 и G2 должны иметь хотя бы одну общую вершину v2. Теперь начиная из v2, построим в G цикл P2 подобно тому, как построили P1.

 

 

Объединим циклы P1 и P2 следующим образом: пройдем часть P1 от вершины v1 до вершины v2, затем пройдем цикл P2, затем – оставшуюся часть P1 от v2 до v1.

Если объединенный цикл не эйлеров, проделав аналогичные построения, получим еще больший цикл. Поскольку степени вершин во всех графах, составленных из ребер, не попавших в строящийся цикл, четные, и число ребер в этих графах убывает, то процесс закончится построением эйлерова цикла.                                                                                 ■

 

Данная теорема служит критерием существования эйлерова цикла в графе. Это связано с тем, что эйлеровых графов с числом вершин n среди множества графов с тем же числом вершин почти нет.

Теперь можно показать, что на графе к задаче о кенигсбергских мостах нельзя построить эйлеров цикл, так как этот граф имеет вершины нечетной степени. Вообще эйлеров граф – это такой граф, который можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.

Для построения эйлерова цикла применяется так называемый алгоритм Флери.

Конечно, в задаче о кенигсбергских мостах можно было бы поставить такой вопрос: «Возможно, ли пройти каждый мост по одному разу, но не обязательно возвращаться в исходную точку?» Для этого рассматриваются такие понятия как эйлеров путь и собственный эйлеров путь.

 

Определение 10.2.  Пусть G(V, E) – граф. Путь, который включает каждое ребро графа G только один раз называется эйлеровым путем. Эйлеров путь, который не является циклом называется собственным эйлеровым путем.

Сформулируем теорему (без доказательства), в которой описано условие, при котором граф имеет собственный эйлеров путь.

 

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

 

По этой теореме получается, что задача о кенигсбергских мостах так же не имеет и эйлерова пути.

 

Аналогично можно ввести понятие эйлерова цикла для ориентированного графа и условие существования эйлерова цикла в орграфе.

Определение 10.3. Пусть G(V, E) - ориентированный граф. Ориентированный цикл, который включает все ребра и вершины графа G, называется эйлеровым циклом.

 

Теорема 10.3. Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и полустепень захода каждой вершины равна ее полустепени исхода.

 

Какое еще применение эйлерового цикла для решения практических задач? Рассмотрим следующий пример.

Пример 10.1.  Из какого минимального числа кусков проволоки можно спаять каркас куба? Толщина всех ребер каркаса должна быть одинаковой.

Решенеие.

Чтобы решить данную задачу, сначала сформулируем следующую теорему, которую примем без доказательства.

Теорема 10.4. Если связный граф содержит ровно 2n вершин нечетной степени, то минимальное число реберно-непересекающихся цепей, на которые можно разбить его ребра, равно n.

 

 

 

 

10.2.  Пути и циклы Гамильтона.

Алгоритм Литтла.

 

В 1857 году математик Уильям Роуэн Гамильтон придумал игру. Существует несколько версий того, как это произошло. По одной из версий он описал игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек. В любом случае она включала додекаэдр, т.е. правильный многогранник, 12 граней которых представляли собой равные правильные пятиугольники. В каждом из 20 углов, или вершин тела, просверливалась дырочка, в которую вставлялся колышек, изображавший город. Используя веревку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город.

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

 

Определение 10.4.  Пусть G(V, E) – граф. Гамильтонов путь – это простой путь, который проходит через каждую вершину графа G. Гамильтонов цикл – это простой цикл, который проходит через каждую вершину графа G.

 

Выше был приведен изящный критерий существования у графа эйлерова цикла. К сожалению, никому не удалось установить необходимые и достаточные условия существования у графа гамильтонова цикла. Тем не менее доказано ряд теорем, в которых приводятся некоторые условия существования у графа гамильтонова цикла. Но эти теоремы мы рассматривать не будем.

 

Мы рассмотрим одну из задач, в которой требуется отыскать гамильтонов цикл в взвешенном графе минимальной длины. Сначала введем формулировку задачи, а потом алгоритм решения этой задачи.

 

 

Задача коммивояжера (развозчика продукции или бродячего торговца).

 

Формулировка задачи:  коммивояжер должен посетить один и только один раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

 

Когда задача сформулирована, то с помощью математического языка (символов, функций, уравнений или неравенств и т.д.) строится математическая модель задачи. Понятие «математическая модель» введем в разделе «Основы математического моделирования». Пока будем оперировать данным понятием, как некоторым объективным фактом.

 

Пусть C=[cij] – матрица расстояний между городами. Для составления математической модели задачи обозначим через xij факт переезда коммивояжером из города i в город j. Поскольку переезд из одного города в другой может осуществляться только один раз, то xij должны принимать только два значения: 1 или 0, т.е. булевы значения. Таким образом:

 

 

Математическая модель задачи примет следующий вид:

                                                               (1)

                                                                (2)

                                                                (3)

Система ограничений (2) обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только один раз, а система (3) – маршрута, когда он выезжает из каждого города только один раз. К сожалению, эти ограничения недостаточны, так как среди допустимых ими решений имеются маршруты, не образующие полный цикл, включающий все города. Устранение подциклов достигается при добавлении системы ограничений:

,                          (4)

где переменные u могут принимать произвольные действительные значения.

 

Решение задачи коммивояжера методом ветвей и границ (алгоритм Литтла).

 

Если считать города вершинами графа, а коммуникации – его дугами, то нахождение минимального пути, проходящего один и только один раз через каждый город с возвращением в исходную точку можно рассматривать как нахождение на графе гамильтонова цикла минимальной длины.

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

,   .

Сравнивая нижние границы и подмножеств и , можно выделить среди них то, которое с большей вероятностью содержит гамильтонов цикл минимальной длины. Затем одно из подмножеств или по аналогичному правилу разбивается на два новых и . Для них снова отыскиваются нижние границы и и т.д.

 

Процесс ветвления продолжается до тех пор, пока не отыщется единственный гамильтонов цикл. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергают дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего гамильтонова цикла. Если же такой найдется, то анализ оборванных ветвей продолжается относительно нового значения длины цикла. Его называют вторым рекордом. Процесс решения заканчивается тогда, когда будут проанализированы все подмножества.

 

 

Алгоритм Литтла.

 

Пусть известна матрица весов некоторого орграфа, вершины которого занумеруем числами от 1 до :

,

где – вес дуги, соединяющей вершины и j, где .

Символ ставится для блокировки дуг графа, которые явно не включаются в гамильтонов цикл, т.е. в расчет не берутся дуги и . Можно показать, что оптимальность решения не меняется от прибавления некоторого числа к строке или столбцу матрицы W.

Алгоритм Литтла разбивается на несколько шагов.

Шаг 1. Приведение исходной матрицы.

В каждом столбце и в каждой строке матрицы W нужно получить хотя бы один нуль. Для этого, например, в первом столбце выбираем минимальный элемент и вычитаем его из всех элементов первого столбца. Аналогично поступаем с остальными столбцами. Если при этом в некоторых строках не появляются нули, то для них осуществляем ту же процедуру.

После этого вычисляем константу приведения – сумму минимальных элементов столбцов и строк, которые вычитались. Получаем приведенную матрицу с константой приведения .

Шаг 2. Определение степеней нулей.

Находим степени каждого нуля – сумму минимальных элементов строки и столбца , в которых стоит этот нуль, без учета самого нуля. Нуль с максимальной степенью определяет дугу , которая вероятнее всего войдет в гамильтонов цикл. Например, если нуль с максимальной степенью находится на пересечении второй строки и третьего столбца, то дуга , вероятнее всего, войдет в гамильтонов цикл.

Шаг 3. Ветвление.

На самом деле, дуга, соответствующая максимальной степени нуля, может, как входить в гамильтонов цикл, так и не входить в него. Поэтому дальше нужно рассмотреть сразу два случая.

Первый случай. Возможно, дуга вошла в гамильтонов цикл. Блокируем ее, полагая . Строку и столбец вычеркиваем. Если требуется, приводим полученную матрицу меньшего порядка с константой приведения .

Второй случай. Дуга не вошла в гамильтонов цикл. Полагаем . Если требуется, приводим полученную матрицу с константой приведения .

Если , то шаги 2, 3 повторяем с матрицей .

Если , то шаги 2, 3 повторяем с матрицей . И так до тех пор, пока не дойдем до матрицы второго порядка, содержащей два нуля:

,

где и – некоторые числа или . Эти нули соответствуют двум последним дугам гамильтонова цикла: , . При этом .

Если , где , то задача решена. Если же для некоторого получается , то всю процедуру следует провести с матрицей . На последнем этапе получим новое значение функции : . Это значение сравниваем с , то есть новый процесс продолжается до тех пор, пока новые .