Алгоритм нахождения сильных компонент графа

Шаг 1. G – данный граф. Для G построить матрицу достижимости R. Получить матрицу контрдостижимости Q = R^T.

Шаг 2. Положить С = R Ä Q, где Ä – поэлементное умножение матриц.

Шаг 3. Преобразовать матрицу С к блочно-диагональ-ному виду путем перестановки строк и столбцов. Каждая из диагональных подматриц соответствует сильной компоненте графа G. Останов.

Граф G*= (X*,V *) определяется так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (x_i *, x_j *) существует в G * тогда и только тогда, когда в G существует дуга (x_i, x_j), такая, что x_i принадлежит ком­поненте, соответствующей вершине x_i *, а x_j –компоненте, соответствующей вершине x_j*. Граф G* называют конденсацией графа G.

Пример решения задачи

Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построить граф конденсации.

Решение. Матрица смежности графа имеет вид:

Матрица инцидентности графа имеет вид:

Построим матрицу достижимостей R. Для этого найдем множества достижимостей для каждой вершины графа по формуле (1), используя матрицу смежности А.

Матрица достижимостей графа примет вид:

Найдем сильные компоненты графа. Матрица контрдостижимостей Q = R ^T

Получим матрицу С, осуществив поэлементное умножение матриц R и Q. Матрица С примет вид:

Преобразуем полученную матрицу C к блочно-диагональному виду. Поменяем местами 1-й и 3-й столбцы матрицы.

Поменяем местами 1-ю и 3-ю строчки матрицы, получим

Из преобразованной матрицы видно, что в графе можно выделить три сильные компоненты:

.

Построим граф конденсации, вершинами которого сильные компоненты графа, т. е.

. Так как в исходном графе существует дуга (x₂, x₁), то в графе конденсации будет дуга, связывающая вершины . Дуга (x₂, x₃) позволяет сформировать дугу () графа конденсации. Дуга (x₃, x₄) позволяет сформировать дугу () графа конденсации. Граф конденсации исходного графа примет вид (рис. 7):

Рис. 7

Задание 4

Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построить граф конденсации.

Варианты

ПЛАНАРНЫЕ ГРАФЫ

Во многих случаях не имеет значения, как изобразить граф, поскольку изоморфные графы несут одну и ту же информацию. Однако встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. А так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.

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

А б

Рис. 8. Плоские графы

Рис. 9.

Очевидны следующие утверждения:

1) всякий подграф планарного графа планарен;

2) граф планарен тогда и только тогда, когда каждая его связная компонента – планарный граф.

О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку).

Поиск по сайту: