|
Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[aij] порядка n, где
Матрица инцидентности графа G называется матрица B(G)=[bij] порядка nm, где
Графы G1(V1, X1) и G(V2, X2) называются изоморфными, если существует биекция f: V1→V2, такая, что выполнено:
При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G на себя называется автоморфизмом.
Контрольные вопросы.
1. Что такое граф и орграф?
2. Дайте понятие матрицы смежности. Приведите пример.
3. Как строятся матрицы достижимостей и контрадостижимостей?
4. Что такое граф сигналов? Как рассчитываются узловые сигналы в
таком графе?
5. Что такое передача графа? Как она рассчитывается?
6. Каковы основные термины и определения для неориентированных графов?
7. Каковы основные термины и определения для ориентированных графов?
8. В чем различие гамильтонова и эйлерова графов?
9. Как строится матрица смежности?
10. Как строится матрица инциденций?
Лекция 21. Маршрут, цепь, цикл в ориентированных графах (2 часа)
План:
1. Основные понятие
2. Эйлеровы циклы и цепи
3. Гамильтоновы циклы. Оценка временной сложности алгоритмов
Ключевые слова: Маршрут, цепь, цикл, Эйлеровы циклы и цепи, Гамильтоновы циклы
Пусть G — конечный граф. Маршрутом S в G называется последовательность ребер,
S = (u1, u2, …, un), (1)
в которой любые соседние два ребра ui-1, ui, (i = 2, n) имеют общую вершину.
На графах допускаются маршруты, в которых не принимаются во внимание направления ребер. Такие маршруты называются неориентированными.
Пусть на графе определен маршрут (1). Та вершина ребра u1, которая не является общей с вершиной ребра u2, называется начальной вершиной маршрута S.
Аналогично вводится понятие конечной вершины маршрута: та вершина ребра un, которая не является общей с вершиной un-1, называется конечной вершиной маршрута S.
Остальные вершины маршрута S называются внутренними.
Нуль‑маршрутом называется маршрут, не содержащий ребер.
Вершина uj называется достижимой из вершины ui, если существует маршрут из ui в uj. Для определенности считают, что любая вершина ui достижима из себя нуль-маршрутом независимо от наличия петель.
Неориентированный граф называется связным, если все его вершины попарно достижимы.
Неориентированный граф называется соотнесенным, если он получен из ориентированного либо смешанного графа заменой всех дуг на неориентированные ребра.
Ориентированный либо смешанный граф называется связным, если связен соответствующий ему соотнесенный граф.
Ясно, что отношение достижимости, построенное на ребрах графа, является отношением эквивалентности и разбивает любой граф на классы связных подграфов.
Маршрут называется цепью, если все его ребра различны и — простой цепью, если все его вершины различны
Цепь называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла — замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.
Началом (концом) цикла можно считать любую из его вершин.
На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла — понятие контура.
Путь — это ориентированная цепь. Контур — это замкнутый путь. Рассмотрим примеры различных маршрутов на графе G, представленном на рисунке 1.
v1
u5
v4 u4 v3 u1 u2
u3 v2
u 6
u7 v5
Рисунок 1.
Маршрут (u4, u1, u2) является простой цепью.
Маршрут (u4, u1, u2, u3, u1 ) цепью не является, поскольку ребро u1 встречается в нем дважды. Маршрут (u4, u3, u2, u1) представляет цепь, но не простую, поскольку вершина v3 встречается на ней дважды: как начало ребра u1 и как конец ребра u3. Такая цепь содержит в себе цикл. В данном случае в цепи (u4, u3, u2, u1) имеем цикл (u3, u2, u1 ). Этот цикл простой. Примером не простого цикла может служить маршрут (u1, u2, u3, u7, u6, u5 ).
Существенный интерес в теории графов, а также для приложений представляют маршруты, которые образуют эйлеровы и гамильтоновы циклы и цепи. Такие маршруты рассматриваются нами ниже.
Do'stlaringiz bilan baham: |
