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

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

      В данной программе реализованы алгоритмы  Брона-Кэрбоша (перебор с возвратом), алгоритм Ткача, алгоритм поиска η-областей (эволюционный).

 

2. ПОСТАНОВКА  ЗАДАЧИ

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

      Пользователь  может строить граф самостоятельно или же загружать его из файла и достраивать по усмотрению, выбирать алгоритм поиска МНМ из предложенных программой, сохранять изображение графа и/или сам граф.

      Для решения этой задачи необходимо реализовать  графическую составляющую для постройки  графа и необходимые алгоритмы  поиска МНМ.

 

3.РАЗРАБОТКА АЛГОРИТМОВ

3.1 Алгоритм  Брона-Кэрбоша

    Метод Брона-Кэрбоша построения всех МНМ использует дерево поиска. В процессе поиска на k-м этапе используется три множества:

• - независимые множества вершин (НМ) на k-м этапе;
• - подмножество вершин, которые еще не использовались для расширения НМ;
• - множество вершин, которые уже использовались для поиска решения НМ.

   Таким образом, легко показать, что  является МНМ, если  Ø.

Описание  работы алгоритма Брона-Кэрбоша

Начальная установка

    Шаг 1.

Прямой  шаг

    Шаг 2. Выбираем таким образом, чтобы было НМ ( выбирается из ). Формируем , , .

Проверка

    Шаг 3. Если , то, если идти к шагу 5, а если , то остановиться, иначе к шагу 4.

    Шаг 4. Если = = , то вывести МНМ и перейти к шагу 5, или, если = , а , идти к шагу 5. Иначе идти к шагу 2.

Шаг возвращения

      Шаг 5. Положим k=k-1 и исправим множества:

, , - не трогаем.

      Шаг 6. Если k=0 и , то все МНМ уже выведены и остановка, иначе идти к шагу 3. 
 

3.2 Алгоритм Ткача

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

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

 

3.3 Алгоритм  поиска η-областей

      Необходимо  построить для графа G_d матрицу смежности R. Переставим все столбцы и строки помеченные элементами некоторого внутренне–устойчивого подмножества P таким образом, чтобы они располагались рядом друг с другом начиная с левой (верхней) стороны матрицы. Анализ состояния матрицы смежности показывает что если столбцы матрицы с номерами от l до l+m помечены элементами, образующими независимое множество вершин, то симметрично относительно главной диагонали матрицы R на пересечении столбцов и строк матрицы с номерами от l до  (l+m -1) формируется область P_i квадратной формы размером m*m, элементы которой имеют нулевое значение. Назовем такую область -областью.

      Формирование  η-областей в матрице R осуществляется в процессе её эволюционной модификации. Эволюционная модификация матрицы R производится путём выборочных групповых перестановок соседних столбцов и строк, что обеспечивает направленное последовательное перемещение элементов матрицы R с нулевым значениями и объединение их в η-области.

Адаптивный  процесс состоит из повторяющихся  шагов, каждый из которых представляет собой переход от одного решения (состояния матрицы R) к другому – лучшему.

      На  каждом шаге анализируются пары (i, i+1) соседних строк матрицы. Анализ осуществляется в два такта. На первом такте анализируются все пары (i, i+1), у которых первый элемент i-нечетное число. На втором такте анализируются пары, у которых первый элемент i-четное число.

Например: пусть n=9, тогда на первом такте рассматриваются пары строк {(1,2),(3,4),(5,6),(7,8)}. На втором такте - {(2,3),(4,5),(6,7),(8,9)}.

      Пары  строк анализируются независимо друг от друга. По результатам анализа принимается решение о перестановке соседней пары строк.

      Локальная цель перестановок - перемещение нулевых  элементов матрицы снизу-вверх  и справа-налево. Глобальная цель - формирование η-области P_i(l,m) с максимальным значением параметра m, то есть выделение максимального внутренне-устойчивого множества.

      Пусть для анализа выбрана пара строк (i, i+1) матрицы R=||r_ij|| размером n*n .В строках выделяют две части: 1 - (j=1÷i-1); 2 - j=i+2÷n). Суть анализа заключается в определении истинностного значения трёх нижеприведенных условий.

1. > - 1-я часть.

2. = - 1-я часть, и > - 2-я часть.

3. = - 1-я часть, и = - 2-я часть.

      Ответ «да», то есть – переставлять, вырабатывается, если выполняются условия 1 и 2 . В случае выполнения условия 3 ответ «да» вырабатывается с вероятностью P, задаваемой априорно. В остальных случаях вырабатывается ответ «нет».

      Адаптивная  поисковая процедура продолжается, пока существуют пары, для которых  выполняются условия 1 и 2. в результате будет сформирована η-область P₁(1,m) и в графе G_d определено максимальное внутренне-устойчивое подмножество X¹_d.

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

      Если  же решается задача раскраски, то в  графе G_d удаляется подмножество вершин X¹_d, а из матрицы R удаляются m столбцов и строк, покрывающих область P₁(1,m). Образуя граф G¹_d  и матрица R. Далее над полученной матрицей R¹ производится аналогичные действия, то есть в G¹_d выделяется максимальное внутренне-устойчивое подмножество X²_{d .}Выше перечисленные действия продолжаются, пока матрица смежности не станет пустой, т.е. все вершины будут окрашены.

 

4. ОПИСАНИЕ  ПРОГРАММЫ

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

4.1 Общие  сведения

      Данный  программный продукт создавался в среде C++ Builder 6 Enterprise.

      Системные требования: минимальные, необходимо наличие монитора и клавиатуры.

      Вызов программы осуществляется запуском exe-файла в корневом каталоге программы. Исходный текст программы хранится в файлах Project1.cpp, Unit1.cpp, Unit1.h. Файл проекта Project1.bpr.

4.2 Возможности  программы

• Создание  графа. Пользователь может строить граф собственноручно, или загружать его из txt-файла, с возможностью дальнейшей обработки.
• Редактирование графа. Пользователь имеет возможность добавлять вершины и ребра, перемещать вершины, удалять вершины (в этом случае все инцидентные ей ребра также будут удалены).
• Поиск МНМ. Пользователь может осуществлять поиск МНМ с помощью 3-х алгоритмов на его усмотрение.
• Сохранение графа. Пользователь может сохранить как структуру графа в txt-файл, с возможностью загрузить ее в дальнейшем, так и изображение графа.

4.3 Отладка программы

     Отладка программы осуществлялась в следующих случаях:

• Проверка работоспособности каждого из алгоритмов
• Отладка передвигания вершины по полю
• Проверка правильности отрисовка графа после загрузки из файла
• Проверка правильности сохранения структуры графа в файл

4.4 Справка

1. Левый клик по свободному месту – добавление вершины
2. Левый клик по вершине – её выделение
3. Левый клик по свободному месту, когда одна вершина выделена – добавление в указанном месте новой вершины и соединение ее ребром в выделенной
4. Левый клик по другой вершине, когда одна вершина выделена – соединение этих вершин ребром
5. Нажатие ESC, когда одна вершины выделена – снятие выделения
6. Нажатие DEL, когда одна вершина выделена – удаление выделенной вершины
7. Левый клик по выделенной вершине и удерживание – перемещение выделенной вершины
8. Нажатие клавиши «Очистить» – удаление всех объектов, очищение поля
9. После построения графа необходимо нашать кнопку «Завершить построение». Для редактирования нажать кнопку «Редактирование».

10)Чтоб  осуществить поиск МНМ на графе,  необходимо нажать кнопку, запускающую один из алгоритмов. 

 

ВЫВОДЫ

      В данном курсовом проекте была реализована  программа нахождения максимального независимого множества на графах с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска η-областей. В ходе работы были изучены различные алгоритмы нахождения МНМ, способы реализации построения графа в среде C++ Builder 6 Enterprise. При оформлении курсовой работы был получены навыки оформления программной документации.

 

СПИСОК  ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Архангельский. А. Я. «С++ Builder 6.0 Программирование». М., Изд-во «БИНОМ», 2003г.

Кристофидес Н. «Теория графов. Алгоритмический подход». Изд-во «Мир», 1978г.

Харари  Ф. «Теория графов». Изд-во: «Либроком», 2009г.