Теорема

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

Эксцентриситет (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. Достижимость

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