Содержание
- 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. Скачать презентацию