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

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

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).

28. Деревья. Центры и центроиды.

29. Определение путей в графе.

30. Приведение графа к ЯПФ.

31. Планарные графы. Теорема Эйлера.

32. Проблема 4-х красок.

33. Теорема Менгера

34. Теорема Холла

35. Понятие группы

36. Отображения. Морфизмы.

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

Множество внешней устойчивости – множество вершин, для которых выполняется одно из следующих правил:

1) Любая вершина входит в это множество

2) Либо вершина не входит в это множество, но из этой вершины есть дуга в данное множество.

Поиск внешне устойчивого множества происходит в другой классической задаче:

Как расставить минимальное число ферзей, чтобы все поля доски были под боем.

a

f b

e c

d

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

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

1. Матрица смежности дополняется единицами (1) по главной диагонали.

2. Выписываем построчные дизъюнкции.

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

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

Получим: acd Ú aef Ú bc Ú ce

Эти конъюнкции и дают множества внешней устойчивости.

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

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

25. Ядро графа.

???