- •Оглавление
- •Глава 1. Алгебраические системы 17
- •Глава 2. Элементы комбинаторики 88
- •Глава 3. Основы теории графов 101
- •Глава 4. Основы математической логики 169
- •4.1.1.4. Эквивалентные преобразования формул 179
- •4.1.4. Выполнить подстановку: 247
- •Глава 5. Основы теории алгоритмов 252
- •Глава 6. Конечные автоматы 289
- •Введение
- •Глава 1. Алгебраические системы
- •1.1 Множества
- •1.1.1. Четкие множества
- •1.1.2. Нечеткие множества
- •1.2. Соответствия, отображения и функции
- •1.2.1. Четкие отображения и функции
- •1.2.2. Нечеткие отображения
- •1.3. Отношение
- •1.3.1. Четкие отношения
- •1.3.2. Нечеткое отношение
- •1.4. Элементы общей алгебры
- •1.5. Булева алгебра
- •1.5.1. Булевы операции
- •1.5.2. Законы булевой алгебры
- •1.5.3. Формула булевой функции
- •1.5.4. Описание булевой функции
- •1.5.5. Суперпозиция булевых функций
- •1.5.6. Свойства булевых функций
- •1.5.6.1. Самодвойственные булевы функции
- •1.5.6.2. Монотонные булевы функции
- •1.5.6.3. Линейные булевы функции
- •1.5.6.4. Функции, сохраняющие “0”
- •1.5.6.5. Функции, сохраняющие “1”
- •1.5.6.6. Функционально полные системы
- •1.5.7. Разложение булевых функции
- •1.5.7.1. Днф булевой функции
- •1.5.7.2. Кнф булевой функции
- •Алгоритм преобразования формулы к скнф:
- •1.5.8. Минимизация булевых функций.
- •1.5.8.1.Минимизация днф булевой функции
- •1.5.8.2. Минимизация кнф булевой функции
- •1.6. Алгебра четких множеств
- •1.6.1. Операции над множествами
- •1.6.2. Законы алгебры множеств
- •1.6.3. Эквивалентные преобразования формул
- •1.6.4. Композиция отображений и отношений
- •1.6.5. Поиск неизвестного множества
- •1.7. Алгебра нечетких множеств
- •1.7.1. Операции над нечеткими множествами
- •1.7.2. Композиция нечетких отображений
- •1.7.3. Композиция нечетких отношений
- •1.7.4. Свойства нечетких отношений
- •Вопросы и задачи
- •Глава 2. Элементы комбинаторики
- •2.1. Размещение из n элементов по k
- •2.2. Перестановка элементов
- •2.3 Сочетание из n элементов по k
- •2.4. Разбиение множества
- •2. 5 Правила комбинаторики
- •Вопросы и задачи
- •Глава 3. Основы теории графов
- •3.1. Граф и его характеристики
- •3.2. Описание графа
- •3. 3. Числа графа
- •3.4. Операции над графами
- •3.4.1. Унарные операции
- •3.4.1.1 Поиск дополнительного графа
- •3.4.1.2. Введение и удаление вершин графа
- •3.4.1.3. Стягивание вершин графа
- •3.4.1.4. Введение и удаление ребер графа
- •3.4.1.5. Поиск плотности и неплотности графа
- •3.4.1.6. Поиск числа компонент связности графа
- •3.4.1.7. Поиск устойчивости графа
- •3.4.1.8. Поиск цикломатического числа графа
- •3.4.1.9. Поиск хроматического числа графа
- •3.4.2. Бинарные операции
- •3.4.2.1. Объединение графов
- •3.4.2.2. Пересечение графов
- •3.4.2.3. Композиция графов
- •3.4.2.4. Соединение графов
- •3.4.2.5. Прямое произведение графов
- •3.4.2.6. Изоморфизм графов
- •3.5. Некоторые алгоритмы на графах
- •3.5.1. Построение покрывающего остова
- •3.5.2. Построение остова минимального веса
- •3.5.3. Поиск кратчайших путей в сети.
- •3.5.4. Поиск максимального потока в сети
- •3.5.5. Метод критического пути в управлении
- •3.6. Нечеткие графы
- •Вопросы и задачи
- •Глава 4. Основы математической логики
- •4.1. Логика высказываний
- •4.1.1. Алгебра высказываний
- •4.1.1.1. Логические операции
- •4.1.1.2. Правила записи сложных формул.
- •4.1.1.3. Законы алгебры высказываний
- •4.1.1.4. Эквивалентные преобразования формул
- •4.1.1.5. Нормальные формы формул
- •4.1.2. Исчисление высказываний
- •4.1.2.1. Интерпретация формул
- •4.1.2.2. Аксиомы и правила введения и удаления логических связок
- •4.1.2.3. Метод дедуктивного вывода
- •4.1.2.4. Принцип резолюции
- •4. 2. Логика предикатов
- •4.2.1. Алгебра предикатов
- •4.2.1.1. Законы алгебры предикатов
- •4.2.1.2. Предваренная нормальная форма формулы
- •4.2.1.3 Сколемовская стандартная форма формулы
- •4. 2. 2. Исчисление предикатов
- •4.2.2.1. Правила подстановки
- •4.2.2.2. Правила введения и удаления кванторов
- •4.2.2.3. Правила заключения
- •4.2.2.4. Метод дедуктивного вывода
- •4.2.2.5. Принцип резолюции
- •4.2.2.6. Логическое программирование
- •4.3. Логика реляционная
- •4.3.1 Реляционная алгебра
- •4.3.1.1. Унарные операции
- •4.3.1.2. Бинарные операции
- •4.3.1.3. Правила реляционной алгебры
- •4.3.2. Реляционное исчисление
- •4.3.3. Языки реляционной логики
- •4.4. Нечеткая логика
- •4.4.1. Нечеткое исчисление
- •4.4.2. Экспертные системы
- •Вопросы и задачи
- •Глава 5. Основы теории алгоритмов
- •5.1. Рекурсивные функции
- •5.1.1. Базовые функции
- •5.1.2. Элементарные операции
- •5.2. Машина Тьюринга
- •5.2.1. Описание машины Тьюринга
- •5.2.2. Примеры машин Тьюринга
- •5.2.3. Композиция машин Тьюринга
- •5.3. Нормальные алгоритмы Маркова
- •5.4 Сложность вычислений
- •Вопросы и задачи
- •Глава 6. Конечные автоматы
- •6.1. Абстрактный автомат
- •6.1.1. Типы конечных автоматов
- •6.1.2. Описание автоматов
- •6.1.3. Автоматное моделирование алгоритмов
- •6.1.3.1. Автомат Мили - модель управляющего автомата
- •6.1.3.2. Автомат Мура - модель управляющего автомата
- •6.1.3.3. Микропрограммный автомат
- •6.1.4. Эквивалентность автоматов
- •6.1.5. Эквивалентность внутренних состояний автомата
- •6.1.5.1. Детерминированный автомат
- •6.1.5.2. Недетерминированный автомат
- •6.2. Структурный автомат
- •6.2.1. Произведение автоматов
- •6.2.1.1. Последовательное соединение автоматов
- •6.2.1.2. Параллельное соединение автоматов
- •Обратная связь автоматов
- •6.2.3. Сумма автоматов
- •6.2.4. Структурный автомат и кодирование
- •6.3. Логическое проектирование автоматов
- •6.3.1. Кодирование алфавитов автомата
- •6.3.2. Автоматы без “памяти”.
- •6.3.2.1. Формирование оператора
- •6.3.2.2. Формирование системы операторов
- •Логическая схема комбинационного автомата
- •6.3.3. Автоматы с “памятью”
- •6.3.3.1. Формирование оператора
- •6.3.3.2. Формирование оператора
- •.3.3.3. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
3.2. Описание графа
Граф может быть задан списком или матричными структурами.
Списки. При описании графа списками используют модели G=<X; r> и G=<X; h>.
Первая форма - список отношений - применяется в тех случаях, когда необходимо хранить информацию о весе ребра (протяжённость, загрузка, пропускная способность линии связи и т.п.) и поиска инцидентных вершин.
В таблице 3.1 приведены характеристики графа, описанного рис.3.11а) по модели G=<X; r>.
Таблица 3.1. |
|||||||
ri |
r1 |
r2 |
r3 |
r4 |
r5 |
r6 |
r7 |
(xi, xj) |
(x1,x2) |
(x5,x6) |
(x2,x5) |
(x2,x3) |
(x1,x4) |
(x3,x4) |
(x3,x6) |
l(ri) |
2 |
4 |
5 |
8 |
4 |
8 |
5 |
Вторая форма - список смежности - применяется в тех случаях, когда необходимо хранить информацию о весе вершины (время исполнения оператора, надёжность контактной площадки или загруженность узла и т.п.) и поиска смежных вершин.
В таблице 3.2.приведены характеристики графа, описанного рис.3.11b) по модели G=<X; h>.
Таблица 3.2 |
||||||
xi |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
h(xi) |
x2, x3, x4 |
x1, x3, x5 |
x1, x4, x6 |
x1, x3 |
x2, x6 |
x3, x5 |
p(xi) |
0,9 |
0,8 |
0,8 |
0,6 |
0,8 |
0,9 |
При описании графа матрицами используют, прежде всего, матрицы инциденции и матрицы смежности
Матрица инциденции. Поскольку инциденция есть отношение принадлежности элемента одного множества другому, то для графа G=<X, r> матрица инциденции ||q|| фиксирует эту принадлежность элемента множества r элементу множества X на множестве {0, 1}. Строки матрицы есть элементы множества r, а столбцы – элементы множества X. Элементы матрицы инциденции неориентированного графа определяются по формуле:
1, если ri=(xi, xj) инцидентно xj,
q(i. j) =
0, в противном случае.
В каждой строке матрицы количество единиц равно двум, а в каждом столбце - степени вершины - i .
В таблице 3.3. приведена матрица инциденции для неориентированного графа, представленного на рис. 3.2.
Особый интерес представляют петли на графе. Например, у вершины x4 есть петля, концевые вершины которой принадлежат x4. При задании графа с петлями рекомендуется расщеплять матрицу на две: матрицу-истоков и матрицу-стоков, т. е рассматривать две матрицы ориентированного графа.
Таблица 3.3. |
||||||
q |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
r01 |
1 |
1 |
0 |
0 |
0 |
0 |
r04 |
1 |
0 |
0 |
0 |
1 |
0 |
r13 |
0 |
1 |
0 |
1 |
0 |
0 |
r14 |
0 |
1 |
0 |
0 |
1 |
0 |
r15 |
0 |
1 |
0 |
0 |
0 |
1 |
r35 |
0 |
0 |
0 |
1 |
0 |
1 |
r44 |
0 |
0 |
0 |
0 |
1 |
0 |
r45 |
0 |
0 |
0 |
0 |
1 |
1 |
|
2 |
4 |
0 |
2 |
6 |
3 |
Элементы матрицы инциденции для ориентированного графа определяют по другой формуле:
+1, если ri,j исходит из вершины xi;
q(i. j)= 0, если ri,j не инцидентна вершинам xi и xj;
-1, если дуга ri,j заходит в вершину xj.
В таблице 3.4 приведена матрица инциденции для ориентированного графа, представленного на рис. 3.2.
-
Таблица 3.4.
q
x0
x1
x2
x3
x4
x5
r01
+1
-1
0
0
0
0
r04
+1
0
0
0
-1
0
r13
0
+1
0
-1
0
0
r14
0
+1
0
0
-1
0
r15
0
+1
0
0
0
-1
r35
0
0
0
+1
0
-1
r44
0
0
0
0
1
0
r45
0
0
0
0
+1
-1
+
2
3
0
1
1
0
-
0
1
0
1
2
3
В каждой строке сумма “+1” и “-1” равна нулю, т. к. “+1” представляет вершину – исток, а “-1” вершину – сток.
При задании ориентированного графа с петлями рекомендуется расщеплять вершину с петлей на две вершины: вершину-исток и вершину-сток,
В каждом столбце матрицы число “+1” равно полустепени исхода вершины xi, т.е. i +, а число “-1” равно полустепени захода вершины xi , т.е. i -.
Матрица смежности. Поскольку смежность есть отношение между элементами одного множества, то матрица смежности ||ri,j|| есть квадратная матрица, число строк и столбцов которой равно мощности множества |X|=n.
Элементы матрицы смежности определяются соотношением
1, если xi смежна xj;
r(i, j) =
0, в противном случае.
В таблице 3.5 представлена матрица смежности для неориентированного графа (см. рис. 3.2а).
Петля у вершины x4 формирует “1” на диагонали матрицы (xi, xj). В таблице можно выделить дополнительную строку или столбец для хранения информации о степени каждой вершины графа.
.
-
Таблица 3.5
r
x0
x1
x2
x3
x4
x5
i
x0
0
1
0
0
1
0
2
x1
1
0
0
1
1
1
4
x2
0
0
0
0
0
0
0
x3
0
1
0
0
0
1
2
x4
1
1
0
0
1
1
4
x5
0
1
0
1
1
0
3
i
2
4
0
2
4
3
В таблице 3.6 представлена матрица смежности для ориентированного графа (см. рис. 3.2b), но при условии, что строки заданы вершинами-истоками, а столбцы - вершинами-стоками.
.
-
Таблица 3.6
r
x0
x1
x2
x3
x4
x5
i+
x0
0
1
0
0
1
0
3
x1
0
0
0
1
1
1
3
x2
0
0
0
0
0
0
0
x3
0
0
0
0
0
1
1
x4
0
0
0
0
1
1
2
x5
0
0
0
0
0
0
0
i-
0
1
0
0
2
3
Поэтому итоговый столбец таблицы - i+ показывает полустепени вершин-истоков, а итоговая строка - I- - полустепени вершин-стоков.
По матрицам смежности можно сделать следующие выводы:
каждый ненулевой элемент главной диагонали соответствует петле на графе;
матрица смежности для неориентированного графа симметрична относительно главной диагонали;
матрица смежности для ориентированного графа несимметрична относительно главной диагонали;
столбец ориентированного графа, все элементы которого имеют значение “0”, соответствует вершине-истоку всего графа (см. таблицу 3.6);
строка ориентированного графа, все элементы которой имеют значение “0”, соответствует вершине-стоку всего графа (см. таблицу 3.6).
Матрица весов. Матрица весов вершинно-взвешенного графа есть матрица-столбец, число строк которой равно числу вершин n, а позициями – значение веса вершины:
.
Матрица весов реберно-взвешенного графа есть квадратная матрица, число строк и столбцов которой равно числу вершин графа. Позиции матрицы весов (xi, xj) при ij определяются соотношением:
0, если i=j;
L(i, j) = li,j, если вершина xi смежна вершине xj и вес ребра li,j;
, если вершина xi несмежна вершине xj.
В таблице 3.7 дана матрица весов для графа на рис. 3.11а).
-
Таблица 3.7
L
x1
x2
x3
x4
x5
x6
x1
0
2
4
x2
2
0
8
5
x3
8
0
8
5
x4
4
8
0
x5
5
0
4
x6
5
4
0
Матрица достижимости. Поскольку h(xi) есть множество вершин, которые смежны вершине xi, или “окрестность” вершины xi, или достижимы из xi за “один шаг”, то отображение h(h(xi))=h2(xi) есть вершины графа, достижимые из xi за “два шага” через вершины, сформированные на “первом шаге”. Отображение h(h(h(xi)))=h3(xi) есть вершины, достижимые из вершины xi за ”три шага” через вершины, сформированные на втором шаге. Так как любая вершина связного графа должна быть достижима за pn “шагов”, то множество вершин достижимых из вершины xi за это число “шагов” может быть представлено в виде:
qp(xi )=Ih(xi) h2(xi) ..hp(xi),
где I –диагональ матрицы.
Для построения матрицы достижимости удобно использовать матрицу смежности, т.е.
||qp||=I||r||||r2||||r3||..||rp|||.
Для возведения в степень матрицы смежности используют правило умножения булевых матриц:
ri,j2=k=1n (ri,k rk,j),
ri,j3=k=1n (ri,k rk,j2) и так далее.
Пример: в таблице r дана матрица смежности неориентированного графа. Определить достижимость каждой вершины графа.
Окрестностью вершины x1 является {x2, x4}, x2 – {x1, x3}, x3 – {x2, x4}, x4 – {x1, x3}.
-
r
x1
x2
x3
x4
q
x1
x2
x3
x4
x1
0
1
0
1
x1
1
1
0
1
x2
1
0
1
0
x2
1
1
1
0
x3
0
1
0
1
x3
0
1
1
1
x4
1
0
1
0
x4
1
0
1
1
r2
x1
x2
x3
x4
q2
x1
x2
x3
x4
1
1
0
1
0
x1
1
1
1
1
x2
0
1
0
1
x2
1
1
1
1
x3
1
0
1
0
x3
1
1
1
1
x4
0
1
0
1
x4
1
1
1
1
Ответ: любая вершина графа достижима не более, чем за “два шага”.
Пример: дана матрица смежности ориентированного графа. Определить достижимость каждой вершины графа.
-
r
x1
x2
x3
x4
q
x1
x2
x3
x4
x1
0
1
0
1
x1
1
1
0
1
x2
0
0
1
0
x2
0
1
1
0
x3
0
0
0
1
x3
0
0
1
1
x4
1
0
0
0
x4
1
0
0
1
-
r2
x1
x2
x3
x4
q2
x1
x2
x3
x4
1
1
0
1
0
x1
1
1
1
1
x2
0
0
0
1
x2
0
1
1
1
x3
1
0
0
0
x3
1
0
1
1
x4
0
1
0
1
x4
1
1
0
1
-
r3
x1
x2
x3
x4
q3
x1
x2
x3
x4
x1
0
1
0
1
x1
1
1
1
1
x2
1
0
0
0
x2
1
1
1
1
x3
0
1
0
1
x3
1
1
1
1
x4
1
0
1
0
x4
1
1
1
1
Ответ: любая вершина графа достижима не более, чем за “три шага”.
Матрица разрезов. Если можно построить множество разрезов в виде совместимых кортежей, то можно оформить матрицу разрезов b, строками которой являются индексированные разрезы bi, а столбцами – ребра графа rj, одни из концевых вершин которых принадлежат множеству X’, а другие - множеству (X\X’),. Элементы матрицы разрезов вычисляют по формуле:
1, если j-е ребро участвует в i-м разрезе,
b(i, j)=
0, в противном случае.
Например, если x1X’, а x4X\X’ (см. рис. 3.6), то можно оформить не менее 18 разрезов, разъединяющих эти вершины. Ниже в таблице 3.8 приведена матрица только для пяти разрезов.
-
Таблица 3.8
b
r1
r2
r3
r4
r5
r6
r7
r8
r9
r10
r11
b1
1
0
0
0
0
0
0
1
0
1
0
b2
1
0
0
0
0
0
1
0
1
1
0
b3
1
0
0
0
0
1
0
0
0
0
1
b4
0
1
0
0
0
0
1
0
0
0
1
b5
0
0
1
1
0
0
0
1
1
0
1
Матрица циклов. Если в графе существует несколько циклов, т их описание удобно сосредоточить в матрице циклов с, каждая строка которой есть индексированный цикл ci, а каждый столбец – ребро, включаемое в цикл.
Элементы матрицы циклов вычисляют по формуле:
1, если j-е ребро участвует в i-м разрезе,
c(i, j)=
0, в противном случае.
Для графа, приведенного на рис. 3.10а) можно оформить не менее 18 циклов. Ниже в таблице 3.9 приведена матрица только для шести циклов этого графа.
Таблица 3.9
-
с
r1
r2
r3
r4
r5
r6
r7
r8
r9
c1
1
1
0
0
0
1
0
0
0
c2
0
1
1
1
0
0
0
0
0
c3
0
0
1
0
0
0
0
1
1
c4
1
0
1
0
0
0
1
1
0
c5
1
0
0
1
0
1
0
1
1
с6
0
0
0
1
0
1
1
1
0