Ядро графа

Множество внешней устойчивости - такое множество вершин графа, что:

1) либо вершины принадлежат этому множеству.

2) либо они имеют дуги в этом множестве.

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

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

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

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

Для решения этой задачи также используется соответствующий алгоритм Магу.

Возьмем граф из предыдущего примера:

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

Множества, одновременно внутренне и внешне устойчивые называются ядром графа.

Для рассмотренного графа - {b, c}

В графе может быть несколько ядер (например - 2)

или не быть совсем.

Клика

Клика - максимально большой полный подграф данного графа.

a

f b

e c

d