Простая цепь в маршруте

19. Маршрут в графе. Цепь. Простая цепь. Циклический маршрут. Цикл. Простой цикл. Путь и контур в орграфе. Примеры.

Маршрутом в графе G = называется последовательность вершин и рёбер вида v0,e1,v1,e2, . vn-1,en,vn, где vi ∈ V, i ∈ [0,n], ei ∈ E, (vi-1,ei), (vi,ei) ∈ I, i ∈ [1,n]. Вершины v0, vn называются связанными данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn – концом маршрута. Если v0 = vn, то маршрут называют замкнутым. Число n называется длиной маршрута.

Маршрут, в котором все дуги различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Цепь, не являющаяся циклом, называется простой, если в ней нет повторяющихся вершин. Цикл, в котором все вершины, кроме первой и последней, различны, называется простым циклом.

Пример : Маршрут a,,b,,c,,a,, является цепью, но не является простой цепью.

Путь в орграфе — это последовательность вершин v1, v2, …, vn, для которой существуют дуги v1 → v2, v2 → v3, …, vn-1 → vn. Говорят, что этот путь начинается в вершине v1, проходит через вершины v2, v3, …, vn-1, и заканчивается в вершине vn.

Контур — замкнутый путь в орграфе.

20. Достижимость в неориентированном графе. Матрица достижимости, ее нахождение. Компоненты связности графа, их нахождение.

Отношение достижимости является рефлексивным и транзитивным.. Для неориентированных графов это отношение также симметрично и, следовательно, является отношением эквивалентности. В неориентированном графе классы эквивалентности по отношению достижимости называются связными компонентами.

Матрица достижимости простого ориентированного графа — бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Рассмотрим простой связный ориентированный граф G=(V=<1,2,3,4>,E=<(1,2),(1,3),(3,2),(3,4),(4,3)>) Он имеет матрицу смежности E.

Найдем булевы степени этой матрицы

Eквадрат=0 0 1 0 Eкуб=0 1 0 1 Eв четвертой= 0 0 1 0

Получим матрицу достижимости

Е*=E v Eквадрат v Eкуб v E в четвертой=0 1 1 1

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

21. Достижимость и взаимная достижимость в ориентированном графе. Матрицы достижимости и сильной связности, их нахождение. Компоненты сильной связёности, их нахождение.

Для ориентированных графов достижимость должна быть не симметричным отношением. Симметричной является взаимная достижимость.

Вершины v и w ориентированного графа G=(V,E) называются взаимно достижимыми, если в G есть путь из v в w и путь из w в v.

Отношение взаимной достижимости является рефлексивным, симметричным и транзитивным и, следовательно, эквивалентностью на множестве вершин графа. Классы эквивалентности по отношению взаимной достижимости называются компонентами сильной связности или двусвязными компонентами графа.

Источник

Маршруты, цепи, циклы

До 4 баллов за конспект

Определение. Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.

В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин v ₀, v ₁ ,, …, v_k, то вершины v ₀, v_k называют концами маршрута. Если v ₀ = v_k, то маршрут называют замкнутым, в противном случае – незамкнутым.

Определение. Маршрут, в котором нет повторений ребер, называется цепью. Цепь, в которой все вершины различны, кроме, может быть, ее концов называется простой. Замкнутая простая цепь называется простымциклом. Про цепь говорят, что она соединяет свои концы.

Определение. Простой цикл с р вершинами обозначается С_р . Например, граф – это одновременно граф С₃.

Определение. Ориентированная простая цепь называется путем, ориентированный простой цикл называют контуром.

Рассмотрим граф на рис. 11. Маршруты в этом графе будем задавать последовательностью вершин.

Пример маршрута: 1 – 2 – 3 – 5 – 7 – 4 – 3 – 5 – 6 – 2 – 3 – 4.

Пример замкнутого маршрута: 3 – 4 – 5 – 7 – 3 – 4 – 1 – 3.

Пример цепи, соединяющий вершины 6 и 8: 6 – 5 – 3 – 4 – 5 – 7 – 3 – 2 – 6 – 8.

Пример цикла: 5 – 3 – 2 – 6 – 5 – 7 – 4 – 5.

Примеры простых цепей, соединяющих вершины 1 и 6: 1 – 3 – 4 – 5 – 6; 1 – 2 – 6; 1 – 4 – 7 – 8 – 6.

Примеры простых циклов: 3 – 5 – 7 – 4 – 3; 1 – 2 – 6 – 8 – 7 – 4 – 1;

Рассмотрим ориентированный граф на рис. 12. Ориентированные маршруты в этом графе будем задавать последовательностью вершин, проходимых в направлении ориентации дуг.

Пример ориентированного маршрута: 1 ® 2 ® 3 ® 5 ® 2 ® 6 ® 8 ® 5.

Пример замкнутого ориентированного маршрута: 1 ® 4 ® 5 ® 2 ® 6 ® 8 ® 5 ® 2 ® 3 ® 1.

Пример ориентированной цепи: 4 ® 5 ® 7 ® 8 ®5 ® 2.

Пример замкнутой ориентированной цепи: 6 ® 8 ® 5 ® 2 ® 3 ® 1 ® 5 ® 6.

Пример пути, соединяющего вершины 3 и 9: 3 ® 1 ® 4 ® 5® 6 ® 9.

Пример контура: 5 ® 7 ® 4 ® 5.

Определение. Длиной маршрута называют число ребер в нем с учетом повторений.

Определение. Расстоянием между вершинами называют длину кратчайшей цепи, соединяющей эти вершины. Сама такая цепь называется геодезической.

Определение. Самая длинная геодезическая цепь называется диаметром графа. Длину диаметра так же будем называть диаметром и обозначать буквой . Расстояние между вершинами и и v обозначим через d (u, v).

Рассмотрим граф на рис. 11.

d (1, 5) = 2; d (5, 7) = 1; d (4, 9) = 3; d (1, 8) = 3. = 3 и геодезических длины 3 в графе несколько. Например, это геодезические 1 – 2 – 6 – 9 и 1 – 4 – 7 – 8.

Определение. Ярусом вершины v порядка n (обозначение: ), n = 0, 1, 2, … называется множество вершин, находящихся от вершины v на расстоянии n.

Рассмотрим граф на рис.11 и выпишем ярусы вершины 9.

D (9, 0) = <9>; (9, 1) = <6>; (9, 2) = <2, 5, 8>; (9, 3) = <1, 3, 4, 7>.

Определение. Две вершины и и v называются связными, если их соединяет хотя бы одна простая цепь.

Очевидно, что отношение связности — это отношение эквивалентности.

Определение. Граф G (V, E) называют связным, если любые две его вершины можно соединить простой цепью. В противном случае граф называется несвязным.

Несвязный граф состоит из нескольких связных компонент связности. Вершины, входящие в некоторую компонентусвязности образуют класс эквивалентности по отношению связности.

На рис. 13 показан граф, состоящий из четных компонент связности.

Определение. Ориентированный граф называется сильно связным, если любые две его вершины можно соединить путем. Ориентированный граф называется слабо связным, если связен граф, получающийся из данного орграфа заменой всех дуг на ребра. На рис. 14 показаны сильно связный и слабо связный орграфы.

В заключение опишем необходимые и достаточные условия двудольности графа.

Утверждение (Кениг). Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник