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

Ядро графа

Множество внешней устойчивости.

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

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

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

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

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

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

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

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

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

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

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

M M

Матрица M² дает все пути длиной в 2

Матрица Мⁿ - пути длиной в n.

Если Мⁱ - нулевая матрица, то наибольший путь в графе имеет длину i - 1.

Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц

M^* = M¹ È M² È M³ ...

Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.