ДЕРЕВЬЯ - Cs.ioc.ee

Определение дерева и основные свойства
Остовные деревья графа
ДЕРЕВЬЯ
Тема 8
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Loengu kava
1
Определение дерева и основные свойства
2
Остовные деревья графа
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
J¨argmine punkt
1
Определение дерева и основные свойства
2
Остовные деревья графа
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Определение дерева
Определение
Граф, в котором нет циклов, называется лесом. Связный лес называется
деревом.
Примеры графа
Вершина, степень которой 1, называется листом.
Утверждение. Каждое дерево является двудольным графом
Доказательство.
Начнем с какой-нибудь вершины распределять вершины по
основаниям (долям). У нас не может возникнуть противоречия с
определением двудольного графа, т.к. нет циклов
ч.т.д.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Определение дерева
Определение
Граф, в котором нет циклов, называется лесом. Связный лес называется
деревом.
Примеры графа
Вершина, степень которой 1, называется листом.
Утверждение. Каждое дерево является двудольным графом
Доказательство.
Начнем с какой-нибудь вершины распределять вершины по
основаниям (долям). У нас не может возникнуть противоречия с
определением двудольного графа, т.к. нет циклов
ч.т.д.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Ребра и компоненты связности
Лемма L1
Если у графа G имеется n вершин, m ребер и k компонент
связности, то n − k 6 m.
Доказательство.
Индукция по m.
База. Если m = 0, то каждая вершина графа G является
отдельным связным компонентом, т.е. k = n.
Шаг. m > 0. Удалим из графа G одно ребро, получим граф с
m − 1 ребрами. Дальше есть 2 варианта:
Число компонент связности не изменилось. По индукции
получаем n − k 6 m − 1 < m.
Число компонент связности увеличилось на 1. По
индукции получаем n − (k + 1) 6 m − 1. Поэтому n − k 6 m.
ч.т.д.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Связность и цикличность
Теорема
T = (V , E ) граф с n-вершинами. Из двух утверждений следует третье:
(a) T - связный;
(b) T - без циклов;
(c) В T имеется n − 1 ребер.
Доказательство.
(a) & (b)⇒(c). Если T содержит 1 вершину, тогда все его ребра являются
петлями, т.е. T содержит цикл, что противоречит условию (b). Следовательно,
число ребер 0.
Если число вершин в T - n > 0, тогда из условия (a) следует, что с любой
вершиной связано минимум 1 ребро, а из условия (b) следует, что найдется
такая вершина v , что deg(v ) < 2, потому что иначе в графе был бы цикл.
Индуцированный подграф T 0 со множеством вершин V \ {v } является связным и
без циклов, по индукции в нем n − 2 ребер.
В графе T на 1 ребро больше, чем в графе T 0 .
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Связность и цикличность
(продолжение доказательства ...)
(b) & (c)⇒(a). Утверждаем наоборот, что T не является связным, т.е. у него k
связных компонентов T1 , . . . , Tk , которые все связные и без циклов. Поэтому в
каждом из них ребер на 1 меньше, чем вершин. Тогда в графе T всего должно
быть n − k ребер. Так как по условию (c) в графе n − 1 ребер, то k = 1 т.е. T
является связным.
(a) & (c)⇒(b). Утверждаем, что в графе T есть цикл. Удалив оттуда одно ребро,
останется связный граф с n вершинами и n − 2 ребрами, который противоречит
Лемме L1.
ч.т.д.
Два альтернативных определения дерева
Дерево - связный граф с n вершинами и n − 1 ребрами.
Дерево - свободный от циклов граф с n вершинами и n − 1 ребрами.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Связность и цикличность
(продолжение доказательства ...)
(b) & (c)⇒(a). Утверждаем наоборот, что T не является связным, т.е. у него k
связных компонентов T1 , . . . , Tk , которые все связные и без циклов. Поэтому в
каждом из них ребер на 1 меньше, чем вершин. Тогда в графе T всего должно
быть n − k ребер. Так как по условию (c) в графе n − 1 ребер, то k = 1 т.е. T
является связным.
(a) & (c)⇒(b). Утверждаем, что в графе T есть цикл. Удалив оттуда одно ребро,
останется связный граф с n вершинами и n − 2 ребрами, который противоречит
Лемме L1.
ч.т.д.
Два альтернативных определения дерева
Дерево - связный граф с n вершинами и n − 1 ребрами.
Дерево - свободный от циклов граф с n вершинами и n − 1 ребрами.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Связность деревьев
Определение
В связном графе G = (V , E ) ребро e ∈ E называется мостом, если при удалении
этого ребра граф G становится несвязным.
Теорема
Граф T является деревом тогда и только тогда, когда он связный и каждое его
ребро является мостом.
Доказательство.
Необходимость. В T имеется n вершин и n − 1 ребер. Если удалим одно ребро,
останется граф с n вершинами и с n − 2 ребрами, который согласно Лемме L1
является несвязным. Поэтому это ребро является мостом.
Достаточность. Если в T найдется какой-нибудь цикл, то ребра, принадлежащие
циклу не являются мостами, т.к. при удалении одного из них, граф останется
связным. Поэтому T без циклов (и согласно предположению теоремы –
связный), т.е. T является деревом.
ч.т.д.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Критерии дерева
Теорема 8.1.1
T - граф, в котором n вершин. Следующие утверждения равны:
(a) T - дерево;
(b) между двумя произвольными вершинами T имеется ровно одна простая
цепь;
(c) T не имеет циклов, но при добавлении ребра все равно между какими
двумя вершинами, возникнет цикл.
Доказательство.
(a) ⇒(b). Между каждыми двумя вершинами есть хотя бы одна простая цепь, в
противном случае T был бы связным. Если между вершинами есть несколько
простых цепей, то эти цепи создадут цикл, поэтому T не может быть деревом.
(b) ⇒(c). T не имеет циклов, т.к. в цикле между вершинами есть как минимум
две простые цепи. При добавлении ребра e между вершинами u и v возникнет
цикл u v −e− u.
(c) ⇒(a). Предположим, что T не является связным. При добавлении ребра
между вершинами, принадлежащим к связным компонентам, цикл не возникнет.
Следовательно, у нас противоположное утверждение.
ч.т.д.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
J¨argmine punkt
1
Определение дерева и основные свойства
2
Остовные деревья графа
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Остовное дерево графа
Определение
Остовным деревом связного графа G = (V , E ) является
подграф T графа G , который является деревом со множеством
вершин V .
В случае несвязного графа можем говорить о остовном лесе соединение остовных деревьев связных компонентов этого
графа.
Примеры остовных деревьев:
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Алгоритм нахождения остовного дерева
G = (V , E ) - какой-то граф с n вершинами и для каждого ребра e ∈ E определен
его вес w (e) ∈ R. Если G 0 = (V 0 , E 0 ) - подграф графа G , тогда
w (G 0 ) =
∑
w (e).
e∈E 0
Алгоритм Джозефа Крускала для нахождения остовного дерева с минимальным
весом
Вход: Граф G = (V , E ), где |V | = n.
Выход: Дерево T = (V , E 0 ), где E 0 ⊆ E .
Выбираем за ребро e1 ребро с минимальным весом в графе G ;
for i := 2 step 1 to n − 1
do
Выбираем за ребро ei в графе G ребро так, что выполнены условия:
1
2
3
ei отличается от ребер e1 , . . . , ei−1 ;
ei не составляет с ребрами e1 , . . . , ei−1 цикла;
ei имеет минимальный вес и удовлетворяет двум
предыдущим условиям;
od
return(T (V , {e1 , . . . , en−1 }))
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Пример: Нахождение минимального остовного дерева
99
68
48
93
101
91
59
78
129
111
155
152
136
108
99
72
79
97
143
103
51
73
91
87
128
71
Jaan Penjam, email: [email protected]
113
72
84
96
84
64
48
68
25
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Правильность алгоритма
Теорема
Алгоритм Крускала является корректным.
Доказательство.
T - остовное дерево – он без циклов, у него n вершин и n − 1 ребер.
Допустим, что w (T ) не является минимальным.T 0 такое остовное дерево графа
G с минимальным весом, что у G с T имеется максимальное число общих ребер.
k ∈ {1, . . . , n − 1} - наименьшее такое число, что ek ∈
/ E (T 0 ). S = T 0 ∪ {ek }. В графе
S есть какой-то цикл C . Так как T и T 0 не имеют циклов, то ek ∈ C и есть
e ∈ E (T 0 ) \ E (T ), так что e ∈ C .
Граф T 00 = S \ {e} - связный и имеет n − 1 ребер, т.е. является остовным деревом.
Ребро e такое, что
отличается от ребер e1 , . . . , ek−1 ,
не составляет с ребрами e1 , . . . , ek−1 цикла (потому что e1 , . . . ek−1 ∈ E (T 0 )).
Ребро ek является с минимальным весом среди тех ребер, которые
отличаются от ребер e1 , . . . , ek−1 ,
не составляют с ребрами e1 , . . . , ek−1 цикла.
Другими словами, w (ek ) 6 w (e). Следовательно, подучаем
w (T 00 ) = w (T 0 ) − w (e) + w (ek ) 6 w (T 0 ), т.е. вес T 00 не больше веса остовного
дерева T 0 . У дерева T 00 больше общих ребер с деревом T , чем у дерева T 0 , что
противоречит выбору T 0 .
ч.т.д.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Оценка вычислительной сложности нахождения
минимального остовного дерева
Пусть G – граф с n вершинами и m ребрами.
Сложность алгоритма Крускала – сложность O(m log m)
Aльтернативные алгоритмы построения минимального остовного дерева:
Алгоритм Прима (также алгоритм Прима-Ярника-Дейкстры; DJP
algorithm) – сложность O(m log n)
Обратный метод Крускала (англ.: reverse-delete algorithm) – сложность
O(m log m(log log m)3 )
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Задача коммивояжёра и минимальное остовное дерево
Пример
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Задача коммивояжёра и минимальное остовное дерево
Пример
Гамильтонов цикл минимальным весом w (H) = 2 + 1 + 3 + 2 + 4 + 1 = 13.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Задача коммивояжёра и минимальное остовное дерево
(2)
Пример
Остовное дерево минимальным весом w (T ) = 1 + 2 + 1 + 2 + 2 = 7.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Задача коммивояжёра и минимальное остовное дерево
(3)
Пример
Остовное дерево минимальным весом w (T ) = 1 + 2 + 1 + 1 + 2 = 7.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Задача коммивояжёра и минимальное остовное дерево
(4)
Пример
На основе минимального остовного дерева составляем маршрут весом
w (M) = 2 + 2 + 3 + 1 + 2 + 1 = 14, который окажется лишь 7,7% длиннее, чем
оптимальное решение задачи коммивояжёра.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья
Определение дерева и основные свойства
Остовные деревья графа
Задача коммивояжёра и минимальное остовное дерево
(4)
Пример
Когда весы ребер графа выполняют неравенство треугольника:
d(A, C ) 6 d(A, B) + d(B, C ), то маршрут составленный описанным методом не
превышает оптимльное больше чем дважды.
Jaan Penjam, email: [email protected]
Дискретная математика II: Деревья