Множество внешней устойчивости - такое множество вершин графа, что:
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 b
g
c
f
e d
Требуемые результаты получаются путем перемножения матриц смежности графа.
M - матрица смежностей, показывает пути длиной в 1 в данном графе.
a
b
c
d
e
f
g
a
b
c
d
e
f
g
a
b
c
d
e
f
g
a
b
c
d
e
f
g
M M
Матрица M2 дает все пути длиной в 2
a
b
c
d
e
f
g
a
b
c
d
e
f
g
Матрица Мn - пути длиной в n.
Если Мi - нулевая матрица, то наибольший путь в графе имеет длину i - 1.
Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц
M* = M1 È M2 È M3 ...
Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.