Similar presentations:
Теория и методы дискретных вычислений
1.
ТЕОРИЯ И МЕТОДЫ ДИСКРЕТНЫХВЫЧИСЛЕНИЙ
Лектор –
доктор технических наук, профессор
Князьков Владимир Сергеевич
Кафедра ЭВМ
Вятский государственный университет
1
2. А. Основная литература
Волченская Т.В., Князьков В.С. Компьютерная математика: ч.2.Теория графов: Учеб. пособие. - 2007. – 124 с.-//www.intuit.ru
Харари Ф. Теория графов: учебник для вузов / Ф. Харари. – М.:
УРСС, 2006.
Иванов Б.Н. Дискретная математика. Алгоритмы и программы.
Расширенный курс. – М: Известия, 2011. – 512 с.
http://www.intuit.ru/studies/courses/1033/241/info
1.
Электронные лекции
2.
Примеры
3.
Тесты – в итоге СЕРТИФИКАТ ИНТУИТ
2
3. Б. Дополнительная литература
1.Белоусов А. И., Ткачев С. Б. Дискретная математика. – М.: Изд-во МГТУ
им Н.Э. Баумана, 2001. – 744 с.
2.
Оре О. Графы и их применение: Пер. с англ. - Изд.3-е стереотипное. –
М.: КомКнига, 2006.
3.
Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В.
П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС,
2003. — 296 с.
4.
Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика:
графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с.
5.
5. Кормен,Томас Х., Лейзерсон, и др. Алгоритмы: построение и анализ, 2е издание. Пер. с англ. — М.:Изд. дом "Вильямс", 2010. — 1296 с.:
6.
6. Дискретная математика, Асеев Г.Г.
7.
7. Комбинаторика и теория графов, Носов В.А.
8.
8. Дискретная математика, Асанов М.О., Графы, Матроиды, Алгоритмы
3
4. 1. Введение и области применения теории графов 2. Способы представления графов 3. Основные операции на графах
45. Введение
В последние годы особую важность приобрели те разделыматематики, которые имеют отношение к развитию
цифровых устройств, цифровой связи и цифровых
вычислительных машин. Базой для преподавания этих
дисциплин наряду с классическими методами анализа
непрерывных
физических
моделей
стали
алгебраические, логические и комбинаторные методы
исследования
различных
моделей
дискретной
математики.
Значительно возросла популярность теории графов - ветви
дискретной математики. Графы встречаются во многих
областях под разными названиями: “структуры” в
гражданском
строительстве,”сети”
в
электронике,
”социограммы”
в
социологии
и
экономике,
“молекулярные структуры” в химии,”дорожные карты”,
электрические или газовые распределительные сети и
т.д.
5
6.
Области применения дискретных моделейКомбинаторные вычисления находят широкое
применение в различных областях :
Производство РЭА и ВТ
• оптимальное размещение элементов
и трассировка;
разбиение схемы на подсхемы для
реализации блоками и т.д.
6
7. Области применения дискретных моделей
78.
Области применения дискретных моделей2. Строительство
-Как построить транспортную сеть в регионе, чтобы
минимизировать затраты на строительство и оптимизировать
транспортные перевозки.
- Как соединить мостами острова в пойме большой реки,
минимизируя затраты и учитывая параметры сейсмостойкости и
прочности.
-Сколько вариантов прокладки трубопроводов между
заданными пунктами?
8
9.
На рис. изображена схема путей, связывающих эти города.Различные варианты путешествий отличаются друг от
друга порядком посещения городов В, С, и .D. Существует
шесть вариантов путешествия. В таблице указаны
варианты и длин каждого пути:
Путь
Длина пути
Путь
Длина пути
ABCDA
1555
ACDBA
1300
ABDCA
1300
ADBCA
1450
ACBDA
1450
ADCBA
1550
9
10.
1011.
1112. Области применения дискретных моделей
1213. Области применения дискретных моделей
-при исследовании так называемой проблемыоптимизации, возникающей при конструировании
больших систем как технических, так и программных,
например, таких как компиляторы;
-в области проектирования для построения
эффективных алгоритмов и анализа их сложности.;
-при разработке алгоритмов конструкторского
проектирования схем;
-В психологии при анализе совместимости;
-В системах управления…
13
14. Области применения дискретных моделей
1415.
Графыи способы их представления
15
16. Основные определения
Формальное определение графа может быть дано следующимобразом: графом называется двойка вида
G = (X, A),
где X={xi},i=1,2,...,n - множество вершин
графа,
A={ai},i=1,2, ... ,m –множество дуг или ребер графа.
Граф задается
или вершин
множеством
точек
х1,х2, ...,хn
и множеством линий -дуг или ребер
a1,a2,...,am, ,
соединяющих между собой все или часть
точек.
x
1
x
4
x
2
x
3
16
17. Графы могут быть ориентированными, неориентированными и смешанными
ОрграфГрафы могут быть ориентированными,
неориентированными и смешанными
x2
Если ребра ориентированы, что обычно
показывается стрелкой, то они
называются дугами, и граф с такими
ребрами
называется x
ориентированным графом или 1
орграфом
a1
a2
a3
a4
x3
a5
a6
x4
17
18. Неориентированный граф
Если ребра не имеют ориентации, то граф называетсянеориентированным
a2
x1
x2
a3
a1
a4
x3
a6
x4
a5
x5
18
19. Смешанный граф
Граф, в котором присутствуют и ребра, и дуги называетсясмешанным
x2
a2
a1
a3
x1
a4
x3
a5
x5
a6
a7
x4
19
20. Дубликат или неориентированный двойник
В случае когда мы хотимпренебречь
направленностью дуг, то
неориентированный
граф, соответствующий
G, будет обозначаться
G
и
называться
неориентированным
дубликатом
или
неориентированным
двойником
a1
x2
a3
a2
a4
x1
x3
a5
a6
x4
x2
x3
x1
x4
20
21. Инцидентность вершин и дуг
Дуга aiможет
быть
представлена
упорядоченной
парой вершин (xn, xk), состоящей
из начальной xn и конечной xk
вершин.
Например, дуга a1 задается
парой вершин (x2, x1).
Если xn, xk — концевые
вершины дуги ai, то говорят,
что
вершины
xn
и
xk
инцидентны дуге ai
или
дуга ai инцидентна вершинам
xn и xk.
x2
a1
a3
a2
a4
x3
x1
a5
a6
x4
21
22. Петля
Дуга, у которой начальная и конечная вершинысовпадают, называется петлей.
В графе G3 дуга а7 является петлей.
x2
a2
a1
a3
x1
a4
x3
a5
x5
a6
x4
a7
22
23. Характеристики вершин
Полустепеньюисхода вершины xi
— d0(xi) называется
количество
дуг,
исходящих
из
этой
вершины.
x2
a1
x1
a3
a2
a4
x3
a5
Например для орграфа
G1(рис.2,а)
характеристики
полустепеней
исхода
следующие:
d0(x1)=1,
d0(x2)=2,
d0(x3)=2, d0(x4)=1.
a6
x4
Рис. 2,а
23
24. Характеристики вершин
x2Полустепенью
захода
вершины
xi — dt(xi)
называется
количество
дуг, входящих в эту
вершину.
a1
a3
a2
a4
x3
x1
a5
Например для орграфа G1:
dt(x1)=2,
dt(x2)=1, dt(x3)=2,
dt(x4)=1.
a6
x4
24
25. Характеристики вершин
Очевидно, что сумма полустепеней исхода всех вершинграфа,
а также сумма полустепеней захода всех вершин графа
равна общему числу дуг графа, т.е.
d x d x
n
i 1
n
0
i
i 1
t
i
m
где n-число вершин графа, m-число дуг.
25
26. Характеристики вершин
Для неориентированного графа – степень вершины d (xi)–это количество инцидентных ребер вершины xi
a2
x1
x2
a3
a1
a4
x3
x4
a5
x5
Например, d (x1)=2, d (x2)=3, d (x3)=3…
26
27. Способы описания графов
Теоретико-множественное описаниеОписание отображениями
Графическое
Матричное
27
28. Теоретико-множественное представление графов
Граф описывается явным перечислением элементов множестввершин и дуг.
x2 рис.3 и рис. 4.
Примеры описания приведены для орграфов на
a4
a1
a2
x1
a3
x3
a5
a6
x4
Рис. 3
28
29.
Орграф G5G5=(X, A), где X={B, C, D, E, F} - множество вершин графа,
A={ai}, i=1,2,...,5 - множество дуг графа,
причем
a1=(F, B), a2=(B, E), a3=(F, D), a4=(E, C), a5=(C, D).
B
a1
F
C
a2
a3
E
a4
a5
D
29
30.
Задание графов отображениямиОписание графов состоит в задании множества вершин Х и
соответствий Г или отображений для каждой вершины.
Соответствием Г называется отображение множества Х
в Х,
Отображением вершины xi — Г(xi) является множество
вершин, в которые существуют дуги из вершины xi, то есть
Г(xi)={ xj: дуга (xi,) xj A}
.
30
31.
Задание графов соответствиемТак для орграфа на рис. такое
описание :
G =(X, Г),
x2
где X={xi}, i=1,2,...,4 - множество
x1
вершин,
Г(х1)={ x2 },
Г(x2)={ x3, x4 },
Г(x3)={ x3 },
Г(x4)={ x1, x2 }
a4
a1
a2
a3
x3
a5
a6
x4
- отображения.
31
32. Задание графов соответствием
Для неориентированногоили
смешанного
предполагается,
графов x1
что каждое ребро как бы заменяется
двумя
противоположно
направленными дугами.
Например, для графа на рис.2,б : x4
Г(х2)={ x1, x3, x5 },
Г(x4)={ x3, x5} и т.д.
a1
a2
x2
a3
x3
a4
a5
x5
Рис. 2,б
32
33. Матричное представление графов
Для обработки на ЭВМ графы удобно представлятьв виде матриц смежности и инциденций.
Матрица смежности
размерностью n n,
-
это
квадратная
матрица
где n - число вершин графа, однозначно представляющая
его структуру.
A={aij}, i,j= 1,2,...,n, причем
aij=1, если дуга (xi, xj),
aij=0, если нет дуги (xi, xj).
33
34. Матрица смежности
Так для графа на рис. матрица смежности выглядиттак:
x1
x2
А=
x6
x3
x5
6
а)
x4
x1
x2
x3
x4
x5
x6
x1
0
0
0
0
0
1
x2 x3
1 1
1 0
0 0
0 1
0 0
0 0
б)
x4
0
0
0
0
1
0
x5
1
1
0
0
0
1
x6
0
0
0
0
0
1
34
35.
Матрица смежностиПо матрице смежности
можно найти
характеристики вершин.
Так сумма элементов iой строки матрицы даетА=
полустепень исхода
вершины xi,
а сумма элементов i-го
столбца дает полустепень
захода вершины xi.
x1
x2
x3
x4
x5
x6
x1
0
0
0
0
0
1
x2 x 3
1 1
1 0
0 0
0 1
0 0
0 0
б)
x4
0
0
0
0
1
0
x5
1
1
0
0
0
1
x6
0
0
0
0
0
1
Сумма единиц главной диагонали – это количество
петель.
35
36. Матрица смежности
По матрице смежностиможно найти прямые и
обратные отображения.
Рассмотрим i-ю строку
матрицы.
Если элемент
А=
aij=1, то элемент графа
xj
входит
в
отображение Г(xi).
Например, в 2-й строке
матрицы А единицы
стоят в 2-м и
5-м
столбцах,
следовательно,
Г(х2)={ x2, x5}.
x1
x2
x3
x4
x5
x6
x1
0
0
0
0
0
1
x2 x 3
1 1
1 0
0 0
0 1
0 0
0 0
б)
x4
0
0
0
0
1
0
x5
1
1
0
0
0
1
x6
0
0
0
0
0
1
36
37.
Матрица инциденцийМатрица инциденций - это прямоугольная матрица размером
n m,
где n- количество вершин графа, а m - количество дуг графа.
Обозначается матрица инциденций
B={ bij },i=1,2,...,n, j=1,2,...,m.
Каждый элемент матрицы :
bij= 1, если xi является начальной вершиной дуги aj,
bij= -1, если xi является конечной вершиной дуги aj,
bij= 0, если xi не является концевой вершиной дуги aj или если
aj является петлей.
37
38.
Матрица инциденцийx 1 a1
a3
x2
a9
a8 a4
a10 x6
x3
a5
a7
x5
В=
a2
Для того, чтобы пометить
вершину, содержащую
петлю, можно в этом
столбце поставить * или
любой другой символ.
x1
x2
x3
x4
x5
x6
a6
a1
1
-1
0
0
0
0
x4
a2
1
0
-1
0
0
0
a3
0
*0
0
0
0
0
a4
0
1
0
0
-1
0
a5
0
0
-1
1
0
0
a6
0
0
0
-1
1
0
a7
0
0
0
0
-1
1
a8
1
0
0
0
-1
0
a9
-1
0
0
0
0
1
a1
00
0
0
0
0
*0
38
в)
39.
Матрица инциденцийПо матрице инциденций можно найти характеристики графа:
Число 1 в i-ой строке– это d0(xi)
*
Число -1 в i-ой строке– это dt(xi)
*
Число нулевых столбцов – это число петель в графе.
В=
x1
x2
x3
x4
x5
x6
a1
1
-1
0
0
0
0
a2
1
0
-1
0
0
0
a3
0
0
*
0
0
0
0
a4
0
1
0
0
-1
0
a5
0
0
-1
1
0
0
a6
0
0
0
-1
1
0
a7
0
0
0
0
-1
1
a8
1
0
0
0
-1
0
a9
-1
0
0
0
0
1
a1
00
0
0
0
0
*0 39
40.
Матрица инциденцийДля неориентированного графа, матрица инциденций
определяется так же, за исключением того ,что все
элементы, равные -1, заменяются на 1.
x1
x2
X3
X4
x5
a1
1
1
0
0
0
a2
0
0
1
1
0
a3
0
1
1
0
0
a4
0
1
0
0
1
a5
0
0
0
1
1
x1
x2
a1
a3
a2
x4
x3
a5
a4
x5
40
41. Операции над графами
Рассмотрим семь операций над графами,три из которых являются бинарными, включающими два графа,
а остальные четыре - унарные, то есть определены на одном
графе.
Исходные графы G1 и G2 показаны на рис. 6, а,б. G1=(X1, A1),
где X1={xi}, i=1,2,...,6, A={ ai }, i=1,2,...,7. и G2=(X2, A2), где X2={ xi },
i=1,2,...,6, A={a1, a3, a5, a6, a9, a10}.
Матрицы смежности графов показаны на рис.6,в
и
6,г
соответственно. (Чтобы не загромождать рисунок , нули не
показаны).
41
42. Операции над графами Исходные графы
Операции над графами Исходныеx1
x1
x2
x1
x2
x3
1
1
x2
А1=
x3
а)
x4
x3
графы
x4
x5
x6
1
1
1
1
1
x4
x5
x5
x6
x6
в)
42
43. Операции над графами.Исходные графы
x2x1
x1
x1
А2=
x3
x4
x2
x3
x4
1
1
1
x5
x6
x2
x3
x4
1
1
1
1
x5
x6
x5
б)
x6
г)
43
44. Операции над графами. Объединение
Объединение графов G1 и G2, обозначаемое какG 1 G 2,
представляет такой граф
G3=(X1 X2, A1 A2),
что множество его вершин является объединением Х1 и Х2,
а множество ребер - объединением А1 и А2.
Граф G3, полученный операцией объединения графов G1 и
G2, показан на рис. 7а, а его матрица смежности - на рис. 7б.
44
45. Объединение
x1x3
x2
x2
x1
x3
x4
x5
x6
x2
x1
x3
x4
x4
а)
x6
x5
G1
x6
x5
G2
G 1 G 2
45
46. Объединение
xx
x
x
x
x
1
2
3
4
5
1
1
x6
x
1
1
3
x
x
x
x
x
1
2
3
4
5
6
1
1
1
x
2
x
x
1
x
А1=
x
2
1
1
1
1
А2=
x
1
1
3
x
1
1
4
x
4
x
5
x
6
5
x
6
46
47. Объединение
x1x1
x2
x3
x4
1
1
1
x2
А3=
x5
x6
1
1
1
x3
1
x4
1
1
1
x5
x6
г)
47
48.
Объединениеa1
a9
x1
a5 a
4
x3
a7 a
10
x2
x1
x1
a8
a3
x4
А3=
a6
x3
x4
1
1
1
x5
x6
1
1
1
x2
x3
1
x4
1
1
1
x5
x6
x6
x5
x2
G1 G2
б)
Рис. 7
48
49.
Пересечение G1 G2Пересечение графов G1 и G2, обозначаемое как
представляет собой граф
G1 G2,
G4=(X1 X2, A1 A2).
Таким образом, множество вершин графа G4 состоит из
вершин, присутствующих одновременно в G1 и G2.
Операция пересечения графов G1 G2 показана на рис. 8.
49
50. Пересечение G1 G2
Пересечение G1 G2x1
x2
x2
x1
x1
a1
x2
a5
a3
x3
x3
x4
x3
a6
x4
а)
x4
x6
x5
x6
x5
x6
x5
G1
G2
Рис. 8
50
51. Пересечение G1 G2
Пересечение G1 G2x
x
x
x
x
x
1
2
3
4
5
1
1
x6
x
1
1
3
x
1
3
6
2
4
5
1 1 1
x
2
x
x x x
1
x
А1=
x x
2
1
1
1
1
А2
=
x
1
1
3
x
x
4
4
x
x
5
5
x
x
6
6
1
1
51
52. Пересечение G1 G2
Пересечение G1 G2x1
x1
А3=
x2
x3
1
1
x4
x5
x6
x2
x3
1
1
x4
x5
x6
г)
52
53.
Кольцевая сумма G1 G2Кольцевая сумма двух графов G1 и G2, обозначаемая как
G1 G2,
представляет собой граф G5, порожденный на множестве
ребер
А1 А2.
Другими словами, граф G5 не имеет изолированных вершин
и состоит только из ребер, присутствующих либо в G1, либо в
G2, но не в обоих одновременно.
Кольцевая сумма графов G1 и G2 показана на рис. 9.
53
54. Кольцевая сумма G1 G2
Кольцевая сумма G1 G2x2
x1
x1
x3
x2
x2
x1
x3
x4
x5
x6
x3
x4
x4
а)
x6
x5
G1
x6
x5
G2
Рис. 9
54
55.
Операции над графамиТри рассмотренные операции коммутативны т.е.
G1 G2 = G2 G1,
G1 G2 = G2 G1,
G1 G2 = G2 G1 ,
и многоместны ,
т.е. G1 G2 G3 G4 ... , G1 G2 G3 G4 ... и так
далее.
55
56.
Унарные операцииУдаление вершины
Если xi-вершина графа G=(X,A), то G-xiпорожденный подграф графа G на множестве вершин X-xi ,
т.е. G-xi является графом , получившимся после удаления
из графа G вершины xi и всех ребер, инцидентных этой
вершине.
X2
X2
X1
a1
a4
a3 a
5
a2
a6
a8
X5
а
X3
X1
a2
a7
X4
X5
a4
a1
a3
a5
a8
X4
б)
56
57.
Удаление ребра или дугиЕсли ai-дуга графа G=(X,A), то
G-ai
- подграф графа G, получающийся после удаления
из G дуги ai.
Заметим, что концевые вершины дуги ai не удаляются.
Удаление из графа множества вершин или дуг
определяются как
последовательное
удаление
определенных вершин или дуг.
57
58.
Удаление ребра или дугиУдаление дуг a4 и a7 показано на рис.11 б.
X2
X2
a1
X1
a2
a5
a6
a8
X5
a7
X4
X3
X1
X3
a3
a4
a1
a4
a2
X5
a3
a5
а
a6 6
a8
a7
X4
б)
а)
Рис. 11
58
59.
Замыкание или отождествлениеГоворят, что пара вершин xi и xj в
графе G замыкается (или
отождествляется),
если они заменяются такой новой
вершиной, что все дуги в графе G,
инцидентные вершинам xi и xj ,
становятся инцидентными новой
вершине.
59
60.
Замыкание или отождествление(X1, Х2)
X2
X2
a1
a4
X1
a2
Xa
12
X3
a3
a5
a6
a8
X5
а)
a7
X4
a2
a
a1 4
a1
X3
a3
a5
a6
X5
a8
Рис. 12
б)
a7
X4
60
61.
СтягиваниеПод стягиванием подразумевают операцию удаления дуги
или ребра и отождествление его концевых вершин.
Граф, изображенный на рис.6,д получен стягиванием дуги а1, а
на рис.8,е - стягиванием дуг a1, a6 и a7.
X2
a1
X1
a2
(X1, ХX2)
2
a4
X3
a3
a5
a6
a8
X5
а)
a7
Xa1 2
a2
X4 Рис. 12X5
a4
a1
a3 a5
a8
а)
a6
X3
a7
X4
61
62. Стягивание
(X1, Х2)X2
(X1, Х2)
X2
Xa1 2
a2
X5
a4
a1
a3
X3
a5
a6
a8
а)
a7
X4
Xa1 2
a2
X5
a4
a1
(X3, Х4)
X3
a3 a
5
a6
a8
а
8
a7
X4
б)
62