I.                  Независимые множества.

 

Пусть дан граф G=(X,E) – неориентрированный произвольный граф

 

 

• Определение №1:                          ( Независимое множество )

Множество Y вершин графа X (Y содержится в Х), попарно несмежных, называется независимым или внутриустойчивым множеством графа G.

 

Очевидно, что подграф графа G, порожденный независимым множеством является пустым графом.

 

           

• Определение №2:                                    ( Максимальное множество )

Максимальное независимое множество графа G – это независимое множество графа G, несодержащееся полностью ни в одном другом независимом множестве данного графа.

 

                                  

 

• Определение №3:                           ( Наибольшее множество )

Независимое множество максимальной мощности графа G называется наибольшим независимым множеством графа.

                                  

 

• Определение №4:                               ( Число независимости множество )

Мощность наибольшего независимого множества графа называется числом независимости графа.

 

                        Обозначается: α_o (G)

 

II.               Практический пример.

 

#1 (4)  Найти матрицу смежности (A) и инцидентности (B).

 

#2 (2c)  Перечислить все максимальные независимые и наибольшие независимые множества графа G, показанного на рисунке, и найти число независимости .

 

 

                                                              

Решение:

                                                • Максимальные независимые множества:

 

Y₁ = {x_1, x_3, x₅}           Y₂ = {x_1, x_4, x₉}           Y₃ = {x_1, x_6, x₉}           Y₄ = {x_1, x_3, x₆}           Y₅ = {x_1, x_4, x₈}

Y₆ = {x_1, x_5, x₈}           Y₇ = {x_1, x_6, x₈}           Y₈ = {x_2, x_4, x₈}           Y₉ = {x_2, x_5, x₇}           Y₁₀ = {x_2, x_5, x₈}

Y₁₁ = {x_2, x_6, x₈}          Y₁₂ = {x_3, x_5, x₁₀}         Y₁₃ = {x_3, x_6, x₁₀}         Y₁₄ = {x_4, x_8, x₁₀}         Y₁₅ = {x_5, x_7, x₁₀}

                                               Y₁₆ = {x_5, x_8, x₁₀}                    Y₁₇ = {x_6, x_8, x₁₀}

 

           

                                                • Наибольшие независимые множества:

 

Y = {x_1, x_5, x_7, x₉}

 

                                                                             α_o (G) = 4

 

 

III.           Алгоритм Брона-Кербоша.

 

Алгоритм Брона-Кербоша - алгоритм поиска всех клик* (а так же максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик.

*Кликой в неориентированном графе называется подмножество вершин, каждые две из  которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней.

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

Легко показать, что задача о клике и задача о независимом множестве по сути эквивалентны: каждая из них получается из другой, путем построения дополнения графа — такого графа, в котором есть все вершины исходного графа, причем в дополнении графа вершины соединены ребром тогда и только тогда, если они не были соединены в исходном графе.

 

IV.            Текст программы.

 

V.               Output программы.

 

VI.            Вывод.

 

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