Диссертация (1149246), страница 3
Текст из файла (страница 3)
Максимальное независимое множество (МНМ) наибольшей мощности называется наибольшим независимыммножеством (ННМ). Число вершин в ННМ графа G есть неплотность ε(G).Очевидно, φ(G) = ε(G) и ε(G) = φ(G).Под плотностью ребер будем понимать величину отношения реального количества ребер графа к максимально возможному при данном количестве вершин [33].Граф называется связным, если множество его вершин невозможно такразбить на попарно непересекающиеся непустые множества, чтобы никакиедве вершины из разных подмножеств не были смежны. Несвязный же граф Gоднозначно разбивается указанным образом на связные подграфы, называемыекомпонентами связности. Число компонент связности графа G будем обозначать κ(G).Графы G = (V, E) и G′ = (V ′ , E ′ ) называются изоморфными (G ≃ G′ ), еслимежду множествами V и V ′ их вершин можно установить взаимно однозначноесоответствие ↔, сохраняющее отношение смежности вершин, т.
е. такое, чтодля любых x, y ∈ V и соответствующих им вершин x′ , y ′ ∈ V ′ (x ↔ x′ , y ↔ y ′ )имеет место(x, y) ∈ E ⇔ (x′ , y ′ ) ∈ E ′ ,при этом само соответствие ↔ называется изоморфизмом графов.Пусть f : G → H – функция, относящая каждому графу G некоторыйэлемент f (G) из множества H произвольной природы (в действительности элементами H чаще всего служат числа, векторы, матрицы). Эту функцию будемназывать инвариантом, если на изоморфных графах ее значения совпадают:∀G, G′ : G ≃ G′ ⇒ f (G) = f (G′ ).Число компонент связности κ(G) графа G, его плотность φ(G) и неплотностьε(G) являются одними из наиболее важных инвариантов графа.14§2. Постановка задачи о поиске максимальныхнезависимых множествЗадачу о поиске максимальных независимых множеств можно рассматривать в двух вариантах.
Первый вариант – это поиск наибольшего независимогомножества, второй – перечисление всех максимальных независимых множествграфа.Задачу поиска наибольшего независимого множества можно сформулировать в следующем виде. Пусть задан неориентированный граф G = (V, E).Найти такое множество вершин Qmax ⊂ V , что|Qmax | = maxQ∈Ω |Q|,где Ω = {Q ⊂ V | ∀ u, v ∈ Q (u, v) ∈/ E}.Во втором варианте задача заключается в построении множестваM (G) = {Q ∈ Ω | @ Y ∈ Ω | Y ̸= Q & Q ⊂ Y }.На Рисунке 1 представлено наибольшее независимое множество неориентированного графа: Qmax = {2, 5, 8, 9, 11, 12, 18, 20}.Рис.
1: Наибольшее независимое множество неориентированного графа.15Отметим, что количество максимальных независимых множеств в рассматриваемом графе равно 295. Cреди них:– 10 МНМ Q, таких что |Q| = 6,– 280 МНМ Q, таких что |Q| = 7,– 5 МНМ Q, таких что |Q| = 8.Как видим, несмотря на сравнительно небольшой размер графа, общее количество всех МНМ очень велико.Задача поиска максимальных независимых множеств графа G эквивалентназадаче поиска клик в дополнительном графе G.
На Рисунке 2 изображен неориентированный граф G и дополнительный к нему граф G. Нетрудно видеть,что МНМ Q1 = {2, 4, 5} и Q2 = {1, 3} в графе G представляют собой клики вграфе G.Рис. 2: Слева – неориентированный граф G, справа – дополнительный к нему граф G.Рассматриваемая задача независимо от варианта постановки принадлежитк классу N P -полных задач.Впервые понятие N P -полноты было введено независимо друг от друга Куком [32] и Левиным [7] в начале 70-х годов XX-го века. До этого времени быловыделено только два сложностных класса: P – класс задач с полиномиальнойсложностью и N P – класс задач с полиномиально проверяемым решением.Задача называется полиномиальной, т.
е. относится к классу P , если существует константа k и алгоритм, решающий ее (в худшем случае) за время O(nk ),где n есть длина входа алгоритма [18].16Задача относится к классу N P , если алгоритм, проверяющий решение этойзадачи, относится к классу P [18].После того, как в теорию алгоритмов были введены понятия сложностныхклассов была сформулирована основная проблема теории сложности:«P = N P ?» и высказана гипотеза о несовпадении этих классов. Это предположение опирается как раз на существование класса N P -полных задач(N P -complete, N P C).Задача принадлежит к классу N P C, если выполнены два условия:1) она должна принадлежать классу N P ,2) к этой задаче должны полиномиально сводиться все задачи из классаN P [18].В настоящее время не существует точного полиномиального алгоритма решения задачи о поиске максимальных независимых множеств, как впрочем идля любой другой N P -полной задачи. Несмотря на это нет теоретическогодоказательства того, что существование такого алгоритма в принципе невозможно.
Конечно, для задачи построения всех максимальных независимых множеств возможность разработки подобного алгоритма мало вероятна (в силудоказательства [52] экспоненциальной зависимости числа МНМ от размерностиграфа), но для задачи поиска всего лишь одного наибольшего независимогомножества такого однозначного ответа дать нельзя.§3.
Алгоритмы поиска максимальных независимыхмножеств в неориентированном графеОбзор алгоритмов, представленных в этом параграфе, сделан, опираясь наработу Пардалоса и др. [57], в которой очень подробно представлена историяразвития алгоритмов поиска максимальных независимых множеств.Самым первым алгоритмом для перечисления всех клик принято считатьалгоритм Харари (Harary) и Росс (Ross) 1957 года [40]. В своей работе они17представили метод для определения всех клик в специальном графе, которыйимел не больше трех клик. На создание подобного алгоритма их мотивироваланеобходимость решения подобных задач в социометрии.В 1970 году Августон (Auguston) и Минкер (Minker) [25] представили результаты исследования технологии кластеризации, применяемой в информационных системах, с точки зрения теории графов.
В их работе проводилосьсравнение алгоритмов Биерстона (Bierston) и Боннера (Bonner). Метод, используемый в обоих алгоритмах, получил название метод последовательности вершин (the vertex sequence method), или метод удаления точки (point removal method) [57]. Исходя из результатов вычислительного эксперимента ониустановили, что алгоритм Биерстона является более эффективным. Оригинальная работа Биерстона опубликована не была [57].
Та версия алгоритма, котораябыла протестирована Августоном и Минкером, содержала две ошибки, которыебыли исправлены Маллиганом (Mulligan) [53] в 1972 году.Затем в 1973 году были представлены два новых алгоритма, использующихметод поиска с возвращением (backtracking method). Это были алгоритм Аккоюнлу (Akkoyunlu) [24] и алгоритм Брона-Кербоша [27]. Основным преимуществомэтих алгоритмов было отсутствие повторной генерации уже сформированныхклик. Согласно результатам тестирования, приведенным в [27], алгоритм БронаКербоша является более эффективным, чем алгоритм Биерстона.Вслед за работой [27] в 70-х и 80-х годах последовали и другие публикации,посвященные проблеме поиска клик и максимальных независимых множеств вграфе.
Среди них статьи [45], [49], [50] и [54].Алгоритм Остина (Osteen) [54] был разработан для графов специальноговида. В работе [50] был представлен метод, который основывался на разбиенииисходного графа на «цепочку подграфов», удовлетворяющих определенным требованиям. При таком разбиении можно гарантировать, что хотя бы в одномподграфе клика будет содержаться целиком.
Лукакис (Loukakis) [49] и Джон-18сон (Johnson) [45] представили алгоритмы для генерации всех максимальныхнезависимых множеств в лексикографическом порядке.В 2004 году в работе [42] были приведены результаты сравнения работыалгоритмов Лукакиса (Loukakis), Цукияма (Tsukiyama) и Чиба (Chiba) с алгоритмом Брона-Кербоша и его различными вариациями.
Согласно этим результатам алгоритм Брона-Кербоша до сих пор является одним из самых эффективных для решения задачи о поиске всех максимальных независимых множествнеориентированного графа.В 2006 году в работе [69] была представлена очередная модификация алгоритма Брона-Кербоша. Опираясь на результаты Муна [52] также была полученаоценка его временной сложности: O(3n/3 ).Все вышеперечисленные алгоритмы решают задачу о построении всех максимальных независимых множеств графа, но нередко во многих практическихзадачах возникает необходимость найти только наибольшее из них.Одним из основных методов поиска наибольшего независимого множестваявляется метод ветвей и границ.
Большинство алгоритмов используют его вкачестве организации вычислительного процесса.Изучение проблемы поиска наибольшего независимого множества началосьв 70-е годы с работ Хука (Houck) [44] и Тарьяна (Tarjan) [66]. Тарьян и Трояновски (Trojanowski) представили рекурсивный алгоритм решения задачи онаибольшем независимом множестве. Также в работе [66] была получена оценкавременной сложности предложенного алгоритма: O(2 n/3 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
