Внутренняя устойчивость графа

Множество внутренней устойчивости - множество несмежных вершин графа.

a

f b

e c

d

	a	b	c	d	e	f
a
b
c
d
e
f

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

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

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

Последние годы ситуация изменилась.

Для нахождения таких множеств появился замечательный алгоритм Магу, который,

Фактически дает аналитическое (!) решение этой задачи.

Алгоритм Магу.

1. По единицам матрицы строим парные дизъюнкты.

(а Ú b)(a Ú c)(b Ú e)(c Ú f)(d Ú b)(d Ú e)(e Ú c)(f Ú b)(f Ú d)(f Ú e)

2. Преобразуем в ДНФ, выполнив все возможные поглощения и операции идемпотентности.

Получим: bcde Ú bcef Ú adef Ú afeb Ú fbdc

3. Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.

{ a, f }, { a, d }, { a, e }, { b, c }, { c, d }

Максимальное из таких множеств дает число внутренней устойчивости (здесь оно равно 2).