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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 04.05.2012. Сдан: 2011. Страниц: 21. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Министерство  образования и науки Украины 
Национальный технический университет  
«Харьковский политехнический институт»
 
 

Кафедра КМММ 
 

    ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
    К КУРСОВОЙ РАБОТЕ
    по  дисциплине «Дискретная математика» 

    Поиск максимального независимого множества  графа с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска ?-областей 
 

Выполнил   Тихомиров Д. К. 
ст. гр. ИФ5_а 
 
 

    Руководитель,
    доц. каф. КМММ Тоница О. В. 
 
 
 
 
 

                  2010

РЕФЕРАТ

     Пояснительная записка: 23 стр., 5 рис., 2 приложения, 3 источника.
     В данном документе описывается программа, написанная в соответствии с постановкой  задачи на курсовое проектирование по теме «Поиск максимального независимого множества графа с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска ?-областей» по дисциплине «Дискретная математика». Данная программа осуществляет поиск максимального независимого множества построенного или загруженного графа с помощью вышеуказанных алгоритмов.
      Результатом стала программа поиска максимального независимого множества графа. Алгоритмы работы программы описаны в разделе «Математическая база».
      В записке описаны постановка задачи, реализованные алгоритмы, инструкция к пользованию и прочая информация о программе. В приложениях содержатся скриншоты из игры и основные части кода программы.
      ГРАФ  МАКСИМАЛЬНО НЕЗАВИСИМОЕ МНОЖЕСТВО  ПОИСК АЛГОРИТМ БРОНА-КЭРБОША ТКАЧА ? ЭТА ОБЛАСТИ 

СОДЕРЖАНИЕ

Введение                   4
1.Математические методы                                                                                 6
2.Постановка  задачи               11
3.Разработка  алгоритмов              12
      3.1. Алгоритм Брона-Кэрбоша            12
      3.2. Алгоритм Ткача              13
      3.3. Алгоритм поиска ?-областей            14
4.Описание программы               17
Выводы                 19
Список использованных источников            20
Приложение А: Экранные формы             21
Приложение Б: код               22 

 

 

ВВЕДЕНИЕ

   Во  многих прикладных задачах требуется  найти в конечном множестве объектов максимальную систему объектов, попарно  не связанных друг с другом, или  же выбрать минимальную систему  объектов, связанных со всеми другими. Формулировки подобных задач на языке  теории графов приводят к понятиям независимости и покрытия.
   Одна  из чисто житейских интерпретаций  понятия независимости состоит  в следующем. Определенный человек  желает устроить юбилей с максимальным числом гостей из своих знакомых. Стремясь сделать юбилейный вечер приятным, он должен организовать все так, чтобы  на этом вечере присутствовали люди, симпатизирующие  друг другу. Так как отношение "симпатии" не является транзитивным, то ему для достижения цели придется находить число независимости графа своих знакомых.
   Этот  граф устроен следующим образом. Вершины его - знакомые юбиляра. Две  вершины смежны, если соответствующие  знакомые друг другу не симпатизируют. Нетрудно понять, что число независимости  этого графа и представляет тот  самый максимальный контингент приглашенных, который может себе позволить юбиляр.
   Таким образом, задача поиска наибольшего  независимого множества заключается  в нахождении наибольшего количества несмежных между собой вершин графа. Данная программа предлагает 3 алгоритма решения этой задачи.  

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

Три задачи

    Независимым множеством вершин графа называется любое множество попарно не смежных  вершин, т.е. множество вершин, порождающее  пустой подграф. Независимое множество  называется максимальным, если оно  не является собственным подмножеством  другого независимого множества, и  наибольшим, если оно содержит наибольшее количество вершин. Число вершин в  наибольшем независимом множестве  графа G обозначается через ?(G) и называется числом независимости графа. Задача о независимом множестве состоит в нахождении наибольшего независимого множества.
    Кликой графа называется множество вершин, порождающее полный подграф, т.е. множество вершин, каждые две из которых смежны. Число вершин в клике наибольшего размера называется кликовым числом графа и обозначается через ?(G). Очевидно, задача о независимом множестве преобразуется в задачу о клике и наоборот простым переходом от данного графа G к дополнительному графу , так что ?(G) = ?().
    Вершинное покрытие графа - это такое множество вершин, что каждое ребро графа инцидентно хотя бы одной из этих вершин. Наименьшее число вершин в вершинном покрытии графа G обозначается через ?(G) и называется числом вершинного покрытия графа. В графе на рис. 1.1 наибольшим независимым множеством является множество {1,3,4,7}, наибольшей кликой - множество {2,3,5,6}, наименьшим вершинным покрытием - множество {2,5,6}.

Рисунок 1.1
      Между задачами о независимом множестве  и о вершинном покрытии тоже имеется  простая связь благодаря следующему факту.
Теорема 1. Подмножество U множества вершин графа G является вершинным покрытием тогда и только тогда, когда = VG - U - независимое множество.
Доказательство. Если U - вершинное покрытие, то всякое ребро содержит хотя бы одну вершину из множества U и, значит, нет ни одного ребра, соединяющего две вершины из множества . Следовательно, - независимое множество. Обратно, если - независимое множество, то нет ребер, соединяющих вершины из и, значит, у каждого ребра одна или обе вершины принадлежат множеству U. Следовательно, U - вершинное покрытие.
      Из  этой теоремы следует, что ?(G) + ?(G) = N для любого графа G с N вершинами.
      Таким образом, все три задачи тесно  связаны друг с другом, так что  достаточно научиться решать одну из них, и мы будем уметь решать остальные  две. Вместе с тем известно, что  эти задачи NP-полны. Для таких  задач не известно эффективных алгоритмов, а накопленный к настоящему времени  опыт делает правдоподобным предположение  о том, что таких алгоритмов и  не существует. Тем не менее, алгоритмы  для подобных задач разрабатывались  и продолжают разрабатываться, и  в некоторых случаях они могут  быть полезны. Все эти алгоритмы в той или иной форме осуществляют перебор вариантов (число которых может быть очень большим).
      Пусть G - граф, в котором требуется найти наибольшее независимое множество. Выберем в нем произвольную вершину . Обозначим через подграф, получающийся удалением из графа G вершины a, т.е. , а через   - подграф, получающийся удалением из G всех вершин, смежных с . На рисунке 1.2 показаны графы и , получающиеся из графа , изображенного на рис. 1.1, при .

Рисунок 1.2. 
      Пусть X - какое-нибудь независимое множество графа G. Если оно не содержит вершины , то оно является независимым множеством графа . Если же , то никакая вершина, смежная с , не принадлежит X. В этом случае множество X является независимым множеством графа . Заметим, что в графе на одну вершину меньше, чем в исходном графе G. Если вершина не является изолированной, то и в графе вершин меньше, чем в графе G. Таким образом, задача о независимом множестве для графа G свелась к решению той же задачи для двух графов меньшего размера. Это приводит к рекуррентному соотношению для числа независимости: и к рекурсивному алгоритму для нахождения наибольшего независимого множества графа  G: найдем наибольшее независимое множество графа , затем наибольшее независимое множество графа и выберем большее из этих двух множеств. В целом процесс решения задачи при этом можно рассматривать как исчерпывающий поиск в возникающем дереве подзадач. Чтобы не путать вершины дерева и вершины графа, вершины дерева будем называть узлами. Узел, не являющийся листом, называется внутренним узлом. Каждому внутреннему узлу дерева соответствует некоторый граф и некоторая вершина этого графа . Вершину можно выбирать произвольно, но она не должна быть изолированной вершиной графа . Внутренний узел имеет двух сыновей - левого и правого. Левому сыну соответствует подграф графа , получаемый удалением вершины , а правому - подграф, получаемый удалением всех вершин, смежных с . Корню дерева соответствует исходный граф. Листьям соответствуют подграфы, не имеющие ребер, то есть подграфы, у которых все вершины изолированные. Множества вершин этих подграфов - это независимые множества исходного графа.
      Для нахождения наибольшего независимого множества не обязательно строить  все дерево полностью, а достаточно обойти его в том или ином порядке, запоминая на каждом шаге только небольшую  часть информации об устройстве этого  дерева. Можно, например, применить  поиск в глубину для обхода дерева: сначала пройти от корня  до некоторого листа, затем вернуться  к предку этого листа и искать следующий лист, и т.д.
      Для одного и того же графа могут получиться разные деревья в зависимости  от того, как выбирается активная вершина  в каждом узле дерева. Может быть различным и число листьев в этих деревьях, а значит, и трудоемкость алгоритма, основанного на обходе дерева. Однако в любом случае листьев в дереве будет не меньше, чем максимальных независимых множеств у графа, так как каждое из этих множеств будет соответствовать некоторому листу. Так, для графа , т.е. графа, состоящего из компонент связности, каждая из которых изоморфна графу , в дереве подзадач будет листьев.  

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


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

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


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

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

    Метод Брона-Кэрбоша построения всех МНМ использует дерево поиска. В процессе поиска на k-м этапе используется три множества:
    - независимые множества вершин (НМ) на k-м этапе;
    - подмножество вершин, которые еще не использовались для расширения НМ;
    - множество вершин, которые уже использовались для поиска решения НМ.
   Таким образом, легко показать, что  является МНМ, если  O.
Описание  работы алгоритма Брона-Кэрбоша
Начальная установка
    Шаг 1.
Прямой  шаг
    Шаг 2. Выбираем таким образом, чтобы было НМ ( выбирается из ). Формируем , , .
Проверка
    Шаг 3. Если , то, если идти к шагу 5, а если , то остановиться, иначе к шагу 4.
    Шаг 4. Если = = , то вывести МНМ и перейти к шагу 5, или, если = , а , идти к шагу 5. Иначе идти к шагу 2.
Шаг возвращения
      Шаг 5. Положим k=k-1 и исправим множества:
, , - не трогаем.
      Шаг 6. Если k=0 и , то все МНМ уже выведены и остановка, иначе идти к шагу 3. 
 

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


3.3 Алгоритм  поиска ?-областей
      Необходимо  построить для графа Gd матрицу смежности R. Переставим все столбцы и строки помеченные элементами некоторого внутренне–устойчивого подмножества P таким образом, чтобы они располагались рядом друг с другом начиная с левой (верхней) стороны матрицы. Анализ состояния матрицы смежности показывает что если столбцы матрицы с номерами от l до l+m помечены элементами, образующими независимое множество вершин, то симметрично относительно главной диагонали матрицы R на пересечении столбцов и строк матрицы с номерами от l до  (l+m -1) формируется область Pi квадратной формы размером 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)}.
      Пары  строк анализируются независимо друг от друга. По результатам анализа принимается решение о перестановке соседней пары строк.
      Локальная цель перестановок - перемещение нулевых  элементов матрицы снизу-вверх  и справа-налево. Глобальная цель - формирование ?-области Pi(l,m) с максимальным значением параметра m, то есть выделение максимального внутренне-устойчивого множества.
      Пусть для анализа выбрана пара строк (i, i+1) матрицы R=||rij|| размером 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. в результате будет сформирована ?-область P1(1,m) и в графе Gd определено максимальное внутренне-устойчивое подмножество X1d.
        Если целью поиска было нахождение максимального паросочетания, то работа алгоритма на этом завершается.
      Если  же решается задача раскраски, то в  графе Gd удаляется подмножество вершин X1d, а из матрицы R удаляются m столбцов и строк, покрывающих область P1(1,m). Образуя граф G1d  и матрица R. Далее над полученной матрицей R1 производится аналогичные действия, то есть в G1d выделяется максимальное внутренне-устойчивое подмножество X2d .Выше перечисленные действия продолжаются, пока матрица смежности не станет пустой, т.е. все вершины будут окрашены.
 


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 Справка

    Левый клик по свободному месту – добавление вершины
    Левый клик по вершине – её выделение
    Левый клик по свободному месту, когда одна вершина выделена – добавление в указанном месте новой вершины и соединение ее ребром в выделенной
    Левый клик по другой вершине, когда одна вершина выделена – соединение этих вершин ребром
    Нажатие ESC, когда одна вершины выделена – снятие выделения
    Нажатие DEL, когда одна вершина выделена – удаление выделенной вершины
    Левый клик по выделенной вершине и удерживание – перемещение выделенной вершины
    Нажатие клавиши «Очистить» – удаление всех объектов, очищение поля
    После построения графа необходимо нашать кнопку «Завершить построение». Для редактирования нажать кнопку «Редактирование».
    10)Чтоб  осуществить поиск МНМ на графе,  необходимо нажать кнопку, запускающую один из алгоритмов. 

 


ВЫВОДЫ

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


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

    Архангельский. А. Я. «С++ Builder 6.0 Программирование». М., Изд-во «БИНОМ», 2003г.
    Кристофидес Н. «Теория графов. Алгоритмический подход». Изд-во «Мир», 1978г.
    Харари  Ф. «Теория графов». Изд-во: «Либроком», 2009г. 

Приложение  А: Экранные формы.


Рисунок А.1: пустое рабочее поле

Рисунок А.2: загрузка графа из файла

Рисунок А.3: построение графа

Рисунок А.4: поиск МНМ 
 

 


Приложение  Б: Код программы.

//---------------------------------------------------------------------------
#define IMG Form1->Image1->Canvas 

#include <vcl.h>
#include <math.h>
#include <cstdio>
#include <conio.h>
#include <iostream.h>
#pragma hdrstop 

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.