- •Курсовая работа На тему: Внешняя устойчивость графа.
- •Постановка задачи
- •Сведения из теории
- •Множество внешней устойчивости
- •Основные используемые законы алгебры высказываний
- •Решение задачи с помощью алгоритма Магу Построение матрицы смежности
- •Составление условия входимости
- •Преобразование выражения
- •Проверка результатов.
- •Заключение
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Пермский национальный исследовательский политехнический университет Кафедра ИТАС
Курсовая работа На тему: Внешняя устойчивость графа.
Выполнил: студент гр.АСУ-11
Усанин Ф.Н.
Проверил: преподаватель
Соловьев А.Е.
Пермь, 2012
Оглавление
Постановка задачи……………………………………………………………………………………………. 3
Сведения из теории………………………………………………………………………………………….. 4
Множество внешней устойчивости
Основные используемые законы алгебры высказываний
Решение задачи с помощью алгоритма Магу…………………………………………………. 5
Построение матрицы смежности
Составление условия входимости
Преобразование выражения
Проверка результатов………………………………………………………………………………………. 9
Заключение……………………………………………………………………………………………………… 10
Постановка задачи
Найти внешнюю устойчивость графа при игре конем на поле 4х4.
То есть найти минимальное число клеток и их координат на доске, таких, что если поставить в них коней, они смогли бы держать под боем все клетки шахматной доски размером 4х4.
Сведения из теории
Множество внешней устойчивости
Множество называется множеством внешней устойчивости, если вершины входят в это множество или имеют стрелки в этом множестве.
Для нахождения внешней устойчивости графов используют специальный алгоритм - алгоритм Магу
Алгоритм Магу состоит из следующих этапов:
1. Для графа составляется матрица смежности
2. Матрица смежности дополняется единицами по главной диагонали.
3. Выписывается условие входимости (построчные дизъюнкции)
4. Выражение приводится к ДНФ.
5. Все вершины, входящие в элементарную конъюнкцию, образуют множество внешней устойчивости
Основные используемые законы алгебры высказываний
Дистрибутивный закон
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 |