Алгоритмы нахождения независимого множества

ФОРМУЛИРОВКА ЗАДАЧИ
Дано: неориентированный граф G (V ,E ).
Задача: найти максимальное по числу элементов независимое множество в графе G .
Максимальное независимое
множество: {1, 4, 6, 7}

ФОРМУЛИРОВКА ЗАДАЧИ
Дано: неориентированный граф G (V ,E ).
Задача: найти максимальное по числу элементов независимое множество в графе G .
Максимальное независимое
множество: {1, 4, 6, 7}
Есть и другие максимальные
независимые множества:
{5, 6, 7, 8}

ФОРМУЛИРОВКА ЗАДАЧИ
Дано: неориентированный граф G (V ,E ).
Задача: найти максимальное по числу элементов независимое множество в графе G .
Максимальное независимое
множество: {1, 4, 6, 7}
Есть и другие максимальные
независимые множества:
{5, 6, 7, 8}
{2, 3, 5, 8}

МЕТОД ПОЛНОГО ПЕРЕБОРА
Алгоритм полного перебора проверяет все подмножества вершин, являются ли они независимыми множествами. Этот способ является самым простым и очевидным.

МЕТОД ПОЛНОГО ПЕРЕБОРА
Алгоритм проверяет каждую вершину на независимость с другими вершинами и составляет для нее независимое множество.
Каждое найденное множество необходимо проверять на максимальную независимость.
Для этого нужно определять, является ли оно подмножеством какого-либо другого найденного независимого множества.
Вычислительная сложность полного перебора O(n2 2n).

АНАЛИЗ МЕТОДА ПОЛНОГО ПЕРЕБОРА
Различное количество вершин (Плотность 0.3)

АНАЛИЗ МЕТОДА ПОЛНОГО ПЕРЕБОРА
Различная плотность (Количество вершин 50)

АЛГОРИТМ
БРОНА-КЕРБОША
Способом уменьшения количества рассматриваемых вариантов является поиск с возвращением, этот метод лежит в основе алгоритма Брона-Кербоша.
Находит все максимальные по включению независимые множества.

АЛГОРИТМ
БРОНА-КЕРБОША
На каждом шаге алгоритма множество V разбито на четыре части:
M — текущее независимое множество;
Γ(M) — множество вершин, смежных с M;
K – множество кандидатов, т. е. вершин, каждая из которых может быть добавлена в M;
P – множество просмотренных вершин, каждая из которых не может быть добавлена в текущее M, так как уже добавлялась ранее.

АНАЛИЗ АЛГОРИТМА БРОНА-КЕРБОША
Случайный граф плотностью 70%.

АНАЛИЗ АЛГОРИТМА БРОНА-КЕРБОША
Различная плотность (Количество вершин 50)

СРАВНЕНИЕ АЛГОРИТМОВ
Сравнение алгоритмов при различном количестве вершин:

СРАВНЕНИЕ АЛГОРИТМОВ
Сравнение алгоритмов при различной плотности графа:

ВЫВОД
На основании проведенного исследования можно сделать вывод, что алгоритм Брона-Кербоша остается одним из самых эффективных на сегодняшний день для поиска наибольшего независимого множества.