Поиск сильносвязных компонентов в ориентированном графе

Алгоритм определения транзитивного замыкания.

Обход графа в глубину.

Псевдограф

Мультиграф

Простой граф – без кратных ребер и без петель.

Ориентированный граф – все дуги.

Смешанный – ребра и дуги.

Взвешанный или нагруженный – каждому ребру соответствует число, называемое его весом.

Сеть – взвешенный орграф.

Маршрут – последовательность вершин и ребер, в которой каждая вершина кроме последней соединена со следующей.

Путь – маршрут в орграфе.

Длина маршрута – число составляющих ребер графа не сост или сумма весов для взвешенного.

Цикл – цепь, в которой первая и последняя вершина совпадают.

Цепь – маршрут, в котором нет одинаковых ребер.

Простой путь – нет повторов.

Контур – цикл в орграфе.

Ациклический граф - граф без циклов.

Эйлеров цикл – цикл, проходящий по каждому ребру ровно один раз.

Связный граф – в котором существует путь из любой вершины в любую.

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

Две вершины достижимы.

Полный граф – граф, в котором любые две вершины соединены ребром.

Насыщенный граф или плотный – число ребер близко к квадрату его порядка.

Разреженный или ненасыщенный – число ребер намного меньше квадрата порядка.

Способы представления графа.

Матрица смежности или матрица примыканий – матрица, у которой число строк и столбцов равно числу вершин, а на пересечении i-строки с j-столбцом стоит 1, если данные вершины связаны. Больше 1 – для мультиграфов; +2 – для каждой петли.

Матрицы инцидентности – количество строк равно количеству вершин, а количество – количеству ребер. Если вершина концевая, то -1, иначе +1.

Матрица весов – на основе инцидентности, если в нее вместо единичек поставить веса.

Списки примыкания – количество списков равно количеству вершин. Порядковый номер для начала каждого списка. Строятся списки связности.

Заносятся в стек посещенные вершины, помечаются флажками. Если посещали вершину, флаг меняется.

1, 2, 3, 4, 5, 6, 7, 8, 9.

Узлы первого уровня.

1 – 2, 8 – 3, 5 – 4, 6 – 9, 10, 7.

При программировании использовать лучше очередь, а не стек.

Транзитивное замыкание – обозначается со *.

У матрицы А строится матрица А² – будет содержать 1-ки в тех точка на пересечении i-строки и j-го столбца, между которыми есть путь длины не более 2. Для того, чтобы найти n³. Трудоемкость n*n³. O(n³*log n). Умножение заменяется на операцию «И», сложение на «ИЛИ». Алгоритм Уоршелла.

Матрицы связности – матрица связности будет содержать единичку в том случае, если из i-вершины в j-ю есть путь, è ставится единичка.

15.04.2010 г.

Сильно-связные компоненты – граф или подграф, в котором из каждого узла есть путь в каждый. Для того, чтобы найти сильно-связные компоненты нужны матрица достижимости, матрица контр достижимости и матрица взаимной достижимости.

R = ||r_ij||

Q = ||q_ij||

H = ||h_ij||

Матрицы взаимной достижимости.

V3

Пример.

V6

V5

V7

V4

V2

V1

1111000

Дата добавления: 2014-01-05