Содержание
- 2. ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь длины k – последовательность, содержащая k ребер. Длина пути -
- 3. ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Путь называется простым или цепью, если все его ребра различны. Если
- 4. ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Пример. Определить возможные маршруты и их длину из вершины v0 в
- 5. ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Решение. Пути: 1) v0v3v8 длиной 2; 5) v0v3v4v5v4v7v8 длиной 6; 2)
- 6. ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Маршрут v0v1v2v3v0 для графа (рис. 12) является простым циклом; маршрут v3v4v5v6v7v4v3
- 7. ТЕОРИЯ ГРАФОВ ПУТЬ, ЦЕПЬ, ЦИКЛ Эйлеров цикл – последовательность вершин (может быть и с повторениями), через
- 8. ТЕОРИЯ ГРАФОВ СВЯЗНОСТЬ ГРАФА Вершины v’ и v’’ называются связными, если существует маршрут с началом в
- 9. ТЕОРИЯ ГРАФОВ СВЯЗНОСТЬ ГРАФА Граф, изображенный на рис. 13 (a) – не связный, а граф на
- 10. ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Для определения наличия маршрута между двумя вершинами используется матрица смежности. Булево произведение
- 11. ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ Пример. Для графа (рис. 14) определим, какие и в каком количестве существуют
- 12. ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица смежности Матрица В2
- 13. ТЕОРИЯ ГРАФОВ ОСНОВНЫЕ ПОНЯТИЯ Матрица В3 Матрица В4
- 14. ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ При использовании алгебраических операций получаем матрицу, которая характеризует не только наличие путей
- 15. ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ
- 16. ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ
- 17. ТЕОРИЯ ГРАФОВ КОЛИЧЕСТВО МАРШРУТОВ
- 18. ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Матрица достижимости ориентированного графа – бинарная матрица замыкания по транзитивности. Таким образом,
- 19. ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Для нахождения матрицы достижимости начинаем работу с построения матрицы смежности. Находим булевы
- 20. ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Матрица смежности Матрица В2
- 21. ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Более удобный путь определения матрицы достижимости дает так называемый алгоритм Уоршелла (алгоритм
- 22. ТЕОРИЯ ГРАФОВ МАТРИЦА ДОСТИЖИМОСТИ Алгоритм Уоршелла генерирует последовательность матриц W0…Wn, матрица W0 совпадает с матрицей смежности
- 23. ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА Берем k-ый столбец матрицы Wk-1 Строку с номером i(i=1,…,n), у которой на
- 24. ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА
- 25. ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА
- 26. ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА
- 27. ТЕОРИЯ ГРАФОВ АЛГОРИТМ УОРШЕЛЛА
- 29. Скачать презентацию