Матрица сильной связности

Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 достижима из этой вершины, то в соответствующем этой вершине столбце ставим 1, в противном случае 0; по аналогии заполняем остальные строки.

Замечание. По матрице сильной связности можно выписать компоненты сильной связности.

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

Рассмотрим строку X1: вычеркнем столбцы, в которых стоят единицы X1, X2, X3.

Теперь вычеркнем строки: X1, X2, X3.

При пересечении столбцов X1, X2, X3 и строк X1, X2, X3 получилась таблица, т.е. вершины X1, X2, X3 сильно связны между собой и образуют компоненту сильной связности.

Далее рассмотрим оставшиеся невычеркнутые строки: X4 и X5.

Вычеркиваем в строке X4 столбец, в котором стоит единица X4. Теперь вычеркиваем строку X4. При пересечении строки X4 и столбца X4 получили

Вывод X4 - компонента сильной связности. Проделав аналогичную операцию для строки X5, получим X5 - компонента сильной связности.

Итак, у графа G три компоненты сильной связности.

5. Операции над графами (объединение, пересечение).

Определение. Объединением графов называется граф, у которого объединены множество вершин и множество дуг графов . Обозначение .