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

Кафедра КМММ 
 

    ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

    К КУРСОВОЙ РАБОТЕ

    по  дисциплине «Дискретная математика» 

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

Выполнил   Тихомиров Д. К. 

ст. гр. ИФ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 алгоритма решения этой задачи.  

1. МАТЕМАТИЧЕСКИЕ МЕТОДЫ

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

Три задачи

1. Независимым множеством вершин графа называется любое множество попарно не смежных  вершин, т.е. множество вершин, порождающее  пустой подграф. Независимое множество  называется максимальным, если оно  не является собственным подмножеством  другого независимого множества, и  наибольшим, если оно содержит наибольшее количество вершин. Число вершин в  наибольшем независимом множестве  графа G обозначается через α(G) и называется числом независимости графа. Задача о независимом множестве состоит в нахождении наибольшего независимого множества.
2. Кликой графа называется множество вершин, порождающее полный подграф, т.е. множество вершин, каждые две из которых смежны. Число вершин в клике наибольшего размера называется кликовым числом графа и обозначается через ω(G). Очевидно, задача о независимом множестве преобразуется в задачу о клике и наоборот простым переходом от данного графа G к дополнительному графу , так что α(G) = ω().
3. Вершинное покрытие графа - это такое множество вершин, что каждое ребро графа инцидентно хотя бы одной из этих вершин. Наименьшее число вершин в вершинном покрытии графа 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: найдем наибольшее независимое множество графа , затем наибольшее независимое множество графа и выберем большее из этих двух множеств. В целом процесс решения задачи при этом можно рассматривать как исчерпывающий поиск в возникающем дереве подзадач. Чтобы не путать вершины дерева и вершины графа, вершины дерева будем называть узлами. Узел, не являющийся листом, называется внутренним узлом. Каждому внутреннему узлу дерева соответствует некоторый граф и некоторая вершина этого графа . Вершину можно выбирать произвольно, но она не должна быть изолированной вершиной графа . Внутренний узел имеет двух сыновей - левого и правого. Левому сыну соответствует подграф графа , получаемый удалением вершины , а правому - подграф, получаемый удалением всех вершин, смежных с . Корню дерева соответствует исходный граф. Листьям соответствуют подграфы, не имеющие ребер, то есть подграфы, у которых все вершины изолированные. Множества вершин этих подграфов - это независимые множества исходного графа.

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

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

      Эвристики для задачи о независимом множестве

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

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