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

• Рассматривается теория графов, а именно нахождение компонент сильной связанности в ориентированном графе.  

• Описывается алгоритм для нахождения компонент сильной связанности.  

• Ориентированный граф задается матрицей смежности, где единица означает наличие дуги.  

• Матрица смежности всегда квадратная, каждая строка и столбец соответствуют вершине.  

• Пример ориентированного графа с дугами между вершинами.  

• Показаны компоненты сильной связанности, но для больших графов это может быть сложно.  

• Алгоритм состоит из построения матрицы достижимости, матрицы обратной достижимости, матрицы сильной связности и выделения компонент.  

• Матрица сильной связности получается путем почленного умножения матриц достижимости и обратной достижимости.  

• Матрица достижимости строится путем установки единиц, если из вершины можно попасть в другую.  

• Пример построения матрицы достижимости для ориентированного графа.  

• Матрица транспонируется для построения матрицы сильной связности.  

• Матрица сильной связности анализируется для выделения компонент сильной связанности.  

• Единицы в первой строке матрицы сильной связности соответствуют вершинам, сильно связанным с первой вершиной.  

• Компоненты сильной связанности выделяются путем вычеркивания строк и столбцов с единицами.  

• Конденсат графа строится путем объединения компонент сильной связанности.  

• Пример построения конденсата графа для ориентированного графа.  

• Пример построения матрицы достижимости для графа с матрицей смежности 8x8.  

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

• Пример построения матрицы достижимости для графа с матрицей смежности 6x6.  

• Все вершины графа достижимы, что означает, что граф сильно связан.  

• Из третьей строки попадаем в первую, дублируем строчки с первой строки.  

• Из четвертой строки попадаем в пятую, из пятой - во вторую.  

• Из пятой строки попадаем в первую, вторую и первую, дублируем единички с первой строки.  

• Из шестой строки попадаем в первую, дублируем единички с первой строки.  

• Записываем транспонированную матрицу и берем их произведения по членам.  

• В третьей позиции появляется ноль, аналогично во второй строке.  

• В первой матрице строка из единиц ничего не добавляет, а во второй матрице строка из единиц не дает ничего нового.  

• Переписываем три строчки, ориентируясь на первую матрицу.  

• В первую компоненту отправляем все вершины, которым соответствуют единицы в первой строке, кроме третьей.  

• Третья вершина остается изолированной.  

• Во вторую компоненту отправляем единственную оставшуюся вершину.  

• Строим конденсат графа: к1, к2 и стрелочки.  

• Из к2 идет ребро в первую компоненту, но не наоборот, чтобы не было сильно связанного графа.  

• Тема не сложная, важно быть аккуратным и придумать удобный алгоритм для проверки достижимости.