Максимальное независимое множество вершин в дереве

Министерство  образования Республики Беларусь

Учреждение  образования

«Белорусский  государственный  университет транспорта» 
 
 
 
 

    Кафедра «Информационные  технологии»

    Максимальное  независимое множество вершин в дереве

 

    

Оглавление

    Введение 3

    Основные определения 4

    Построение всех максимальных независимых множеств 5

    Список использованной литературы 8 

 

    

    Введение

     Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V, E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, – ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.

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

     Матрица смежности – это двумерный массив размерности N*N. 

     A [i, j]=  

    Для хранения перечня ребер необходим  двумерный массив R размерности M*2. Строка массива описывает ребро. 
 
 
 
 

    Основные  определения

    Рассмотрим  неориентированный граф G=(V,E).

    Независимое множество вершин (внутренне  устойчивое множество) — это множество вершин графа G такое, что любые две вершины в нем не смежны, то есть никакая пара вершин не соединена ребром. Любое подмножество S, содержащееся в V, и такое, что пересечение S с множеством вершин смежных с S пусто, является независимым множеством вершин.

    Множество S⊂V, удовлетворяющее условию.

    S∩E(S)=Ø     (1)

    называется  независимым множеством вершин.

    Для графа, изображенного на рисунке 1, независимыми являются {x₇,x₈,x₂}, {x₃,x₁} множества вершин.

    Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Если множество удовлетворяет условию (1) и условию

    H∩E(H)≠Ø ∀H⊃S   (2)

    является  максимальным независимым множеством. Например, множества {x₁,x₃,x₇} и {x₄,x₆} максимальные независимые, а {x₇,x₈,x₂} — нет. В графе может быть более одного независимого множества.

    Если  Q является семейством всех независимых множеств графа G, то

    α[G]=max_S∈Q|S  (3)

    называется  числом независимости графа G, а множество S*, на котором достигается этот максимум, называется наибольшим независимым множеством.

    

    Максимальный  полный подграф (клика) графа G это порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин H, содержащем S, не является полным. То есть, в отличие от максимального независимого множества, в клике все вершины попарно смежны.

    Аналогично  тому, как было определено число  независимости графа, с помощью  соотношения (3) мы можем определить кликовое число графа (известное также как густота или плотность). Это — максимальное число вершин в кликах данного графа. Тогда, образно говоря, у "плотного" графа кликовое число будет, вероятно, больше, а число независимости меньше, в то время как у "разреженного" графа, по всей вероятности, будет иметь место противоположное соотношение между этими числами.

    Построение  всех максимальных независимых  множеств

    Если  граф небольшой (например, с числом вершин, не превосходящим 20), то построить  максимальное независимое множество  можно последовательным перебором независимых множеств с одновременной проверкой каждого множества на максимальность. Если же вершин много, то этот процесс становится сложным технически. Число максимальных независимых множеств возрастает, но во время поиска большое число независимых множеств формируется, а затем вычеркивается, так как обнаруживается, что они содержатся в других, ранее полученных множествах и поэтому не являются максимальными.

    Этот  алгоритм является существенно упрощенным перебором, использующим дерево поиска. В процессе поиска — на некотором  этапе k — независимое множество вершин S_k расширяется путем добавления к нему подходящим образом выбранной вершины (чтобы получилось новое независимое множество S_k+1) на этапе k+1, и так поступают до тех пор, пока добавление вершин станет невозможным, а порождаемое множество не станет максимальным независимым множеством. Пусть Q_k будет на этапе k наибольшим множеством вершин, для которого S_k∩Q_k=Ø, то есть после добавления любой вершины из Q_k к S_k получается независимое множество S_k+1. В некоторый произвольный момент работы алгоритма множество Q_k состоит из вершин двух типов: подмножества Q_k^- тех вершин, которые уже использовались в процессе поиска для расширения множеств S_k, и подмножества Q_k⁺ таких вершин, которые еще не использовались. Тогда дальнейшее ветвление в дереве поиска включает процедуру выбора вершины x_ik ∈ Q_k⁺, добавление ее к S_k для построения множества

    S_k+1 = S_k ∪ {x_ik}    (4)

    и порождение новых множеств:

    Q_k+1^- = Q_k^- − E(x_ik)    (5)

    и

    Q_k+1⁺ = Q_k⁺ − (E(x_ik) ∪ {x_ik}).    (6)

    Шаг возвращения алгоритма состоит  в удалении вершины x_ik из S_k+1, чтобы вернуться к S_k, изъятии x_ik из старого множества Q_k⁺ и добавлении x_ik к старому множеству Q_k^- для формирования новых множеств Q_k⁺ и Q_k^-.

    Множество S_k является максимальный независимым множеством только тогда, когда невозможно его дальнейшее расширение, т.е. когда Q_k⁺=Ø. Если Q_k⁺ ≠ Ø, то текущее множество S_k было расширено на некотором предшествующем этапе работы алгоритма путем добавления вершины из Q_k^-, и поэтому оно не является максимальным независимым множеством. Таким образом, необходимым и достаточным условием того, что S_k — максимальное независимое множество, является выполнение равенств

    Q_k⁺ = Q_k^- = Ø.  (7)

    Если  очередной этап работы алгоритма  наступает тогда, когда существует некоторая вершина х∈Q_k^-, для которой E(x)∩Q_k⁺=Ø, то безразлично, какая из вершин, принадлежащих Q_k⁺, используется для расширения S_k, и это справедливо при любом числе дальнейших ветвлений; вершина х не может быть удалена из Q_p^- на любом следующем шаге р>k. Таким образом, условие

    ∃ x ∈ Q_k^-, такая, что E(x) ∩ Q_k⁺ = Ø,   (8)

    является  достаточным для осуществления  шага возвращения, поскольку из S_k при всяком дальнейшем ветвлении уже не получится максимальное независимое множество.

    Как и во всяком методе, использующем дерево поиска, здесь выгодно стремиться начать шаги возвращения как можно раньше, поскольку это ограничит "размеры" "ненужной" части дерева поиска. Следовательно, целесообразно сосредоточить усилия на том, чтобы возможно раньше добиться выполнения условия (8) с помощью подходящего выбора вершин, используемых при расширении множеств S_k. На каждом следующем шаге процедуры можно выбирать для добавления к S_k любую вершину x_ik ∈ Q_k⁺ на шаге возвращения x_ik будет удалена из Q_k⁺ и включена в Q_k^-. Если вершину x_k выбрать так, чтобы она принадлежала множеству E(х) при некоторой вершине х из Q_k^-, то на соответствующем шаге возвращения величина

    Δ(x) = |E(x) ∪ Q_k⁺|   (9)

    уменьшится  на единицу (по сравнению с тем  значением, которое было до выполнения прямого шага в шага возвращения), так что условие (8) теперь станет выполняться раньше.

    Таким образом, один из возможных способов выбора вершины x_ik для расширения множества S_k состоит, во-первых, в нахождении вершины x* ∈ Q_k^- с возможно меньшим значением величины Δ(х*) и, кроме того, в выборе вершины x_i из множества E(x*)∩Q_k⁺. Такой выбор вершины x_ik будет приводить на шаге возвращения к уменьшению величины Δ(x*) — каждый раз на единицу — до тех пор, пока вершина x* не станет удовлетворять условию (8) при выполнении шага возвращения.