- •Дискретная математика
- •Воронеж 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
Матрица м данного графа имеет вид
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 есть только два таких контура.
Пример. Математическая постановка задачи нахождения оптимальной последовательности выпуска изделий.
Введем некоторые обозначения. Пусть {a1…aL} - множество всевозможных последовательностей выпуска изделия L модификаций; - количество оборудования в группе , где =1,…,N; - время, необходимое на переналадку единицы оборудования -ой группы при переходе с выпуска i-ой модификации на выпуск j-ой модификации.
Пусть G - ориентированный граф, вершины которого представляют изделия, а существование дуги (хi, хi) означает, что изделие j может следовать за изделием i без перенастройки оборудования. Тогда, если в этом графе есть гамильтонов цикл (ориентированный цикл, проходящий через каждую вершину графа), то существует последовательность выпуска изделий, не требующая перенастройки оборудования. Если не существует циклической последовательности выпуска изделий, не требующей перенастройки оборудования, то задача сводится к нахождению последовательности выпуска изделий, требующих наименьших затрат на перенастройку оборудования.
Пусть хij =1, если после изделия i-ой модификации выпускается изделие j-ой модификации; хij=0, если после изделия i-ой модификации изделие j-ой модификации не выпускается.
С так введенными переменными ставим задачу:
Минимизировать функцию
(1)
при условиях
, , . (2)
В качестве дополнительных ограничений необходимо наложить условие «петель», для устранения подконтуров в задаче
(3)
Задача (1)-(3) полностью аналогична классической задаче коммивояжера:
(4)
при условиях
, , . (5)
условие «петель»
(6)
В задаче коммивояжера (4)-(6) ищется оптимальная последовательность обхода «городов», а в задаче (1)-(3) оптимальная последовательность выпуска изделий. В задаче (4)-(6) матрица D с элементами является матрица расстояний между N «городами», этой матрице соответствует матрица В в задаче (1)-(3) с элементами , которая является матрицей времени переналадки оборудования
Таким образом, задачу оптимизации последовательности выпуска изделий можно решить методами решения задачи коммивояжера.