Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Пермский национальный исследовательский политехнический университет Кафедра ИТАС

Курсовая работа На тему: Внешняя устойчивость графа.

Выполнил: студент гр.АСУ-11

Усанин Ф.Н.

Проверил: преподаватель

Соловьев А.Е.

Пермь, 2012

Оглавление

Постановка задачи……………………………………………………………………………………………. 3

Сведения из теории………………………………………………………………………………………….. 4

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

Основные используемые законы алгебры высказываний

Решение задачи с помощью алгоритма Магу…………………………………………………. 5

Построение матрицы смежности

Составление условия входимости

Преобразование выражения

Проверка результатов………………………………………………………………………………………. 9

Заключение……………………………………………………………………………………………………… 10

Постановка задачи

Найти внешнюю устойчивость графа при игре конем на поле 4х4.

То есть найти минимальное число клеток и их координат на доске, таких, что если поставить в них коней, они смогли бы держать под боем все клетки шахматной доски размером 4х4.

Сведения из теории

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

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

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

Алгоритм Магу состоит из следующих этапов:

1.      Для графа составляется матрица смежности

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

3.      Выписывается условие входимости (построчные дизъюнкции)

4.      Выражение приводится к ДНФ.

5.      Все вершины, входящие в элементарную конъюнкцию, образуют множество внешней устойчивости

2. Основные используемые законы алгебры высказываний

Дистрибутивный закон

AvB*C=(AvB)*(AvC) A*(BvC)=A*BvA*C

Закон идемпотентности

AvA=A A*A=A

Закон поглощения

AvA*B=A A*(AvB)=A

Решение задачи с помощью алгоритма Магу Построение матрицы смежности

	A	B	C	D
1
2
3
4

	A1	A2	A3	A4	B1	B2	B3	B4	C1	C2	C3	C4	D1	D2	D3	D4
A1	1						1			1
A2		1						1	1		1
A3			1		1					1		1
A4				1		1					1
B1			1		1						1			1
B2				1		1						1	1		1
B3	1						1		1					1		1
B4		1						1		1					1
C1		1					1		1						1
C2	1		1					1		1						1
C3		1		1	1						1		1
C4			1			1						1		1
D1						1					1		1
D2					1		1					1		1
D3						1		1	1						1
D4							1			1						1