- •Теория множеств.
- •Свойства подмножеств.
- •Операции над множествами.
- •Алгебра теории множеств.
- •Решение уравнений алгебры множеств.
- •Кортеж.
- •Проекция множества.
- •График и свойства графика
- •С войства графиков.
- •Прямое (декартовое) произведение множество.
- •Соответствия.
- •Отношения.
- •О перации над отношениями.
- •Основные свойства отношений.
- •Решетки. Диаграммы Хассе.
- •Математическая логика Высказывания и операции над высказываниями.
- •Операции над высказываниями.
- •Формулы математической логики.
- •Формулы равносильности.
- •Различные формы представления высказываний
- •Выполнимость формулы алгебры логики
- •Выполнимые.
- •Применение математической логики.
- •Минимизация сложных высказываний.
- •Метод Квайна.
- •Метод минимизирующих карт.
- •Метод минимизации с помощью карт Вейча.
- •Булевые функции и их свойства.
- •Функциональная полнота. Теорема Поста.
- •Логика предикат.
- •Логические операции над предикатами.
- •Квантовые операции.
- •Равносильные формулы логики предикатов.
- •Предваренная нормальная форма предиката
- •Теория графов
- •Основные понятия теории графов
- •Перечислением:
- •Множеством образов:
- •Матрицей инцидентности
- •Матрицей смежности
- •Эйлеров граф.
- •Множество внутренней устойчивости графа
- •Алгоритм Магу для определения множества внутренней устойчивости графа
- •Множество внешней устойчивости графа
- •Алгоритм Магу для определения множества внешней устойчивости.
- •Множество путей в графе
- •Алгоритм фронта волны. Поиск минимального пути в графе.
- •Алгоритм фронта волны.
- •Ярусно-параллельная форма графов
- •Деревья и леса
- •Алгоритм получения дерева из графа
- •Теория алгоритмов
- •Рекурсивная функция
- •Пусть даны функции:
- •Машина Тьюринга
- •Работа машины Тьюринга:
- •Нормальные алгоритмы Маркова
- •Теория автоматов
- •Законы функционирования автоматов.
- •Задание автоматов
- •Минимизация автоматов
- •Алгоритм минимизации автомата Мили
- •Особенности минимизации автомата Мура.
- •Минимизация частичных автоматов.
- •Переход от автомата Мили к автомату Мура
- •Переход от автомата Мура к автомату Мили
Матрицей смежности
Смежные дуги – это дуги инцидентные одной вершине.
Смежные вершины – вершины, инцидентные одной дуге.
Матрица смежности - это матрица смежных вершин.
Матрица смежности заполняется по следующему правилу: , если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях (для удобства и наглядности на практике в матрице смежности нули не проставляются).
Для графа, представленного на рис. 3.2 матрица смежности имеет вид:
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
Полустепенью захода i–той вершины называется число дуг, заходящих в данную вершину.
Полустепенью исхода i-той вершины называется число дуг, исходящих из данной вершины.
Степенью i-той вершины исхода называется сумма полустепеней захода и исхода:
(3.2)
Свойства матрицы смежности:
Сумма единиц по строке определяет полустепень исхода;
Сумма единиц по столбцу определяет полустепень захода;
Сумма единиц по строкам и по столбцам определяет степень вершин.
Основное свойство графа:
В любых графах число вершин с нечетной степенью четно.
Путем в графе называется последовательность дуг такая, что каждая следующая дуга исходит из вершины, в которую заходит предыдущая дуга.
Длиной пути называется количество пройденных дуг.
Простой путь – это такой путь, в котором дуга встречается не более одного раза.
Элементарный путь – это путь, в котором вершина встречается не более одного раза.
Контур – путь, начинающийся и заканчивающийся в одной точке.
Петля – контур длиной в одну единицу.
Графы бывают двух видов:
ориентированный граф (орграф) - это граф, состоящий из вершин и дуг.
неориентированный граф – это граф, состоящий из вершин и ребер. Ребро – это дуга, не имеющая направление.
Рис. 3.3. Неориентированный граф
В неориентированном графе путь называется цепью; контур – циклом.
Неориентированный граф также может быть задан с помощью матриц инцидентности и смежности.
Матрица инцидентности для неориентированного графа составляется по правилу:
, если i-тая вершина инцидентна j-тому ребру;
, если i-тая вершина не инцидента j-тому ребру;
, если. в i-той вершине j-тое ребро образует петлю.
Для графа, представленного на рис. 3.3, матрица инцидентности имеет вид:
-
I
II
III
IV
V
VI
VII
1
1
1
1
1
2
1
1
3
1
1
1
4
1
1
1
5
1
1
Матрица смежности для неориентированного графа составляется по правилу: , если из i-тая и j – тая вершины смежные.
Для графа, представленного на рис. 3.3, матрица смежности имеет вид:
-
1
2
3
4
5
1
1
1
1
1
1
2
1
1
3
1
1
1
4
1
1
1
5
1
1
Матрица смежности для неориентированного графа симметрична относительно главной диагонали. Степень i- той вершины равна сумме элементов по строке или по столбцу матрицы смежности.
Если в графе присутствуют как ребра, так и дуги, то он называется смешанным.
Если между двумя вершинами существует более чем 1 дуга или ребро, то такой граф называется мультиграфом.
Рис. 3.4. Смешанный мультиграф.
Граф называется связным, если между любыми двумя вершинами которого существует путь (цепь).