Содержание
- 2. ОСНОВНЫЕ ВОПРОСЫ: Сведения из истории графов. Граф и его элементы. Пути и маршруты в графах Связные
- 3. Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Теория графов – область дискретной математики,
- 4. Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) ,
- 5. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя),
- 6. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВ Термин "граф" впервые появился в книге венгерского математика Д. Кенига в 1936 г.,
- 7. В основе теории лежит понятие графа. Граф - совокупность конечного числа точек, называемых вершинами графа, и
- 8. СОСТАВ ГРАФА Граф состоит из вершин, связанных линиями. Вершины графа обозначают латинскими буквами A, B, C,
- 9. Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы
- 10. Взвешенный граф Это граф, рёбрам или дугам которого поставлены в соответствие числовые величины (они могут обозначать,
- 11. Две вершины графа называются смежными, если существует инцидентное им ребро: на рисунке смежными являются вершины А
- 12. Если граф G имеет ребро , у которого начало и конец совпадают, то это ребро называется
- 13. Два ребра называются смежными, если они имеют общую вершину. На рисунке смежными являются, например, рёбра х1
- 14. Рёбра, которые начинаются в одной и той же вершине, заканчиваются также в одной и той же
- 15. На рисунке кратными являются, например, рёбра х1(А, В), х2(А, В). Вершинам А и С инцидентны рёбра
- 16. На рисунке вершина А имеет степень, равную 1, вершина С – 4, вершина D – 2.
- 17. E Вершина графа, имеющая степень, равную нулю, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль-графом.
- 18. На рисунке вершины А, В, Е, G, H – висячие. х1 х2 х3 х4 х5 х6
- 19. Теорема 1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер
- 20. Вершина называется чётной (нечётной), если её степень – чётное (нечётное) число. На рисунке deg(D)=2, deg(F)=3, значит
- 21. Задача. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был
- 22. Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин. Следствие. Невозможно начертить граф с нечётным
- 23. Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга,
- 24. Дополнением графа называется граф с теми же вершинами V, что и граф G, и имеющий те
- 25. Закономерность 1. Закономерность 2. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше
- 26. Число нечетных вершин любого графа четно. Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 3.
- 27. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по
- 28. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Фигура (граф), которую можно начертить не
- 29. ПУТИ И МАРШРУТЫ В ГРАФАХ Путем в ориентированном графе называется последовательность дуг, в которой конечная вершина
- 30. В качестве примера рассмотрим орграф, представленный на рисунке. Одним из существующих путей, соединяющих вершины 1 и
- 31. Неориентированный граф называется связным, если существует хотя бы один путь между каждой парой вершин. Орграф называется
- 32. Путь называется замкнутым, если начальная и конечная вершины совпадают. Замкнутый путь называется циклом, если все его
- 33. Последовательность попарно смежных вершин неориентированного графа, т.е. последовательность рёбер неориентированного графа, в которой вторая вершина предыдущего
- 34. На рисунке HCDFD – маршрут длиной 4. Обозначение: |HCDFD|=4. Маршрут принято задавать как последовательность рёбер, поскольку
- 35. В графе на рисунке (t, s, p, r), (u, s, t, r) – циклы длиной 4,
- 36. Одноместные операции 1. Удаление ребра графа — при этом все вершины графа сохраняются 2. Добавление ребра
- 37. ОПЕРАЦИИ НАД ГРАФАМИ Двуместные операции Объединением графов и называется граф , множество вершин которого , а
- 38. х3 х4 х6 G1 V2 V1 V3 V4 V5 х3 х1 х5 G=G1UG2 х6 х4 х4
- 39. ПРИМЕНЕНИЕ ГРАФОВ С помощью графов упрощается решение математических задач, головоломок, задач на смекалку. дальше
- 40. ПРИМЕНЕНИЕ ГРАФОВ Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
- 41. Использует графы и дворянство. На рисунке приведена часть генеалогического дерева знаменитого дворянского рода Л. Н. Толстого.
- 42. ПРИМЕНЕНИЕ ГРАФОВ Графами являются блок – схемы программ для ЭВМ. дальше
- 43. ПРИМЕНЕНИЕ ГРАФОВ Типичными графами на географических картах являются изображения железных дорог. дальше
- 44. ПРИМЕНЕНИЕ ГРАФОВ Типичными графами на картах города являются схемы движения городского транспорта. дальше
- 45. ВЫВОДЫ Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические
- 47. Скачать презентацию