Специальная математика (стр. 9 )

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

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

M* = M1 È M2 È M3 …

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

4.9. Приведение графа к ярусно-параллельной форме

Эти рассуждения имеют смысл для ориентированных графов без контуров.

Граф находится в ярусно-параллельной форме (ЯПФ), если в нулевом ярусе размещаются вершины, имеющие нулевую полустепень захода, в i-том ярусе - вершины, в которые заходят дуги только из предыдущих ярусов, причем хотя бы одна дуга из (i - 1)-го яруса.

Пусть дан произвольный граф без циклов.

a

h b

g c

f d

e

	a	b	c	d	e	f	g	h
a			1
b
c		1
d					1			1
e	1						1
f			1
g		1	1
h	1					1

Алгоритм приведения к ЯПФ:

1. Матрица смежности графа просматривается, и в очередной ярус выбираются вершины с нулевой полустепенью захода, соответствующие нулевым столбцам.

2. Строки, соответствующие выбранным на предыдущем шаге вершинам, обнуляются.

3. Осуществляется возврат к шагу 1, до полного исчерпания матрицы.

4. Прорисовываются дуги.

В результате, вышеприведенный граф примет вид:

d

 

e h

g f

a

 

c

b

Ширина яруса определяется числом вершин в ярусе.

Ширина графа в ЯПФ определяется шириной самого большого яруса.

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

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

a

f b

 

e c

 

d

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

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

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

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

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

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

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

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

(a Ú 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).

4.11. Множество внешней устойчивости. Ядро графа.

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

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

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

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

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

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

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

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

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

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

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

1. По главной диагонали проставляем 1.