- •Содержание
- •1. Теория множеств
- •1.1. Основные определения
- •1.2. Операции над множествами
- •1.3. Системы множеств
- •1.4. Декартово произведение множеств
- •1.5. Бинарные отношения
- •1.5.1. Определение бинарного отношения
- •1.5.2. Способы задания бинарного отношения
- •1.5.3. Свойства бинарных отношений
- •1.5.4. Отношения эквивалентности
- •1.7. Контрольные вопросы и упражнения
- •2. Математическая логика
- •2.1.Алгебра логики
- •2.1.1. Логические высказывания
- •2.1.2. Основные логические операции
- •2.1.3. Формулы алгебры логики
- •2.1.4. Логические функции
- •Функции одной переменной
- •Функции двух переменных
- •2.2. Булева алгебра
- •2.2.1. Булевы функции и операции
- •Свойства булевых операций
- •2.2.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы
- •2.3. Полные системы логических функций
- •Класс функций, сохраняющих ноль
- •Класс функций, сохраняющих единицу
- •Класс самодвойственных функций
- •Класс монотонных функций
- •Класс линейных функций
- •2.4. Задача минимизации днф
- •2.4.1. Основные определения
- •2.4.2. Этапы минимизации днф
- •2.4.3. Минимизация днф методом Квайна
- •2.5. Синтез логических схем
- •2.6. Контрольные вопросы и упражнения
- •3. Теория графов
- •3.1. Основные определения
- •3.1.1. Общие понятия
- •3.1.2. Ориентированные и неориентированные графы
- •3.1.3. Маршруты в графах
- •3.1.4. Частичные графы и подграфы
- •3.1.5. Связность в графах
- •3.1.6. Изоморфизм. Плоские графы
- •3.2. Отношения на множествах и графы
- •3.3. Матрицы смежности и инциденций графа
- •3.4. Операции над графами
- •3.4.1. Сумма графов
- •3.4.2. Пересечение графов
- •3.5. Степени графов
- •3.5.1. Степени неориентированных графов
- •3.5.2. Степени ориентированных графов
- •3.6. Характеристики графов
- •3.6.1. Характеристики расстояний в графах
- •3.6.2. Характеристические числа графов
- •3.7. Циклы и разрезы графа
- •3.7.1. Остов и кодерево
- •3.7.2 . Базисные циклы и разрезающие множества
- •Свойства базисных циклов и разрежающих множеств
- •3.7.3. Цикломатическая матрица и матрица разрезов
- •Составление цикломатической матрицы
- •Составление матрицы разрезов
- •3.8. Задача определения путей в графах
- •3.8.1. Определение путей в графе
- •3.8.2. Алгоритм определения кратчайших путей
- •Алгоритм Дейкстры
- •Первая итерация
- •Вторая итерация
- •Третья итерация
- •3.9. Обход графа
- •3.9.1. Эйлеровы маршруты
- •3.9.2. Гамильтоновы маршруты
- •3.10. Контрольные вопросы и упражнения
- •Список литературы
3.1.5. Связность в графах
Рассмотрим вопрос о связности в графах. Пусть G(X) – неориентированный граф. Две вершины хiиxjназываютсясвязными, если существует цепьSс концами хiиxj. ЕслиSпроходит через некоторую вершинуxkболее одного раза, то можно удалить цикл в вершинеxkиз цепиS. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.
Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности (xi~xj, хj~ хkxi~ хk).
Компонентой связностинеориентированного графаG(X) называется подграф НА(А) графаG(X) с множеством вершин АXи множеством ребер вG(X), инцидентных только вершинам из А, причем ни одна вершинаxi А не смежна с вершинами из множества Х \ А (рис. 3.12).
Рис. 3.12. Граф с двумя компонентами связности
Ориентированный граф называется сильно связным, если для любой пары вершин найдется путь, соединяющий их.
Компонентой сильной связностиориентированного графаG(X) называется подграф НА(А) графаG(Х) (подчиняющийся определению сильно связного графа) с множеством вершин АХ и множеством дуг, имеющих начало и конец в А, причем ни одна из вершин хiА и хjX\ А не смежны между собой (рис. 3.13).
Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности
Очевидно, что ориентированный граф G(X) сильно связан тогда и только тогда, когда он имеет одну компоненту связности.
На практике широко используются такие виды графов, как деревья и прадеревья.
Деревомназывается конечный связный неориентированный граф, состоящий, по крайней мере, из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер (рис. 3.14).
Ветвямидерева называются ребра графа, входящие в дерево.Хордами дереваназываются ребра, входящие в граф, дополнительный к данному дереву.Лагранжевым деревомназывается дерево, все ветви которого имеют общую вершину.
Рис. 3.14. Дерево
Лесом называется несвязный граф, каждая компонента связности которого является деревом.
Прадеревомназывается ориентированный графG(X) с корнем х0 X, если в каждую вершину хiх0(хiX) заходит ровно одна дуга, а в корень х0не заходит ни одна дуга. Прадерево не содержит контуров (рис.3.15).
Рис. 3.15. Прадерево
3.1.6. Изоморфизм. Плоские графы
В изображении графа имеется относительно большая свобода в размещении вершин и в выборе формы соединяющих их ребер. Поэтому один и тот же граф может быть представлен по-разному (рис. 3.16).
Р
G1(X1)
G2(X2)
Графы G1(X1) иG2(X2) называютсяизоморфными, если между множествами их вершин существует взаимно однозначное соответствие, сохраняющее смежность вершин. Иначе, если вершины являются смежными (соединены ребрами) в одном из графов, то соответствующие им вершины в другом графе также являются смежными. Если ребра графов ориентированы, то их направление в изоморфных графах также должно соответствовать друг другу.
ГрафG(X) называется плоским, если он может быть изображен на плоскости так, что все пересечения его ребер являются вершинами графаG(X) (рис. 3.17).
а) б)
Рис. 3.17. Примеры плоского (а) и неплоского (б) графов