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

Лекция 11.

 

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

 

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

 

Рассмотрим задачу коммивояжера, которую решим с помощью алгоритма Литтла.

 

Пример 10.1.  Задача коммивояжера: Коммивояжер должен посетить пять городов, заезжая в каждый город по одному разу. Расстояние между городами следующие: между первым городом и вторым – 12 км, между первым и третьим – 25 км, между первым и четвертым – 16 км, между первым и пятым – 31 км, между вторым и третьим – 28 км, между вторым и четвертым – 35 км, между вторым и пятым – 22 км, между третьим и четвертым – 36 км, между третьим и пятым – 20 км, между четвертым и пятым – 19 км. Его маршрут должен минимизировать суммарную длину пройденного пути.

Решение.  Сначала получим приведенный вид данной матрицы. Для этого пронумеруем строки и столбцы. В каждом столбце определим минимальный элемент и запишем его в нижней строке:

.

Из каждого элемента столбца вычитаем соответствующий минимальный элемент. Получаем матрицу :

.

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

.

Вычисляем константу приведения :

.

Находим степени каждого нуля – сумму минимальных элементов строки и столбца, в которых стоит нуль (без учета самого нуля). К каждому нулю приписываем вверху его степень. Максимальной степенью является число 12. Нули с максимальной степенью определяют дуги, которые вероятнее всего войдут в гамильтонов цикл. В нашем случае наиболее вероятной дугой гамильтонова цикла является l(3; 5).

Выбираем дугу l(3; 5).

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

,              .

Обе матрицы не являются приведенными. Для приведения матриц определяем минимальные элементы строк и столбцов.

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

     Þ     .

Теперь определяем минимальные элементы каждого столбца. А потом эти элементы вычитаем из каждого элемента соответствующего столбца.

    Þ     .

Аналогично преобразовываем матрицу .

     Þ     .

Таким образом, получаем две приведенные матрицы:

     и     .

Вычисляем константы приведения:

,       ,

где и – суммы минимальных элементов строк и столбцов матриц и .

, но далее рассматриваем матрицу . Определяем степени нулей этой матрицы:

.

Максимальная степень – число 7. Наиболее вероятными дугами гамильтонова цикла являются дуги l(1; 2), l(4; 1) и l(5;4). Выбираем, например, дугу l(1; 2).

В связи с этим рассматриваем две матрицы: и . В матрице убираем первую строку и второй столбец, элемент заменяем , получаем матрицу . В матрице элемент заменяем . Имеем:

,             .

Обе матрицы не являются приведенными. Преобразуем их по той же схеме, как это делали выше.

     Þ    

     Þ     .

Таким образом, получаем две приведенные матрицы и .

Вычисляем константы приведения:

,       .

Так как , то далее рассматриваем матрицу . Определяем степени каждого нуля.

Максимальная степень – число 32. Наиболее вероятной дугой гамильтонова цикла является дуга l(5; 4).

В связи с этим рассматриваем две матрицы: и . В матрице убираем строку под номером 5 и столбец под номером 4, получаем матрицу . В матрице элемент заменяем . Имеем:

,       .

Матрица не является приведенной. Преобразуем ее по той же схеме как делали выше.

     Þ     .

,        .

Так как , то далее рассматриваем матрицу . Последние две дуги гамильтонова цикла определяем из матрицы : l(2; 3) и l(4; 1).

Таким образом, получаем решение, которое состоит из следующих дуг:  (3; 5), (1;2), (5; 4), (2; 3), (4; 1). Гамильтонов цикл имеет вид 1®2®3®5®4®1, длина цикла равна 95 км.

Сравним константу приведения с константами приведения альтернативных вариантов ( ):

: ;

: ;

: .

Так как , то возвращаемся к приведенной матрице , и от нее начинаем строить гамильтонов цикл.

Определяем степени нулей этой матрицы:

.

Максимальная степень – число 8. Наиболее вероятной дугой гамильтонова цикла является дуга l(5; 3).

В связи с этим рассматриваем две матрицы: и . В матрице убираем пятую строку и третий столбец, элемент уже заменен . В матрице элемент заменяем . Получаем:

,              .

Матрица - приведенная, а матрица не является приведенной. Сделаем ее приведенной, как это делали выше.

     Þ     .

Вычисляем константы приведения:

,       ,

где и – суммы минимальных элементов строк и столбцов матриц и .

Так как , но далее рассматриваем матрицу . Определяем степени нулей этой матрицы:

.

Максимальная степень – число 7. Наиболее вероятными дугами гамильтонова цикла являются дуги l(1; 4), и l(4; 5). Выбираем, например, дугу l(4; 5).

В связи с этим рассматриваем две матрицы: и . В матрице убираем строку под номером 4 и столбец под номером 5, получаем матрицу . В матрице элемент заменяем . Имеем:

,             .

Матрица - приведенная, а матрица не является приведенной. Сделаем ее приведенной, как это делали выше.

     Þ     .

Вычисляем константы приведения:

,   .

Так как , то далее рассматриваем матрицу . Определяем степени каждого нуля.

.

Максимальная степень – число 19. Наиболее вероятной дугой гамильтонова цикла является дуга l(2; 1).

В связи с этим рассматриваем две матрицы: и . В матрице убираем строку под номером 2 и столбец под номером 1, элемент заменяем и получаем матрицу . В матрице элемент заменяем . Имеем:

,       .

Обе матрицы не являются приведенными. Преобразуем их по той же схеме, как это делали выше.

     Þ     ,

     Þ     .

,        .

Так как , то далее рассматриваем матрицу . Последние две дуги гамильтонова цикла определяем из матрицы : l(1; 4) и l(3; 2).

Таким образом, получаем решение, которое состоит из следующих дуг:  (5; 3), (4;5), (2; 1), (1; 4), (3; 2). Гамильтонов цикл имеет вид 1®4®5®3®2®1, длина цикла тоже равна 95 км.

Сравним константу приведения с константами приведения альтернативных вариантов ( ):

: ;

: ;

: .

Это значит, что получили оптимальное решение.

Весь процесс отыскания оптимального плана можно изобразить в виде дерева ветвления:

 

Полученные гамильтоновы циклы 1®2®3®5®4®1 или 1®4®5®3®2®1 можно изобразить в виде орграфа.

 

 

Это означает следующее: коммивояжер сначала посещает город 1, потом – город 2, затем – город 3, после – город 5, и, наконец, город 4, а потом возвращается в город 1. При этом длина всего пути составит 95 км. Второе решение говорит о том, что коммивояжер может ехать в обратную сторону.

,

С помощью метода ветвей и границ с использование современных ЭВМ можно решать задачи коммивояжера для . В связи с малой эффективностью точных методов получили широкое применение эвристические. В настоящее время существует более ста приближенных методов решения задачи коммивояжера, среди которых наиболее прост метод ближайшего соседа. Он реализует требование включать в искомый замкнутый цикл вершину, ближайшую к только что найденной. Алгоритм «ближайшего соседа» состоит в последовательном добавлении к начальной вершине следующей ближайшей к ней и т.д. Метод очень прост, однако степень приближения к оптимальному решению существенно зависит от выбора начальной вершины. Поэтому алгоритм целесообразно применять, начиная с каждой вершины, и затем выбрать замкнутый цикл наименьшей длины. Отметим, что если ближайший сосед для некоторой вершины уже вошел в цикл, то берется следующая по близости вершина и т.д. Например, используя данный метод для полного взвешенного графа с n вершинами, потребуется рассмотреть n! гамильтоновых циклов, из которых выбирается цикл наименьшей длины.

 

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

 

 

п.11.  Планарные графы.

 

11.1.  Планарные графы.

 

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

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

Но надо подчеркнуть, что нас интересует возможность построения графа с непересекающимися ребрами.

 

Определение 11.1. Планарным графом называется граф, который может быть изображен на плоскости, так что его ребра не пересекаются.

Все планарные графы укладываются на плоскости (имеют плоскую укладку).

Пример 11.1.  На рисунках изображен граф и его плоская укладка.

 

,

Очевидно, что

1)  Всякий подграф  планарного графа планарен.

2)  Граф планарен тогда  и только тогда, когда каждая  связная компонента этого графа  – планарный граф.

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

 

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

Пример 11.2.

Теорема 11.1.  (теорема Эйлера)  Если G – связный планарный граф, содержащий v вершин, e ребер и f граней, то

                                                          (11.1.1)

 

 

Доказательство.

Пусть G – связный планарный граф, который имеет v вершин. Рассмотрим некоторый остов этого графа. Остов имеет всего одну внешнюю грань, v вершин и ребер, т.е. , и . Значит, . Формула (11.1.1) для остова выполняется.

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

Таким образом, формула (11.1.1) будет верна для всякого графа, получающегося в результате таких операций, а поскольку графом G заканчивается вся эта процедура, то эта формула будет верна и для него.

■

Пример 11.3.  Планарный граф имеет вершины со степенями 2, 2, 2, 3, 3, 3, 4, 4, 4 и 5, соответственно. Сколько у него ребер и граней?

Решение.  Всего вершин 10, т.е. . Найдем сумму степеней вершин графа . Значит, число ребер равно (по теореме Эйлера о сумме степеней вершин графа). Тогда число граней .