Нахождение компонент связности

Вершины x_i и x_j слабо связны, если в графе существует путь (x_i, x_j).

Вершины x_i и x_j сильно связны, если существуют пути (x_i, x_j) и (x_j, x_i).

Если в графе нет путей из x_i в x_j и нет обратного пути из x_j в x_i, то вершины x_i и x_j несвязны. Для неориентированного графа имеет смысл только понятие сильной связности.

Компонентой связности называетсямаксимальное подмножество сильно связанных между собой вершин.

Отношение связностирефлексивно, симметрично, транзитивно, т. е. является отношением эквивалентности, и однозначно разбивает множество вершин графа на компоненты связности.

Пример 3.4: Задан граф (рис.3.4). Найти его компоненты связности.

	Данный граф может быть разбит на следующие компоненты связности: 1){x1,x2,x3,x4}; 2){x5,x6,x7}; 3){x8} Между компонентами - только слабая связность: есть пути из вершин 1-й компоненты в вершины 2-й и 3-ей компоненты, а также из вершин 2-й компоненты в вершину 3-ей.

Рис. 3.4

 

 

Алгоритм построения компонент связности

В неориентированном графе

1. i= 0. Все вершины графа не отмечены.

2. i=i +1. Выбираем очередную неотмеченную вершину, отмечаем её и все связанные с нею вершины значением индекса i с помощью распространения волны отметок по ребрам, идущих от уже отмеченных индексом i вершин. Таким образом выделяется i компонента связности. Если есть ещё неотмеченные вершины, то выполняется п.2, иначе выделение компонент связности закончено.

Пример 3.5

Рис. 3.5

Решение:

1. i=0

2. i=1. Отмечаем индексом i=1 вершину x₁ и связанные с ней вершины x₃, x₇ и x₉. Получена первая компонента связности: k₁ {x₁,x₃,x₇,x₉ }

2. i= 2. Отметим индексом i =2 вершину x₂ и вершины x₆,x₁₀ . Построена вторая компонента связности: k₂ {x₂,x₆,x₁₀}

2. i= 3. Отмечаются индексом i= 3 вершины x₄ и x₈. Построена третья компонента связности: k₃ {x₄, x₈ }.

2. i= 4. Отмечаются индексом i= 4 вершину x₅, которая формирует четвертую компоненту связности – k₄ {x₅}