2.11.1. Конденсация
Конденсация диграфа D=(V,E) – диграф D*(S,F), FÍE, вершины которого s1,s2,…,sk соответствуют сильным компонентам диграфа D, а дуга {si,sj}ÍF принадлежит диграфу D* тогда и только тогда, когда в D существует дуга, источник которой находится в сильной компоненте si, а цель – в компоненте sj.
Конденсация D* любого диграфа не имеет циклов.
1. Построить матрицу достижимости диграфа R(D).
2. Найти матрицу S(D) = R(D)*RT(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. Из каждой компоненты, соответствующей такой вершине, выбирается по одной вершине.