Содержание
- 2. Понятие графа Линейность является характерной чертой большинства современных естественных и искусственных языков. Линейное представление информации(в виде
- 3. В разных задачах удобно использовать чертежи разных типов. Соответственно определенные вариации допускает и определение графа. Неотъемлемыми
- 4. Граф G= (V, E) состоит из конечного множества вершин (или узлов) V и конечного множества ребер
- 5. Например, Рис.1
- 6. На рисунке 1 изображен граф с шестью вершинами, обозначенными цифрами 1,2,3,4, 5,6, и восемью ребрами, обозначенными
- 7. Ребро a связывает вершины 1 и 2; ребра e и f связывают вершины 1 и 4;
- 8. Два ребра, связывающие одну и ту же пару вершин (как e и f), называют параллельными (или
- 9. Иногда в определении графа запрещают наличие параллельных ребер и/или петель, иногда нет. Мы не будем жестко
- 10. Пусть G= (V, E) – некоторый граф. Граф G′= (V′, E′), вершины и ребра которого являются
- 11. Степенью вершины графа называется число ребер графа, инцидентных этой вершине (петли считаются дважды). Степень вершины v
- 12. Так, для графа из примера имеем: δ(1)= δ(2)= δ(3) = 4, δ(4) = 3, δ(5) =
- 13. Несложно убедиться в справедливости следующего соотношения:
- 14. где m– число ребер графа G= (V, E). В самом деле, ребро, соединяющее вершины x и
- 15. В некоторых случаях рассматриваются направленные ребра, которые называют дугами. Для дуги, соединяющей две вершины, указывают, из
- 16. Если все ребра графа направлены, его называют ориентированным графом, или орграфом. В орграфе параллельными считаются дуги,
- 17. Когда говорят, что в ориентированном графе дуга a соединяет вершины x и y, предполагают, что дуга
- 18. На рис. 2 изображен орграф. Из вершины 1 выходят дуги a и b, в нее входит
- 19. Полустепенью исхода вершины орграфа называется число дуг графа, начинающихся в этой вершине; полустепенью захода – число
- 20. Полустепени исхода и захода вершины v обозначаются соответственно через и . Так, для графа на рис.
- 21. Вершины и дуги графа могут быть дополнительно помечены. В этом случае говорят о нагруженном, или взвешенном,
- 22. Маршруты, цепи и циклы Последовательность вершин графа G представляет собой маршрут в этом графе от вершины
- 23. В случае, когда допускаются параллельные дуги, нужно дополнительно указать, по какой дуге из в проходит маршрут.
- 24. На самом деле, поскольку концы дуг определены однозначно, маршрут можно представить последовательностью дуг . Длиной маршрута
- 25. Вообще говоря, и начальная, и конечная вершины могут встретиться на маршруте как промежуточные вершины. Для любой
- 26. Маршрут называется цепью, если каждая дуга встречается в нем не более одного раза, и простой цепью,
- 27. Если начальная вершина маршрута совпадает с конечной, его называют замкнутым. Замкнутый маршрут называется циклом, если он
- 28. Например, в графе на рис.2 маршрут 1a2c3e1, или, короче, ace, является простым циклом. Поскольку параллельных дуг
- 29. Граф, не содержащий циклов, называется ациклическим. Будем говорить, что вершина y достижима из вершины x, если
- 32. На рис. 3 представлен ациклический граф; «жирными» наконечниками отмечены дуги, входящие в базисный граф. Рис.3
- 33. На множестве вершин неориентированного графа G отношение достижимости является отношением эквивалентности. Класс эквивалентности составляют все вершины,
- 34. Неориентированный граф G называется связным, если в нем любые две вершины можно соединить путем. Связный граф
- 35. На рис. 4 изображен граф с четырьмя компонентами связности. Рис.4
- 36. Эйлеровы цепи и циклы На рис. 5 приведена схема мостов в г. Кенигсберге времен Эйлера. Рис.5
- 37. Построим граф задачи, в котором каждой части города соответствует вершина, а каждому мосту– ребро (рис. 6).
- 38. Решение задачи о кенигсбергских мостах сводится теперь к поиску цикла на построенном графе, в который все
- 39. Рассмотрим последовательность «выходов» – «заходов» для вершины из этого цикла. Чтобы у графа имелся эйлеров цикл,
- 40. Таким образом, если на графе имеется эйлеров цикл, степени всех вершин должны быть четными. Граф на
- 41. Следовательно, имеет место следующая Теорема. Связный граф обладает эйлеровым циклом тогда и только тогда, когда степени
- 42. Матрицы смежности и инцидентности Любой ориентированный граф с вершинами и дугами можно задать его матрицей инцидентности
- 43. Для неориентированного графа матрица инцидентности выглядит следующим образом: если дуга инцидентна вершине , и если дуга
- 44. Например, граф на рис. 2 можно задать следующей матрицей инцидентности (дуги упорядочены в алфавитном порядке):
- 45. Графы без параллельных дуг удобно представлять при помощи матриц смежности. Для графа с n вершинами матрица
- 46. Если в графе имеются параллельные дуги, то можно полагать, что значение элемента матрицы смежности равны числу
- 47. Матрица смежности неориентированного графа симметрична. Например, матрицей смежности графа, представленного на рис. 7, служит матрица А.
- 48. В матрице А вершины занумерованы, начиная с левой верхней, по часовой стрелке. Если изменить порядок нумерации
- 49. Обе матрицы представляют один и тот же граф и получаются одна из другой перестановкой строк и
- 50. Матрица смежности ориентированного графа, вообще говоря, несимметрична. Например, следующая матрица является матрицей смежности ориентированного графа
- 52. Пример. Рассмотрим граф на рис. 8. Пути длины 1 представлены дугами. Все пути длины 2 и
- 53. Матрица смежности графа: дает число путей длины1. Ее квадрат:
- 54. Пусть G– ориентированный граф и A– его матрица смежности. Рассмотрим последовательность матриц Зафиксируем пару вершин i
- 55. В самом деле, если длина пути превосходит n– 1, то такой путь проходит через более чем
- 56. Таким образом, если из i в j имеется некоторый путь, то в одной из матриц последовательности
- 57. Бинарные отношения и графы Бинарное отношение R на конечном множестве V может быть представлено ориентированным графом
- 58. Обратно, всякий ориентированный граф без параллельных дуг G задает бинарное отношение R(G) на множестве своих вершин,
- 59. Если R – бинарное отношение на конечном множестве V= {1, 2, …, n}, а G– граф
- 60. Рассмотрим, как связаны свойства отношения R и соответствующего ему графа G=G(R). Отношение R симметрично, если для
- 61. По существу, граф G оказывается неориентированным. Можно считать, что симметричным отношениям отвечают неориентированные графы.
- 62. Антисимметричность отношения R означает, что xRy и yRx влечет x= y и равносильна тому, что две
- 63. Если R– рефлексивное отношение, то есть xRx для любого x∈V, то граф G имеет петлю в
- 64. Отношение R транзитивно, если из xRy и yRz следует xRz. Для графа G это означает, что
- 68. Скачать презентацию