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

Говорят, что вершина 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 дерево как список вершин сильной компоненты диграфа.