23. Понятие сильной связности. Анализ сильной связности с помощью алгоритмов поиска на графах.

Связность графа. Отыскание компонент связности при графическом задании графа.

Г раф (ор-граф) называется связным (сильно связным), если любая пара его вершин соединяется хотя бы одной цепью.

- сильно связан - слабо связан

Возьмем ор-граф и уберем стрелки, тогда получим неор. граф, о котором говорят, что он ассоциирован с данным. Ор-граф называется слабосвязным, если ассоциированный с ним граф является связным. Максимально связанный (сильно связанный) подграф данного графа называется компонентой связности (сильной связности). Очевидно, если граф G имеет Р компонент связности G1,G2,G3,…,Gp, то число вершин графа G равно числу компонент связности. Если граф неор., то число его ребер равно сумме ребер его компонент связности.

Рассмотрим алгорит выделения компонент связности для неор. графа и этот же алгоритм даст возможность определить, будет ли граф связным. Этот алгоритм может работать и для выделения компонент слабой связности графа.

1) возьмем какую-нибудь вершину, 2) запишем все вершины, ей смежные, получим список, 3) к каждой вершине списка пункта 2 присоединяем смежные вершины, причем если вершина уже есть в списке, то ее уже не пишем, список при этом дополняется, 4) к полученным вершинам снова добавляем смежные к ним, не вошедшие в список, и так до тех пор, пока список не будет расширяться. При этом если в список вошли все вершины графа, то граф связный, в противном случае м ы выделим одну компоненту связности. Тогда берем любую вершину, не вошедшую в первую компоненту связности и повторяем алгоритм.

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

Транзитивное замыкание в теории множеств — это операция на бинарных отношениях. Транзитивное замыкание бинарного отношения R на множестве X есть наименьшее транзитивное отношениена множестве X, включающее R.

Например, если X — это множество людей (и живых, и мёртвых), а R — отношение «является родителем», то транзитивное замыкание R — это отношение «является предком». Если X — это множество аэропортов, а xRy эквивалентно «существует рейс из x в y», и транзитивное замыкание R равно P, то xPy эквивалентно «можно долететь из x в y самолётом» (хотя иногда придётся лететь с пересадками)

25. Понятие сильной связности. Анализ сильной связности с помощью алгоритма нахождения транзитивного замыкания.

Алгоритмы

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

1. При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.

2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.

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

Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.

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