Условия достижимости, базы дуг и растущие деревья

Сентябрь 7, 2022

Главная
Алгебра
Условия достижимости, базы дуг и растущие деревья

Содержание

2. СОДЕРЖАНИЕ Часть 1. Достижимость вершин. Часть 2. Базы дуг. Часть 3. Растущие ориентированные деревья.
3. Часть 1 Условия достижимости
4. Достижимость вершин На ориентированном графе G(X,U) t-я вершина считается достижимой из вершины s-ой, если существует хотя
5. МАТРИЦА ДОСТИЖИМОСТИ ВЕРШИН Матрица смежности вершин Граф Матрица достижимости вершин 1 3 2 4 5
6. Часть 2 Базы дуг
7. БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Базой дуг ориентированного графа G(X,U) с матрицей достижимости вершин «М» называется такое
8. ПРИМЕР 1 Матрица смежности вершин Граф G(X,U) Матрица достижимости вершин Суграф G(X,U’) Суграф G(X,U’’) Суграф G(X,U’’’)
9. МИНИМАЛЬНАЯ БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Минимальной базой дуг взвешенного ориентированного графа G(X,U) с матрицей достижимости вершин
10. ПРИМЕР 2 G(X,U) и М G(X,U’) и M’ G(X,U”) и M” M = M’= M”= Матрица
11. СВОЙСТВА БАЗ ДУГ Теорема 1. Каждый ориентированный граф обладает по крайней мере одной базой дуг. Теорема
12. АЛГОРИТМ ПОИСКА МИНИМАЛЬНОЙ БАЗЫ ДУГ 4 U’ существует 5 U’ –база дуг 6 R(U’) > R
13. ПРИМЕР 3 1 2 1 2 3 3 4 7 4 7 9 3 3 Исходный
14. САМОСТОЯТЕЛЬНО: Определить минимальную базу дуг на графе G(X,U): 2 4 3 5 1 1 8 5
15. Часть 3 Растущие ориентированные деревья
16. МИНИМАЛЬНЫЕ РАСТУЩИЕ ОРИЕНТИРОВАННЫЕ ДЕРЕВЬЯ Содержательная постановка задачи: требуется на заданном взвешенном ориентированном графе G(X,U) выделить подграф
17. ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ
18. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
19. СВОЙСТВА МИНИМАЛЬНЫХ РАСТУЩИХ ДЕРЕВЬЕВ Величина является нижней границей суммарного веса дуг минимального дерева. Если граф G(X,U)
20. ПРИМЕР 4 1 1 2 3 2 3 4 5 4 5 7 3 9 12
21. АЛГОРИТМ ВЫДЕЛЕНИЯ МИНИМАЛЬНОГО ДЕРЕВА НА ГРАФЕ БЕЗ КОНТУРОВ Шаг 1. На исходном графе G(X,U) удаляются все
22. САМОСТОЯТЕЛЬНО: Выделить минимальное дерево с корнем в 1-й вершине на графе G(X,U): 1 2 7 3
23. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ На полученном орграфе: 1. Определить минимальный разрез. 2. Удалить дуги минимального разреза на исходном
24. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9
25. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18
26. ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27
27. Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 1 - 3 Шаг 1. На исходном
28. Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 4 - 6 Шаг 4. Вершина j-я
29. Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 7 - 9 Шаг 7. На множестве
30. ПРИМЕР 5 1 2 9 7 3 4 10 8 4 5 2 3 1 4
32. Скачать презентацию

Слайд 2

СОДЕРЖАНИЕ
Часть 1. Достижимость
вершин.
Часть 2. Базы дуг.
Часть 3. Растущие

ориентированные
деревья.

Слайд 3

Часть 1
Условия достижимости

Слайд 4

Достижимость вершин
На ориентированном графе G(X,U) t-я вершина считается достижимой из вершины

s-ой, если существует хотя бы один путь, ведущий из s-ой вершины в t-ю. Так, 5-я вершина достижима из 1-й.

Слайд 5

МАТРИЦА ДОСТИЖИМОСТИ ВЕРШИН
Матрица смежности вершин Граф Матрица достижимости вершин
1
3

Слайд 6

Часть 2
Базы дуг

Слайд 7

БАЗА ДУГ - ОПРЕДЕЛЕНИЕ
Базой дуг ориентированного графа G(X,U) с матрицей

достижимости вершин «М» называется такое подмножество дуг U’ множества U, что:
граф G(X,U’) обладает такой же матрицей достижимости вершин M’, что и исходный граф G(X,U).
Удаление любой дуги, принадлежащей базе U’, изменяет условия достижимости вершин .

Слайд 8

ПРИМЕР 1
Матрица смежности вершин Граф G(X,U) Матрица достижимости вершин
Суграф G(X,U’) Суграф

G(X,U’’) Суграф G(X,U’’’)

База дуг

Слайд 9

МИНИМАЛЬНАЯ БАЗА ДУГ - ОПРЕДЕЛЕНИЕ
Минимальной базой дуг взвешенного ориентированного графа

G(X,U) с матрицей достижимости вершин «М» называется такое подмножество дуг U’ множества U, что:
граф G(X,U’) обладает такой же матрицей достижимости вершин M’, что и исходный граф G(X,U);
суммарный вес дуг подмножества U’ минимален.

Слайд 10

ПРИМЕР 2
G(X,U) и М G(X,U’) и M’ G(X,U”) и M”
M =

M’= M”=
Матрица достижимости вершин

Слайд 11

СВОЙСТВА БАЗ ДУГ
Теорема 1. Каждый ориентированный граф обладает по крайней мере

одной базой дуг.
Теорема 2 (Кёнига): Ориентированный граф без контуров обладает единственной базой дуг.
Теорема 3 (Гольдберга) : Число дуг любой базы дуг U’ ориентированного графа G(X,U), множество контуров которого не пусто, не превышает величины Y = 2(│X│-1), т.е. │U’│≤ 2│X│-2.

Слайд 12

АЛГОРИТМ ПОИСКА МИНИМАЛЬНОЙ БАЗЫ ДУГ
4 U’ существует
5 U’ –база дуг
6

R(U’) > R

9 Конец
алгоритма

7 R = R(U’)

Да Нет

Нет

Да

Нет

8 Печать R

Слайд 13

ПРИМЕР 3
1 2
1 2
3
3
4
7
4
7
9

Исходный граф
G(X,U)

Суграф G(X,U’) с минимальной базой дуг

Слайд 14

САМОСТОЯТЕЛЬНО:
Определить минимальную базу дуг на графе G(X,U):
2 4
3 5

1 8 5 4

3
6

9
2
7
10

Слайд 15

Часть 3
Растущие ориентированные деревья

Слайд 16

МИНИМАЛЬНЫЕ РАСТУЩИЕ ОРИЕНТИРОВАННЫЕ ДЕРЕВЬЯ
Содержательная постановка задачи: требуется на заданном

взвешенном ориентированном графе G(X,U) выделить подграф - дерево G’(X’,U’) с корнем в заданной s-ой вершине такой, что:
Все вершины, достижимые из s-й вершины на G(X,U), также достижимы из той же вершины на G’(X’,U’).
Суммарный вес дуг множества U’ минимален.

Слайд 17

ОБОЗНАЧЕНИЯ И ОПРЕДЕЛЕНИЯ

Слайд 18

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

Слайд 19

СВОЙСТВА МИНИМАЛЬНЫХ РАСТУЩИХ ДЕРЕВЬЕВ
Величина является
нижней границей суммарного веса дуг

минимального дерева.
Если граф G(X,U) не содержит контуров, то
отвечает оптимальному значению целевой функции. (Сравнить с теоремой Кёнига).

Слайд 20

ПРИМЕР 4
1
1
2 3
2 3
4 5
4

7 3 9 12

5 11

4 1

G(X,U)

G’(X’,U’)

Слайд 21

АЛГОРИТМ ВЫДЕЛЕНИЯ МИНИМАЛЬНОГО ДЕРЕВА НА ГРАФЕ БЕЗ КОНТУРОВ
Шаг 1. На исходном

графе G(X,U) удаляются все вершины, в которые отсутствуют пути из s-й вершины, являющейся корнем дерева. Полученный граф вновь обозначаем G(X,U).
Шаг 2.
Шаг 3. Дуги (p,j), определенные на предыдущем шаге, принадлежат множеству U’.
Шаг 4. Конец алгоритма.

Слайд 22

САМОСТОЯТЕЛЬНО:
Выделить минимальное дерево с корнем в 1-й вершине на графе G(X,U):

1 2 7

3 5

4 6

5 7 9 12

8 10 11 3 2

6
8

4 1

Слайд 23

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ
На полученном орграфе:
1. Определить минимальный разрез.
2. Удалить дуги минимального разреза

на исходном графе G(X,U).
3. На полученном графе G’(X’,U’) построить:
А) матрицу смежности вершин;
Б) минимальную базу дуг
В) минимальное растущее дерево с корнем в вершине – источнике.

Слайд 24

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 1 - 9

Слайд 25

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 10 - 18

Слайд 26

ПЕРСОНАЛЬНЫЕ ЗАДАНИЯ 19 - 27

Слайд 27

Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 1 -

Шаг 1. На исходном графе G(X,U) удаляются все вершины, в которые отсутствуют пути из s-й вершины, являющейся корнем дерева. Полученный граф вновь обозначаем G(X,U).
Шаг 2. Выбирается дуга с минимальным весом, заходящая в каждую вершину подмножества
.
Шаг 3. Если на множестве выбранных дуг есть дуга (s,j), исходящая из s-й вершины, то перейти к шагу 4, в противном случае – к шагу 6.

Слайд 28

Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 4 -

Шаг 4. Вершина j-я «стягивается» в s-ю. Если при этом граф «стянулся» в одну вершину, то перейти к шагу 9, в противном случае – к шагу 5.
Шаг 5. Если образуются пары параллельных и согласно ориентированных дуг, то остаётся одна из них, вес которой меньше. Перейти к шагу 2.
Шаг 6. Каждой j-й вершине (j ≠ s) присваивается потенциал p(j);
где r(i,j)* - дуга, выбранная на шаге 2 последней итерации.

Слайд 29

Алгоритм поиска минимального дерева на орграфе с бикомпонентами: шаги 7 -

Шаг 7. На множестве вершин выбирается такая, потенциал которой минимален.
Шаг 8. Полагая, что выбранная на шаге 7 вершина является j-й, выполняются следующие две операции:
дуга (i,j), помеченная звездочкой «*», теряет эту пометку, а дуга (k,j), такая, что:
её приобретает. Перейти к шагу 3.
Шаг 9. Конец алгоритма. «Стянутые» дуги образуют минимальное дерево.

Слайд 30

ПРИМЕР 5
1 2 9 7 3 4
10 8

4 5

2 3

4 5
2 3
1

6
5

4 1,5
2 3

1,3,5

4
2

2 1,3,4,5

2 4
1
3 5

R = 18

1 2 3 4

1 7

6
5

1 2 10 3

6
5

1 2

6
10

7 2 6

Условия достижимости, базы дуг и растущие деревья

Содержание

СОДЕРЖАНИЕЧасть 1. Достижимость вершин.Часть 2. Базы дуг.Часть 3. Растущие

Часть 1Условия достижимости

Достижимость вершинНа ориентированном графе G(X,U) t-я вершина считается достижимой из вершины

МАТРИЦА ДОСТИЖИМОСТИ ВЕРШИНМатрица смежности вершин Граф Матрица достижимости вершин 1 3

Часть 2Базы дуг

БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Базой дуг ориентированного графа G(X,U) с матрицей

ПРИМЕР 1Матрица смежности вершин Граф G(X,U) Матрица достижимости вершинСуграф G(X,U’) Суграф

МИНИМАЛЬНАЯ БАЗА ДУГ - ОПРЕДЕЛЕНИЕ Минимальной базой дуг взвешенного ориентированного графа

ПРИМЕР 2G(X,U) и М G(X,U’) и M’ G(X,U”) и M”M =

СВОЙСТВА БАЗ ДУГТеорема 1. Каждый ориентированный граф обладает по крайней мере

АЛГОРИТМ ПОИСКА МИНИМАЛЬНОЙ БАЗЫ ДУГ 4 U’ существует5 U’ –база дуг6

ПРИМЕР 3 1 2 1 2 3 3 4 747 9

САМОСТОЯТЕЛЬНО:Определить минимальную базу дуг на графе G(X,U): 2 4 3 5

Часть 3 Растущие ориентированные деревья

МИНИМАЛЬНЫЕ РАСТУЩИЕ ОРИЕНТИРОВАННЫЕ ДЕРЕВЬЯ Содержательная постановка задачи: требуется на заданном