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

Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида 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,{a,b},b,{b,c},c,{c,a},a,{a,d}, является цепью, но не является простой цепью.

Путь в орграфе — это последовательность вершин 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.

0 1 1 0

0 0 0 0

E= 0 1 0 1

0 0 1 0

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

0 1 0 1 0 0 1 0 0 1 0 1

0 0 0 0 0 0 0 0 0 0 0 0

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

0 1 0 1 0 0 1 0 0 1 0 1

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

0 1 1 1

0 0 0 0

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

0 1 1 1

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

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

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

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

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