- •Введение
- •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.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
Шаг 1. G – данный граф. Для G построить матрицу достижимости R и матрицу контрдостижимости Q=RT. Перейти к шагу 2.
Шаг 2. Положить С=RQ, где – поэлементное умножение матриц. Перейти к шагу 3.
Шаг 3. Преобразовать матрицу С к блочно-диагональ-ному виду путем перестановки строк и столбцов. Каждая из диагональных подматриц соответствует сильной компоненте графа G. Останов.
4.8.4. Базы и антибазы
База или вершинная база В есть множество вершин графа G, из которого достижима любая вершина графа и которое является минимальным в том смысле, что не существует собственного подмножества в В, обладающего таким свойством достижимости.
Базой является такое множество вершин графа G, которое удовлетворяет следующим двум условиям:
каждая вершина графа G достижима хотя бы из одной вершины множества В;
в В нет вершины, которая достижима из другой вершины множества В.
Из этих условий получаются следующие утверждения.
1. В множестве В нет двух вершин, которые принадлежат одной и той же СК графа G.
2. В любом графе без контуров существует единственная база. Она состоит из всех таких вершин, полустепени захода которых равны 0.
Доказательства этих утверждений простые и непосредственно следуют из определений. Утверждения позволяют сформировать алгоритм нахождения баз ориентированного графа, который описывает следующая последовательность шагов.
Шаг 1. G – данный граф. Для G найти все сильные компоненты.
Шаг 2. Построить конденсацию G* графа G.
Шаг 3. Определить базу В* конденсации G*, включив в В* те вершины G*, полустепени захода которых равны 0.
Шаг 4. Построить базу В графа G из В*, взяв по одной вершине из сильных компонент, входящих в В*. Останов.
Пример. Для графа G, приведенного на рис. 4.25, конденсация показана на рис. 4.26. Базой графа G* является множества , поскольку и единственные вершины в графе G* с полустепенями захода, равными 0. Базами графа G являются , и .
Понятие, двойственное понятию базы есть антибаза. Антибаза графа G есть такое минимально возможное множестве вершин, что какова бы ни была вершина графа G, из нее достижима некоторая вершина в . Свойства антибаз аналогичны свойствам баз, надо только «прямые» понятия заменить на двойственные. Опишем алгоритм нахождения антибаз графа.
Шаг 1. G данный граф. Для G найти все сильные компоненты.
Шаг 2. Построить конденсацию G* графа G.
Шаг 3. Определить антибазу В* конденсации G*, включив вВ* те вершины G*, полустепени исхода которых равны 0.
Шаг 4. Построить антибазу графа G из В*, взяв по одной вершине из сильных компонент, входящих вВ*. Останов.
В примере с графом G, изображенным на рис. 4.25, конденсация графа G* (рис. 4.26) содержит только одну вершину с полустепенью исхода, равной 0. Таким образом, антибаза графа G* , а антибазами графа G являются множества , и .
Понятия связности и достижимости применяют к исследованию структуры организаций. Например, если граф представляет структуру руководства или влияний некоторой организации, то элементы каждой сильной компоненты имеют равную власть и равное влияние друг на друга. Базу графа можно интерпретировать как «коалицию», включающую наименьшее число лиц, обладающих властью над каждым членом организации.