- •Дискретная математика
- •Воронеж 2012
- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3. Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Алгебра логики
- •5.1. Операции над высказываниями
- •5.2. Правила записи сложных формул
- •5.3. Таблицы истинности
- •5.4. Равносильность формул
- •5.5. Дизъюнктивные и конъюнктивные нормальные формы
- •5.5.1. Аналитический способ приведения к сднф
- •5.5.2. Табличный способ приведения к сднф
- •5.5.3. Табличный способ приведения к скнф
- •5.7. Геометрическое представление булевых функций
- •5.7.1. Геометрический метод минимизации булевой функции
- •Задачи и упражнения
- •6. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
4.8.2. Матрицы достижимостей
и контрдостижимостей
М атрица достижимостей графа G=(X,V) , определяется следующим образом:
Множество вершин R(xi) графа G, достижимых из заданной вершины xi, состоит из таких элементов xj, для которых (i, j)-й элемент в матрице достижимостей равен 1. Считают, что каждая вершина достижима из себя самой с помощью пути длины 0, поэтому все диагональные элементы в матрице R равны 1.
Поскольку Г(xi) является множеством таких вершин xj, которые достижимы из xi c использованием путей длины 1 (т.е. Г(xi) – такое множество вершин, для которых в графе существуют дуги (xi, xj)) и поскольку Г(xj) является множеством вершин, достижимых из xj с помощью путей длины 1, то множество Г(Г(xi))=Г2(xi) состоит из вершин, достижимых из xi c использованием путей длины 2. Аналогично Гp(xi) является множеством вершин, которые достижимы из xi с помощью путей длины р.
Так как любая вершина графа G, которая достижима из xi, должна быть достижима с использованием пути (или путей) длины 0, или 1, или 2, ..., или р (с некоторым конечным р≤n), то множество вершин, достижимых из xi , можно представить в виде
R(xi) = { xi }ÈГ(xi)È Г2 (xi )È…È Гp (xi ) (4.3)
Таким образом, множество R(xi) может быть получено последовательным выполнением (слева направо) операций объединения в соотношении (4.3), до тех пор, пока «текущее» множество не перестанет изменяться при очередной операции объединения. С этого момента последующие операции не будут давать новых элементов множеству и, таким образом, будет получено, достижимое множество R(xi). Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число р меньше числа вершин в графе.
Матрицу достижимостей можно построить так. Находим достижимые множества R(xi) для всех вершин xiÎХ способом, приведенным выше. Положим rij=1, если xjÎR(xi), и rij=0 в противном случае. Полученная таким образом матрица R является матрицей достижимостей.
М атрица контрдостижимостей (матрица обратных достижимостей) , определяется следующим образом:
Контрдостижимым множеством Q(xi) графа G является множество таких вершин, что из любой вершины этого множества можно достигнуть вершину xi. Аналогично построению достижимого множества R(xi) на основе соотношения (4.3) можно «сформировать» множество Q(xi), используя следующее выражение:
Q(xi) = {xi} È Г-1 (xi) È Г-2 (xi) È … È Г-р (xi), (4.4) где Г-2 (xi) = Г-1 (Г-1 (xi)) и т. д.
Операции, выполняются слева направо до тех пор, пока очередная операция объединения не перестанет изменять «текущее» множество Q(xi).
Из определений очевидно, что столбец xi матрицы Q (в котором qij=1, если xiÎQ(xi), и qij=0 в противном случае) совпадает со строкой xi матрицы R, т. е. Q=RT, где RT – матрица, транспонированная к матрице достижимостей R.
Пример. Найти матрицы достижимостей и обратных достижимостей для графа G, приведенного на рис. 4.24.
Рис.4.24
Матрица смежности графа G имеет вид
Множества достижимостей находятся с помощью соотношений
R(x1)={x1} È {x2,x5} È {x2,x4,x5} È {x2,x4,x5} = {x1,x2,x4,x5},
R(x2)= {x2} È {x2,x4} È {x2,x4,x5} È {x2,x4,x5} = {x2,x4,x5},
R(х3)= {x3} È {x4} È {x5} È {x5} = {x3,x4,x5},
R(х4)= {x4} È {x5} È {x5} = {x4,x5},
R(х5)= {x5} È {x5} = {x5},
R(х6)= {x6} È {x3,x7} È {x4Èx6} È {x3,x5,x7} È {x4,x5,x6}=
= {x3,x4,x5,x6,x7},
R(х7)= {x7} È {x4,x6} È {x3,x5,x7} È {x4,x5,x6}=
= {x3,x4,x5,x6,x7}.
Следовательно, матрица достижимостей имеет вид
м атрица обратных достижимостей такова:
Так как R(xi) является множеством вершин, достижимых из xi, а Q(xj) – множеством вершин, из которых можно достигнуть xj, то – множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от xi к xj. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин xi и xj. Все остальные вершины называются несущественными или избыточными, поскольку их удаление не влияет на пути от xi к xj .
Матрицы достижимостей и обратных достижимостей являются полными в том смысле, что на длины путей от xi к xj не накладывались никакие ограничения. С другой стороны, можно определить матрицы ограниченных достижимостей и контрдостижимостей – надо потребовать, чтобы длины путей не превышали некоторого заданного числа. Эти ограниченные матрицы тоже могут быть построены с помощью соотношений (4.3) и (4.4) – надо действовать точно так, как раньше, при нахождении «неограниченных» матриц, но только теперь р будет верхней границей длины допустимых путей.
Для неориентированного графа множество достижимости позволяет проверить граф на связность. Опишем алгоритм проверки связности неорграфа.
Шаг 1. G =(X,V) – данный неорграф. Для произвольной вершины хiХ найти множество R(xi). Перейти к шагу 2.
Шаг 2. Если R(xi)=X, то граф является связным, иначе граф не является связным. Выдать соответствующее сообщение. Останов.