Теорема

Каждая дипрогулка содержит дипуть.

Эксцентриситет (u) вершиныuдиграфаD=(V,A) определяется какмаксимальный из возможных всех путейот этой вершины до всех остальных вершин диграфа.

Эксцентриситеты вершин диграфа образуют вектор, максимальный элемент которого равен диаметруDдиграфа, а минимальный –радиусу Rнаправленного мультиграфа.

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

Класс сложности

Проблема нахождения максимального пути в диграфе относится к NP-тяжелым.

2.6. Типы связности диграфа.

Говорят, что вершина vдиграфаD(V,E) достижимаиз вершиныu, если (u,v)- дипрогулка.

При этом вершина uконтрдостижимаиз вершиныv. Любая вершина считается достижимой да самой себя.

Вершины vиuдиграфаDвзаимодостижимы, если вершинаvдостижима из вершиныu, и вершинаuдостижима из вершиныv.

Различают следующие типы связностидиграфов:

-сильно связный (сильный)диграф, если любые две вершины в нём взаимодостижимы;

-одностороннесвязный (односторонний)диграф, если для каждой пары его вершин, по крайней мере, одна достижима из другой;

- слабосвязный (слабый)диграф, если неограф основания этого диграфа будет связным.

Пример

a

b

Если [A] матрица связности диграфаDсnвершинами, а [B]- матрица вида

[B]=[A]+[A]²+[A]³+…+[A]^n-1 ,

то диграф D,будет сильно связным тогда и только тогда, когда каждый недиагональный элемент матрицыBбольше 0.

В диграфе различают следующие типы компонент:

сильная компонента- максимальный сильно связанный подграф исходного диграфа;

односторонняя компонента– максимальный односторонне связанный подграф исходного диграфа;

слабая компонента – максимальный слабо связанный подграф исходного диграфа.

Алгоритм использует два обхода в глубину(DFS), один для диграфаD=(V,E) и один для обратного диграфаD^-1(V,E^-1).

Множество вершин деревьев обхода в глубину, полученного из обхода для D^-1(V,E^-1) является сильными компонентами (одна компонента из каждого дерева).

Алгоритм:

1. Выполнить DFSдля того, чтобы получитьвремена завершенияf[u],uV.

2. Построить обратный диграф D^-1(V,E^-1).

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

4. Рассматривать каждое DFSдерево как список вершин сильной компоненты диграфа.

3.7. Достижимость

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

Матрица достижимости r(u,V) задается следующим образом:

Решение проблемы достижимости диграфа требует полиномиального времени, т.е. относится к Р-классу.

Построить матрицу достижимости можно с помощью алгоритма BFS, выполнив его из каждой вершины диграфаD(V,E).

Сложность – О(n(n+m).

• Начало BFS– вершина 1.

• Исследуются все вершины {1,y}A. Из вершины 1 доступны вершины 2 и 4. Эти вершины заносятся в специальную запись

String={2,4}.

• Затем исследуются все вершины {2,y}A. Из вершины 2 доступны вершины 3 и 5, которые заносятся в специальную запись:

String= {2,3,4,5}.

• Исследуются все вершины {4,y}A. Из вершины 4 доступна только вершина 5. Т.к. такая вершина уже есть в специальном списке, то запись остается неизменной.

• Следующими вершинами будут {3,y}A. Из вершины 3 доступна вершина 6. Эта вершина заносится в специальный список:

String={2,3,4,5,6}.

• Рассматриваются вершины {5,y}A. Доступными будут вершины 2 и 6, которые есть в специальном списке.

• Следующие вершины будут {6,y}A. Доступная вершина – вершина 5, которая имеется в специальном списке.

• BFSиз вершины 1 завершен. В результате выполненияBFSсформирована специальная запись

String={2,3,4,5,6},

которая показывает вершины, доступные из вершины 1.

• Данная запись позволяет записать первую строку матрицы достижимости:

(0 1 1 1 1 1).

• Если повторить BSFиз всех оставшихся вершин диграфа, то результатом будет следующая матрица достижимости:

Матрицу смежности A(D) диграфа можно рассматривать какбулевскую матрицу, т.к. элементыA(D) равны нулю или единице.

Матрица достижимости вычисляется следующим образом:

R(D) = A(D)  A²(D)  …  A^n-1, |V|=n,

где - операция поэлементного булевского сложения строк матрицA(D),

A²(D), … , A^n-1;

Для облегчения вычисления степеней матриц A²(D), … ,A^n-1осуществляется с использованием булевских операций (умножение заменяется на, а сложение – на).

Сложность алгоритма – О(n⁴).