Федеральное агентство по образованию Российской федерации
Пермский национальный исследовательский политехнический университет
Кафедра ИТАС
Курсовая работа.
Нахождение внутренней устойчивости.
Проверил: доц. Соловьев А.Е
Выполнил студент группы ЭВТ-11: Надымов Д.В
2012
Оглавление
-
Постановка задачи……………………………………………………………. 2
-
Теоретические сведения………………………………………………….. 2
-
Решение поставленной задачи…………………………………………. 2
-
Матрица смежности………………………………………………………. 2
-
Множество несовместимости…………………………………………3
-
Переход от множества несовместимости к ДНФ……………3
-
ДНФ………………………………………………………………………………….9
-
Дополнения……………………………………………………………..17
-
Число внутренней устойчивости……………………………20
-
Заключение………………………………………………………………………………21
-
Постановка задачи
Найти наибольшее число слонов можно расставить на доске так, чтобы никакие две из них не угрожали друг другу.
-
Теоретические сведения
Множество- совокупность различных элементов, мыслимая как единое целое
Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).
Неориентированный граф G = (V, Е) состоит из конечного множества вершин V и множества ребер Е. В отличие от ориентированного графа, здесь каждое ребро (V,w) соответствует неупорядоченной паре вершин: если (V,w) — неориентированное ребро, то (V, w) = (w, V).
Множество вершин графа называется независимым, если никакие две из них не соединены между собой ребрами. Среди независимых множеств существует хотя бы одно максимально независимое, содержащее максимальное число вершин. Это число вершин называется числом независимости для данного графа (или числом его внутренней устойчивости).
Дизъю́нкция(v) — (лат. disjunctio - разобщение) логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу».
Конъю́нкция (от лат. conjunctio союз, связь) — логическая операция, по своему применению максимально приближённая к союзу "и".
Нормальная форма – это синтаксически однозначный способ записи формулы, реализующей данную функцию. Любую булеву формулу можно привести к равносильной ей формуле простого стандартного вида, которой будет являться дизъюнкция элементов, каждый из которых представляет собой конъюнкцию отдельных различных логических переменных либо со знаком отрицания, либо без него. Такая форма называется дизъюнктивной нормальной формой (ДНФ).
Слон- шахматная фигура, которая может перемещаться на любое число полей по диагонали, при условии, что на его пути нет фигур. Каждый слон может перемещаться либо только по белым полям, либо только по чёрным, поэтому слонов называют белопольными и чернопольными соответственно.
-
Решение поставленной задачи.
3.1 Матрица смежности.
Для того чтобы осуществить задуманное, то есть найти число внутренней устойчивости надо составить матрицу смежности. Ставим слона в каждую клетку нашей шахматной доски (размеры 5 на 5 клеток, строки доски обозначим буквами от A до E, а её столбцы цифрами от 1 до 5), при этом, записываем в матрицу 1, если клетка находится под ударом. Например, если поставим слона в клетку A1, то он сможет пройти по диагонали доски, то есть в матрицу смежности мы запишем единицы на место клеток B2,C3,D4 и E5. В дальнейшем, матрицу смежности будем называть матрица.
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
B1 |
B2 |
B3 |
B4 |
B5 |
C1 |
C2 |
C3 |
C4 |
C5 |
D1 |
D2 |
D3 |
D4 |
D5 |
E1 |
E2 |
E3 |
E4 |
E5 |
|
A1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
A2 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
A3 |
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
A4 |
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
A5 |
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
B1 |
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
B2 |
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
B3 |
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
1 |
|
|
|
|
|
|
B4 |
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
1 |
|
|
|
|
|
B5 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
C1 |
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
C2 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
C3 |
1 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
1 |
|
C4 |
|
1 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
C5 |
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
D1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
D2 |
|
|
|
|
1 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
|
|
D3 |
|
|
|
|
|
1 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
|
D4 |
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
1 |
|
D5 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
E1 |
|
|
|
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
E2 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
E3 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
E4 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
E5 |
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|