Количество компонент сильной связности орграфа

[Sverest]

Как найти количество компонент сильной связности орграфа если известна матрица смежности?

[Sonic86]

Пример нахождения разобран в Кристофидесе Теория графов, например. Не знаю, насколько алгоритм общепринятый, но вообще, задача вряд ли сложная, советую пробежаться по книжкам по дискретке.

[Sverest]

А если у меня все вершины сильно связаны с другими, что делать?

[VAL]

Sverest в сообщении #457835 писал(а):

А если у меня все вершины сильно связаны с другими, что делать?

Написать в ответе 1.

[Sverest]

Матрица смежности

$\begin{bmatrix} 0&0&0&0&1&1 \\ 0&1&0&1&0&0\\ 1&1&1&0&1&1\\ 1&1&1&1&1&1\\ 0&0&0&0&0&1\\ 0&1&1&0&1&1\\ \end{bmatrix}$

из вершины $v_1$
$\{v_1\} \cup \{v_5 v_6\} \cup \{v_6,v_2,v_3,v_5,v_6\} \cup \{v_1 v_2 v_3 v_4 v_5 v_6\}=\{v_1 v_2 v_3 v_4 v_5 v_6\}$

в вершину $v_1$

$\{v_1\} \cup \{v_3,v_4\} \cup \{v_3 v_4 v_6 v_2 v_4 \} \cup \{v_1 v_3 v_4 v_5 v_6\}=\{v_1 v_2 v_3 v_4 v_5 v_6\}$

Я правильно хоть решил?
А в ответе писать: "этот орграф является единственной компонентой сильной связности"?

[VAL]

Sverest в сообщении #457926 писал(а):

Матрица смежности

$\begin{bmatrix} 0&0&0&0&1&1 \\ 0&1&0&1&0&0\\ 1&1&1&0&1&1\\ 1&1&1&1&1&1\\ 0&0&0&0&0&1\\ 0&1&1&0&1&1\\ \end{bmatrix}$

из вершины $v_1$
$\{v_1\} \cup \{v_5 v_6\} \cup \{v_6,v_2,v_3,v_5,v_6\} \cup \{v_1 v_2 v_3 v_4 v_5 v_6\}=\{v_1 v_2 v_3 v_4 v_5 v_6\}$

в вершину $v_1$

$\{v_1\} \cup \{v_3,v_4\} \cup \{v_3 v_4 v_6 v_2 v_4 \} \cup \{v_1 v_3 v_4 v_5 v_6\}=\{v_1 v_2 v_3 v_4 v_5 v_6\}$

Я правильно хоть решил?

Вроде, да

Цитата:

А в ответе писать: "этот орграф является единственной компонентой сильной связности"?

Можно проще: орграф сильно связен.

[Sverest]

Странно в задании было: "Найти количество компонент сильной связности орграфа и определить матрицы смежности этих компонент. Постройте изображения орграфа и его компонент сильной связности."

Как это все сделать если они совпадают