Содержание
- 2. Понятие графа Графы представляют объекты и связи между ними, например: города и дороги, люди и знакомства,
- 3. Множество вершин графа всегда считается непустым, в то время как множество ребер может быть пустым (графы
- 4. Примеры графов
- 5. Инцидентность и смежность Если ребро х соединяет вершины u и v , то говорят, что вершины
- 6. На рисунке вершины u и v соединены ребром кратности 3, на вершине w имеется петля, а
- 7. Степень вершины Число ребер, инцидентных вершине А, называется степенью вершины А и обозначается deg(A) (от англ.
- 8. Теорема 1. В графе G(V, Х) сумма степеней всех его вершин — число четное, равное удвоенному
- 9. Теорема 2. Число нечетных вершин любого графа — четно. Следствие. Невозможно начертить граф с нечетным числом
- 10. Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром.
- 11. Если все пары (Vi, Vj) во множестве X являются упорядоченными, т.е. кортежами длины 2, то граф
- 13. Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления. Например,
- 14. Маршруты и пути Последовательность попарно инцидентных вершин Vi1 ,Vi2, ..., Vik неориентированного графа, т.е. последовательность ребер
- 15. Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии,
- 16. В орграфе маршрут является ориентированным и называется путем. На путь сразу налагаются важные требования, являющиеся частью
- 17. Связность Вершины u и v графа G связаны, если в G существует (u, v )-маршрут. Граф,
- 18. Эйлеров цикл Цикл, содержащий все ребра графа, называется эйлеровым. Граф называется эйлеровым, если в нем существует
- 19. Задача о 7 мостах Кёнигсберга Как можно пройти по всем семи мостам Кёнигсберга, не проходя ни
- 20. Степени всех вершин этого графа нечетны. Из теоремы Эйлера о циклах вытекает, что обойти Кенигсберг, пройдя
- 21. Алгоритмы для построения эйлеровой цепи
- 22. Пусть на шаге 1 выбрана вершина v1. На шаге 2 ограничение никак не сказывается; пусть выбрано
- 23. Текущим графом становится граф, изображенный на рисунке (текущая вершина — v6). Далее выбрать ребро (v6, v3)
- 24. Гамильтонов цикл Цикл, проходящий через каждую вершину графа ровно один раз, называется гамильтоновым. Граф называется гамильтоновым,
- 25. Задача коммивояжера Дан список городов, соединенных дорогами, длины которых известны. Коммивояжер должен объехать все города, побывав
- 26. Операции над графами Подграфом графа G = (V , Х) называется граф G′=(V′, Х′) такой, что
- 28. Операции удаления вершин и ребер Если х — произвольное ребро графа G , то удаление ребра
- 29. Примеры удаления вершин и ребер графа
- 30. Операция объединения графов Пусть G1 = (V1, Х1), G2 = (V2, Х2), . . . ,
- 31. Операция пересечения графов Пусть G1 = (V1, Х1), G2 = (V2, Х2) - графы, не имеющие
- 32. Дополнением графа G (V, X) называется граф с теми же вершинами V, что и граф G,
- 33. Матрица смежности Пусть G — граф, а v1, v2, . . . , vn — множество
- 34. Два графа равны (алгебраически), если равны их матрицы смежности.
- 35. Взвешенный граф - граф (орграф), ребрам (дугам) которого приписаны веса. Иногда изображается в виде пары ,
- 36. Пример:
- 37. Главное удобство матрицы смежности — в том, что ответ на вопрос, существует ли ребро, инцидентное двум
- 38. Списки смежности Пусть G — граф, а v1, v2, . . . , vn — множество
- 39. Матрица инциденций (инцидентности) Матрицей инциденций ориентированного графа G (X, U) называется прямоугольная матрица порядка[n * m],
- 40. Пример:
- 41. Для неориентированного графа aij определяется следующим образом: равен 1, если вершина xi инцидентна ребру uj; равен
- 42. Списки инцидентности Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности. Список инцидентности
- 43. Деревья Деревом называется связный граф без циклов. Теорема. (cвойства деревьев): 1. G связен и не содержит
- 44. Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно
- 45. Алгоритм Краскала (построение кратчайшего остовного дерева) Выбираем самое короткое ребро графа х1, затем ребро х2, самое
- 46. Пример: построить минимальное остовное дерево.
- 50. Алгоритм Дейкстры для нахождения минимального пути в графе Дан взвешенный орфограф G(V,E) без дуг отрицательного веса.
- 51. Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то,
- 53. Скачать презентацию