- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 13.5.Изоморфизм графов
Это отношение эквивалентности на множестве графов.
Определение: Изоморфным отображениемодного неориентированного графа на другой называется взаимооднозначное отображение вершин и дуг или рёбер одного графа – соответственно на вершины и дуги или рёбра другого графа, при котором сохраняется отношение инцидентности.
Пример 13.4:
Графы – неизоморфны, а Графы– изоморфны.
Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и ребер конечно. Подобным же образом определяется изоморфизм ориентированных графов. Установление отношения изоморфности является важной проблемой теории графов. Для некоторых классов графов существуют эффективные алгоритмы, позволяющие установить изоморфизм.
Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
Один из первых вопросов, возникающих при изучении графов, это вопрос о существовании путей между заданными или всеми парами вершин. Ответом на этот вопрос – введённое выше отношение достижимости на вершинах графа вершинадостижима из вершины, еслиили весть путь изв. Иначе говоря, отношение достижимости является рефлексивным и транзитивным замыканием отношения. Для неориентированных графов это отношение также симметрично и, следовательно, является отношением эквивалентности на множестве вершин. В неориентированном графе классы эквивалентности по отношению достижимости называются связными компонентами. Для ориентированных графов достижимость, вообще говоря, не должна быть симметричным отношением. Симметричной является взаимная достижимость.
Определение:Вершиныиориентированного графаназываютсявзаимно достижимыми, если весть путь изви путь изв.
Ясно, что отношение взаимной достижимости является рефлексивным, симметричным и транзитивным и, следовательно, эквивалентностью на множестве вершин графа. Классы эквивалентности по отношению взаимной достижимости называются компонентами сильной связности или двусвязными компонентами графа.
Рассмотрим вначале вопрос о построении отношения достижимости. Определим для каждого графа его граф достижимости (называемый иногда также графом транзитивного замыкания), рёбра которого соответствуют путям исходного графа.
Определение:Пусть– ориентированный граф.Граф достижимостидляимеет тоже множество вершини следующее множество рёберв графевершинадостижима из вершины.
Пример 14.1:Рассмотрим граф.
Тогда можно проверить, что граф достижимости длявыглядит так (новые рёбра – петли для каждой из вершин не показаны):
Каким образом по графу можно построить граф? Один способ заключается в том, чтобы для каждой вершины графаопределить множество достижимых из неё вершин, последовательно добавляя в него вершины, достижимые из неё путями длины 0, 1, 2 и т.д.
Мы рассмотрим другой способ, основанный на использовании матрицы смежности графа и булевых операций.
Ниже для сохранения сходства с обычными операциями над матрицами мы будем использовать «арифметические» обозначения для булевых операций: через «+» будем обозначать дизъюнкцию , а через «*» конъюнкцию.
Обозначим через единичную матрицу размера, а- матрицу смежности заданного графа. Положим. Пусть,,…,. Наша процедура построенияоснована на следующем утверждении.
Лемма.Пусть Тогда
Доказательствопроведём индукцией по.
Базис. При иутверждение справедливо по определению.
Индукционный шаг. Пусть лемма справедлива для . Покажем, что она остаётся справедливой и для. По определениюимеем:
Предположим, что в графе извимеется путь длины. Рассмотрим кратчайший из таких путей. Если его длина, то по предположению индукции. Кроме того,. Поэтомуи. Если длина кратчайшего пути извравна, то пусть- его предпоследняя вершина. Тогда извимеется путь длиныи по предположению индукции. Так как, то. Поэтомуи.
Обратно, если , то хотя бы для одногослагаемоев сумме равно 1. Если это, тои по индуктивному предположению вимеется путь извдлины. Если же, тои. Это означает, что вимеетсяпутьизвдлиныиребро. Объединив их, получаемпутьизвдлины.
Из леммы непосредственно получаем
Следствие 1.Пусть – ориентированный граф с вершинами, а – его граф достижимости. Тогда .
Доказательство:Из леммы следует, что, если вимеется путь изв, то в нём имеется и простой путь извдлины. А по лемме все такие пути представлены в матрице.
Таким образом, процедура построения матрицы смежности графа достижимости длясводится к возведению матрицыв степень. Сделаем несколько замечаний, позволяющих упростить эту процедуру.
Для возведения матрицы в произвольную степеньдостаточно выполнитьвозведений в квадрат:
где – это наименьшее число такое, что.
Так как на диагонали в матрице стоят единицы, то для любыхвсе единицы матрицысохраняются в матрице, в частности, и в матрице.
Если при вычислении элемента матрицыпо стандартной формуле
обнаруживается такое , чтои, то и вся сумма. Поэтому остальные слагаемые можно не рассматривать.
Пример 14.2:Рассмотрим в качестве примера вычисление матрицы графа достижимостидля графапримера 14.1. В этом случае
Так как у имеется 6 вершин, то. Вычислим эту матрицу:
и . Таким образом,
Как видим, эта матрица действительно задаёт граф , представленный в примере 14.1.