Содержание
- 2. Тема: Элементы теории графов Общие понятия Маршруты. Циклы. Связность графов Пленарные графы Ориентированные графы (орграфы) Задачи
- 3. История семи мостов Кёнигсберга Старинная карта Кёнигсберга. Части города: А — Альтштадт, Б — Кнайпхоф, В
- 4. Семь мостов Кёнигсберга Упрощённая схема мостов Кёнигсберга. Граф кёнигсбергских мостов
- 5. Выводы Эйлера Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно
- 6. Общие понятия Граф определяется как пара (двойка) множеств – множество вершин W и множество ребер L:
- 7. Количество вершин графа, т.е. мощность (количество элементов) множества W, – это его порядок n: |W| =
- 8. Свойства матрицы смежности: матрица квадратная порядка n; матрица бинарная (двоичная); на главной диагонали MS только нули
- 9. Графы, которые здесь рассматриваются, – «обыкновенные». Есть еще мультиграфы (рис.2 а), когда смежные вершины могут быть
- 10. Вторая разновидность матричного представления графов матрица инциденций MI: Строки в MI отображают ребра и вершины, с
- 11. Свойства матрицы инциденций: в общем случае матрица прямоугольная, порядка |L| x |W|; матрица бинарная (0, 1);
- 12. Общие понятия Удаляя вершины (не все) и ребра из некоторого графа, получают подграф. А сам граф
- 13. Общие понятия Графы эквивалентны, если они, конечно, имеют одинаковый порядок и одинаковый характер связей – соответствующие
- 14. Общие понятия Степень вершины графа – количество прилежащих ребер. Например: бw1 = 2, бw2 = 2,
- 15. Общие понятия Если все вершины имеют одинаковую степень, граф – регулярный такой-то степени. На рис.4 представлены
- 16. Общие понятия Теорема о сумме степеней всех вершин графа. В символической форме: Т.е., сумма эта равна
- 17. Общие понятия Теорема о количестве вершин нечетной степени: количество таких вершин имеет значение четного числа. Действительно,
- 18. Общие понятия В задачах на графах часто используются помеченные графы. Отмечать (помечать) можно как вершины, так
- 19. Полный граф имеет максимально возможное количество ребер, обозначается Кn (рис.6) Рис.6. Полные графы Общие понятия
- 20. Общие понятия В двудольных графах допускаются связи только между вершинами разных долей (рис.7). Рис.7. Двудольный граф
- 21. Общие понятия Если в двудольном графе количество ребер максимально возможное, он – полный двудольный граф. На
- 22. Маршрут в графе – это последовательность проходимых ребер и вершин. Например, в графе рис.1 возможны такие
- 23. Маршруты и пути могут быть разомкнутые и замкнутые (циклы). Циклы могут быть простые и сложные. Сложные
- 24. Длина маршрута (пути) – это количество проходимых ребер. В примере маршруты имеют длину соответственно 3, 2
- 25. Дерево – это связный ациклический граф (рис 6.7). В корневом дереве одна из вершин специально выделяется
- 26. Теорема о количестве маршрутов заданной длины (рассматривается без доказательства): Количество маршрутов длины k из вершины wi
- 27. Маршруты. Циклы. Связность графов Действительно, MS в 1-й степени (просто MS, п. 6.1) определяет все маршруты
- 28. Маршруты. Циклы. Связность графов Произведение матриц (в общем случае прямоугольных, IхJ на JхК) определяется так. Берется
- 29. Маршруты. Циклы. Связность графов ИЛИ Внутренняя структура строки i = 1 указывает на то, что должны
- 30. Маршруты. Циклы. Связность графов Проверим, действительно ли, например, существуют 2 маршрута длины 1 из w1 в
- 31. Маршруты. Циклы. Связность графов Проверим существование 4 маршрутов w2 → w3 длины 3 , , ,
- 32. Маршруты. Циклы. Связность графов На основе степеней (k = 0, …, n – 1) матрицы смежности
- 33. Маршруты. Циклы. Связность графов В примере для графа рис.1: MSM =
- 34. Маршруты. Циклы. Связность графов Теорема о связности графа: Для связности графа, т.е. для взаимной достижимости любых
- 35. Маршруты. Циклы. Связность графов Из рис. 9 видно, что в самом неблагоприятном случае это значение обеспечивает
- 36. Маршруты. Циклы. Связность графов Если граф несвязный, он распадается на компоненты связности (рис.10). Рис.10. Несвязный граф
- 38. Скачать презентацию