Подструктуры диграфа

2.11.1. Конденсация

Конденсация диграфа D=(V,E) – диграф D^*(S,F), FÍE, вершины которого s₁,s₂,…,s_k соответствуют сильным компонентам диграфа D, а дуга {s_i,s_j}ÍF принадлежит диграфу D^* тогда и только тогда, когда в D существует дуга, источник которой находится в сильной компоненте s_i, а цель – в компоненте s_j.

Конденсация D^* любого диграфа не имеет циклов.

1. Построить матрицу достижимости диграфа R(D).

2. Найти матрицу S(D) = R(D)*R^T(D), где * - оператор поэлементного умножения матриц, Т – операция транспонирования матриц.

3. Перестановкой строк и столбцов привести матрицу S(D) к блочно-диагональному виду, где каждый блок будет соответствовать некоторой сильной компоненте.

2.11.2. База и антибаза диграфа

База диграфа D=(V,E) – наименьшее (относительно включения) подмножество В вершин, удовлетворяющее условию:

любая вершина vÎV-B достижима из какой-либо вершины vÎB.

Базовая компонента – сильная компонента диграфа D=(V,E), в которую не входит ни одна дуга из других сильных компонент. В конденсации D^*=(S,F) таким компонентам соответствуют вершины с нулевыми полустепенями захода.

База и базовые компоненты связаны между собой:

Подмножество В вершин в диграфе D=(V,E) – база, если В состоит из вершин, принадлежащих базовым компонентам, причем в каждую базовую компоненту входит ровно одна вершина из множества В.

1. Построить конденсацию D^*=(S,F) диграфа D=(V,E).

2. Выдилить в конденсации вершины с нулевыми полустепенями захода. Эти вершины будут определять базовые компоненты.

3. Из каждой базовой компоненты выбирается по одной вершине (таким образом, база диграфа может быть определена не единственным образом).

Антибаза диграфа D=(V,E) – наименьшее (относительно включения) подмножество В^’ вершин, удовлетворяющее условию:

любая вершина vÎV достижима из какой-либо вершины uÎV-B^’.

1. Построить конденсацию D^*=(S,F) диграфа D=(V,E).

2. Выделить в конденсации вершины с нулевыми полустепенями исхода.

3. Из каждой компоненты, соответствующей такой вершине, выбирается по одной вершине.