- •Введение
- •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
Матрица м данного графа имеет вид
a b c d e f
b c a c c a
- e d f d b
- - - - - c
В качестве отправной вершины рассмотрим а. Множество S формируется следующим образом:
Но-мер |
Множество S |
Комментарии |
1 |
a |
Добавляем первую возможную вершину в столбце а (т.е. вершину b). |
2 |
а,b |
Добавляем первую возможную вершину в столбце b (т.е. вершину с) |
3 |
a,b,c |
Первая вершина а в столбце с не является возможной (аS), добавляем следующую вершину в столбце (т.е. вершину d). |
4 |
a,b,c,d |
Добавляем вершину f. |
5 |
a,b,c,d,f |
В столбце f нет возможной вершины. Возвращение. |
6 |
a,b,c,d |
В столбце d не существует возможной вершины, следующей за f. Возвращение. |
7 |
a,b,c |
Аналогично предыдущему. Возвращение. |
8 |
а,b |
Добавляем вершину е. |
9 |
a,b,e |
Добавляем вершину с. |
10 |
a,b,e,c |
Добавляем вершину d. |
11 |
a,b,e,c,d |
Добавляем вершину f. |
12 |
a,b,e,c,d,f |
Гамильтонов путь. Дуга (f,a) дает гамильтонов контур. Возвращение. |
13 |
a,b,e,c,d |
Возвращение. |
14 |
a,b,e,c |
Возвращение. |
15 |
a,b,e |
Добавляем вершину d. |
16 |
a,b,e,d |
Добавляем вершину f. |
17 |
a,b,e,d,f |
Добавляем вершину c. |
18 |
a,b,e,d,f,c |
Гамильтонов путь. Путь замыкается дугой (c,a). Возвращение. |
19 |
a,b,e,d,f |
Возвращение. |
20 |
a,b,e,d |
Возвращение. |
21 |
a,b,e |
Возвращение. |
22 |
а,b |
Возвращение. |
23 |
a |
Возвращение. |
24 |
|
Конец поиска. |
В результате работы алгоритма определены гамильтоновы пути 1=[a,b,e,c,d,f], 2=[a,b,e,d,f,c] и контуры [a,b,e,c,d,f,a], [a,b,e,d,f,c,a].
4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
Замечание. «Внутреннее произведение вершин» пути [x1,…,xk] определяется как формальное выражение вида x2x3…xk-1, не содержащее две концевые вершины x1 и xk.
Шаг 1. G – данный орграф на n вершинах; А – матрица смежности с нулевыми элементами на диагонали; – модифицированная матрица смежности, в которой bij=bij)=xj, если существует дуга из xi в xj и 0 в противном случае. Положить k=1, k=A.
Шаг 2. Положить k=k+1. Найти P k=BP k-1.
Шаг 3. Если k=n, то диагональные элементы матрицы P n дают внутренние произведения вершин, которые соответствуют гамильтоновым контурам графа. Получить гамильтоновы контуры. Останов. Иначе перейти к шагу 4.
Шаг 4. Сделать все пути простыми, обнулив в матрице Pk все диагональные элементы, которые содержат сомножителями вершины, соответствующие данной строке. Перейти к шагу 5.
Шаг 5. Если k=n-1, то элементы матрицы Pk дают внутренние произведения вершин, которые соответствуют гамильтоновым путям графа G. Получить гамильтоновы пути. Перейти к шагу 2.
П ример. Рассмотрим граф, изображенный на рис. 4.44.
Рис. 4.44
Матрица смежности А этого графа имеет вид
a b c d e
a 0 1 0 1 0
A = b 0 0 0 1 1
c 0 1 0 0 1
d 0 0 1 0 0
e 1 0 1 0 0
а модифицированная матрица смежности В выглядит следующим образом:
a b c d e
a 0 b 0 d 0
b 0 0 0 d e
B = c 0 b 0 0 e
d 0 0 c 0 0
e a 0 c 0 0
Положим P1=A. Матрица P2’=B1 получается равной
a b c d e
a 0 0 d b b
b e 0 d+e 0 0
P2’ = c e 0 e b b
d 0 c 0 0 c
e 0 a+c 0 a c
Матрица P2 почти такая же, как P2’, только подчеркнутые элементы в P2’ надо заменить нулями. Матрица P3’=BP2 равна
a b c d e
a be dc bd+be 0 dc
b 0 dc+ea+ec 0 ea dc
P3’= c be ea+ec bd+be ea 0
d ce 0 0 cb cb
e ce 0 ad ab+cb ab+cb
Матрица Р3 получается из P3’ после замены подчеркнутых элементов нулями. Матрица Р4’=BP3
a b c d e
a dce 0 0 bea bdc+dcb
b dce 0 ead eab+ecb dcb
P4’= c 0 0 ead bea+eab+ecb bdc
d cbe cea 0 cea 0
e cbe adc+cea abd+abe cea adc
Гамильтоновы пути можно определить по матрице Р4, которая имеет вид
a b c d e
a 0 0 0 0 bdc+cdb
b dce 0 ead 0 0
P4= c 0 0 0 bea+eab 0
d cbe cea 0 0 0
e 0 adc abd 0 0
Гамильтоновы пути abdce и adcbe, соответствующие элементу (1,5) матрицы Р4 дают гамильтоновы контуры abdcea и adcbea, если добавить замыкающую дугу (е,а). Все другие гамильтоновы пути в Р4 приводят к тем же самым контурам, и потому в графе G есть только два таких контура.