Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Примеры решения задач. Пример 1. Пусть задан граф g = (х, u), изображенный на рис

Читайте также:
  1. B. Принятия оптимального управленческого решения по наиболее важным вопросам деятельности на рынке.
  2. I. 1.1. Пример разработки модели задачи технического контроля.
  3. I. 3.1. Двойственная задача линейного программирования.
  4. I.2. Структура оптимизационных задач
  5. I.5.3. Подготовка данных для задачи линейного программирования.
  6. I.5.4. Решение задачи линейного программирования.
  7. I.5.5. Просмотр и анализ результатов решения задачи.

Пример 1. Пусть задан граф G = (Х, U), изображенный на рис. 16.20. Построить ГЦ для заданного графа, используя алгоритм Робертса ─ Флореса.

Рис. 16.20. Исходный граф

Решение: Построим матрицу М для заданного графа. Она будет иметь следующий вид:

.

Теперь воспользуемся описанным ранее алгоритмом.

1.1. Выбираем из матрицы М вершину a и заносим ее в список: L = { а }.

2.1. По матрице смежности выбираем из столбца с индексом a вершину, расположенную в первой ячейке. Это вершина b: L = { a, b }.

2.2. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 3.1.

3.1. Выбираем столбец b, рассматриваем вершину из первой ячейки ─ это вершина a. Такая вершина уже есть в списке L, поэтому из второй ячейки столбца b берем вершину c. Переходим к следующему шагу.

3.2. Вершины с в списке L нет. Заносим ее в список: L = { a, b, c }.

3.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 4.1.

4.1. В столбце c рассматриваем вершину из первой ячейки ─ это вершина b. Такая вершина уже есть в списке L, поэтому из второй ячейки столбца c берем вершину d. Переходим к следующему шагу.

4.2. Вершины d в списке L нет. Заносим ее в список: L = { a, b, c, d }.

4.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 5.1.

5.1. В столбце d все вершины уже рассмотрены. Поэтому возвращаемся на шаг назад и пытаемся построить другой вариант построения пути. Вершина d вычеркивается из списка L = { a, b, c }. Переходим к п. 6.1.

6.1. В столбце c из третьей ячейки столбца берем вершину e. Переходим к следующему шагу.

6.2. Вершины e в списке L нет. Заносим ее в список: L = { a, b, c, e }.

6.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к пункту 7.1.

7.1. В столбце e все вершины уже рассмотрены. Поэтому возвращаемся на шаг назад и пытаемся построить другой вариант построения пути. Вершина e вычеркивается из списка L = { a, b, c }. Переходим к пункту 8.

8.1. В столбце c все вершины уже рассмотрены. Поэтому возвращаемся на шаг назад и пытаемся построить другой вариант построения пути. Вершина c вычеркивается из списка L = { a, b }. Переходим к п. 9.1.

9.1. В столбце b из третьей ячейки столбца берем вершину d. Переходим к следующему шагу.

9.2. Вершины d в списке L нет. Заносим ее в список: L = { a, b, d }.

9.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 10.1.

10.1. В столбце d из третьей ячейки столбца берем вершину c. Переходим к следующему шагу.

10.2. Вершины c в списке L нет. Заносим ее в список: L = { a, b, d, c }.

10.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 11.1.

11.1. В столбце c из третьей ячейки столбца берем вершину e. Переходим к следующему шагу.

11.2. Вершины e в списке L нет. Заносим ее в список: L = { a, b, d, c, e }.

11.3. Проверяем условие |L| = n. Условие выполняется. Следовательно, в графе G построена гамильтонова цепь и нам необходимо проверить, есть ли в исходном графе замыкающее ребро, чтобы завершить гамильтонов цикл.

11.4. В столбце e имеется вершина a, следовательно, поставленная задача выполнена, в графе G построен гамильтонов цикл:

{ abdcea }.

11.5. Конец работы алгоритма.

Пример 2. Пусть задан граф G = (X, U), изображенный на рис. 16.21. Построить ГЦ для данного графа алгебраическим методом.

Рис. 16.21. Исходный граф

Решение:

1. Запишем матрицу смежности B и матрицу перемножений P1 для заданного графа. Матрица P1 на первом этапе совпадает с матрицей.

 

B = .

 

2. После перемножения матриц B и P1, получим матрицу:

    a b c d e  
P2= a b+c+e e e b+e b+c .
b e a+d+e a+e e a+d
c e a+e a+e e a
d b+e e e b+e b
e b+c a+d a b a+b+c+d

 

После исключения из матрицы P’2 элементов, находящихся на главной диагонали, получим матрицу:

    a b c d e  
P2’= a   e e b+e b+c .
b e   a+e e a+d
c e a+e   e a
d b+e e e   b
e b+c a+d a b  

 

3. После перемножения матриц B и P2, получим матрицу:

    a b c d e  
P3’= a be+ce+eb+ec ca+ce+ea+ed ba+be+ea be+ce+eb ba+bd+ca .
b de+db+eb+ec ae+de+ea+ed ae+de+ea ab+ae+eb ab+ac+db
c eb+ec ae+ea+ed ae+ea ab+ae ab+ac
d be+eb+ec ea+ed ba+be+ea be+eb ba+bd
e be+ce+db+de ae+ca+ce+de ae+ba+be+de ab+ae+be+ce ab+ac+ba+bd+ca+db

 

В полученной матрице сначала обнуляем ячейки главной диагонали, а затем из всех ячеек матрицы исключаем элементы, в которые в качестве сомножителя входят концевые вершины цикла. Например, в строке a исключаем все элементы, включающие в качестве сомножителя вершину a. Для наглядности такие элементы выделены в матрице жирным шрифтом. После исключения из матрицы P’2 всех вышеуказанных элементов получим матрицу:

    a b c d e  
P3= a   ce+ed be be+ce+eb bd  
b de+ec   ae+de+ea ae ac  
c eb ae+ea+ed   ab+ae ab .
d be+eb+ec ea ba+be+ea   ba  
e db ca ba ab    

4. После перемножения матриц B и P3, получим матрицу:

    a b c d e  
P’4 = a bde+bec+ceb+edb cae+cea+ced+eca bde+bae+bea+eba bae+cab+cae+ceb+eab bac+cab .
b dbe+deb+dec+edb ace+aed+dea+eca abe+dba+dbe+dea+eba abe+ace+aeb+eab abd+dba
c edb ace+eca+aed abe+eba abe+ace+aeb+eab abd
d bde+edb+bec eca bae+bde+bea+eba bae+eab bac
e bde+bec+ceb+dbe+deb+ dec ace+aed+cae+cea+ced abe+bae+bde+bea+dba+ dbe+dea abe+ace+aeb+bae+cab+ cae+ceb abd+bac+cab+dba

 

После аналогичного преобразования матрицы P’4 можем записать матрицу:

    a b c d e  
  a   ced bde ceb   .
  b dec   dea ace  
P4 = c edb aed   abe+aeb+eab abd
  d bec eca bae+ bea+ eba   bac
  e     dba cab  

Все ненулевые ячейки матрицы P4 представляют собой гамильтоновы цепи. Концами этих цепей являются вершины, на пересечении которых располагается рассматриваемая ячейка. Например, ячейка на пересечении строки a и столбца d представляет собой гамильтонову цепь acebd. Те из построенных цепей, для которых существует замыкающее ребро, образовывают гамильтонов цикл. Анализ полученной матрицы P4 позволяет сделать вывод о наличии в исходном графе G следующего ГЦ:

acedb.

Все остальные цепи либо не имеют замыкающего ребра, либо являются вариантами обнаруженного цикла. Например, cedba или dbace.

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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. В чем состоит идея алгоритма Робертса–Флореса?

2. Опишите последовательность построения гамильтонова цикла в графе с помощью алгоритма Робертса–Флореса.

3. Какова сложность алгоритма Робертса─Флореса?

4. В чем состоит идея алгебраического метода?

5. Опишите последовательность построения гамильтонова цикла в графе с помощью алгебраического метода.

6. Какова сложность алгебраического метода при построении одного гамильтонова цикла?

7. Какова сложность алгебраического метода при построении всех гамильтоновых циклов в графе?

8. В чем заключается отличие стратегии работы алгоритмов Робертса–Флореса и алгебраического?

9. Для решения каких задач следует применять алгоритм Робертса–Флореса?

10. В каких случаях применение алгебраического метода является эффективным?


Дата добавления: 2015-10-26; просмотров: 167 | Нарушение авторских прав


Читайте в этой же книге: КРИТЕРИИ ОЦЕНКИ | Способы задания графов | Примеры РЕШЕНИЯ ЗАДАЧ | Маршруты, цепи, циклы | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Алгоритм Форда | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Эйлеровы и гамильтоновы цепи и циклы | Связь между эйлеровыми и гамильтоновыми графами | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ |
<== предыдущая страница | следующая страница ==>
Алгоритм Робертса ─ Флореса| Геометрический метод решения

mybiblioteka.su - 2015-2024 год. (0.009 сек.)