Содержание
- 2. Связность. Дерево и его виды Множество вершин графа таких, что любые две из него связаны, а
- 3. Например, все компьютеры, включённые в Интернет, образуют связный граф. Два конкретных компьютера могут быть не соединёнными
- 4. В орграфах связность может быть сильной или слабой. В первом случае существует ориентированный путь из любой
- 5. Последовательность v1 , е1 , v2 , е2 , …, vk , еk , vk+1 вершин
- 6. G1 – дерево Рис. 6 G2 – не дерево G3 – не дерево Связный неориентированный граф,
- 7. Следующие утверждения эквивалентны: G – дерево. G – связный неорграф и в нём число ребер m
- 8. Изобразите все деревья (неизоморфные), которые можно построить на 6 вершинах (деревья образуют лес). Рис. 7
- 9. Как правило, дерево-граф выглядит как дерево «вверх ногами». Корневым называется дерево с выделенной по каким-либо соображениям
- 10. Ориентированным деревом называется орграф без циклов и петель, у которого: - есть ровно одна вершина (корень),
- 11. Двоичным называется дерево – неориентированное со степенями вершин не больше 3 (рис. 8); – ориентированное со
- 12. Остовы Граф G′ называется подграфом графа G, если множества их вершин совпадают, а множество рёбер G′
- 13. Пример. Найти число различных остовов графа G (рис. 10).
- 14. Решение. Матрица Кирхгофа данного графа имеет вид:
- 15. Вычислим алгебраическое дополнение элемента k11:
- 19. Значит, данный граф имеет 11 различных остовов. Рис. 11
- 20. Теорема 2. Число рёбер неорграфа G, которые нужно удалить для получения остова, не зависит от порядка
- 21. Алгоритмы нахождения остова минимального веса Связный граф может иметь много остовов. Часто остов требуется выбрать из
- 22. Другими словами, в задаче нужно найти остов графа минимального веса. Алгоритм Прима Разобьём множество вершин V
- 23. Шаг 1. Присвоение начальных значений Пусть (v1 – произвольная вершина), , Ø. Шаг 2. Обновление данных
- 24. Пример. Найти остов минимального веса графа (рис.13) с помощью алгоритма Прима. v6
- 25. Шаг 1. Пусть V′ = {v1}, тогда V′′ = {v2, v3, v4, v5, v6}, U′ =
- 26. v6 1 3 5 7 v4 v1 v3 v5 3 2 4 4 2 v2 Шаг
- 27. Вторая итерация Шаг 2. Шаг 3. V′ ≠ V, переход к шагу 2.
- 28. v6 1 3 5 7 v4 v1 v3 v5 3 2 4 4 2 v2 Вторая
- 29. Третья итерация Шаг 2. Шаг 3. V′ ≠ V, переход к шагу 2.
- 30. v6 1 3 5 7 v4 v1 v3 v5 3 2 4 4 2 v2 Третья
- 31. Четвёртая итерация Шаг 2. Шаг 3. V′ ≠ V, переход к шагу 2.
- 32. v6 1 3 5 7 v4 v1 v3 v5 3 2 4 4 2 v2 Четвёртая
- 33. Пятая итерация Шаг 2. Шаг 3. V′ = V Ø
- 34. v6 1 3 5 7 v4 v1 v3 v5 3 2 4 4 2 v2 Пятая
- 35. Получен остов минимального веса (рис. 14): 2 v6 v5 v3 v1 v2 v4 1 3 3
- 36. Алгоритм Краскала Из всех рёбер выбирают одно с наименьшим весом. Затем из оставшихся находят ребро с
- 37. Пример. Найти остов минимального веса графа (рис.13) с помощью алгоритма Краскала. v6
- 38. Выбираем ребро с минимальным весом: (v4; v6) c весом 1. Снова выбираем ребро с минимальным весом,
- 39. Из оставшихся наименьший вес 2 имеет ребро (v3; v5). Оно не образует цикла с рёбрами, выбранными
- 40. Следующим ребром, включённым в остов, будет (v1; v2) с весом 3, не образующее цикла с тремя
- 42. Скачать презентацию