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

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

Вершины
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, иначе выделение компонент связности
закончено.

8

Пример 3.9.

Рис.
3.9

3.5.1. Алгоритм построения произвольного остова

1.
Для каждой компоненты
i графа
выполняем пункты 2 и 3.

2. Строим
частичный подграф, содержащий все n_i
вершин
i-й
компоненты и не содержащий ребер (0-
граф).

3.
Если в текущий частичный граф включены
уже n_i–1
ребер, то
остов для компоненты i
построен, иначе выбираем очередное
ребро компоненты и пытаемся его включить
в текущий граф.

Если в текущем
графе это не приводит к образованию
цикла, то включаем ребро, иначе – не
включаем.

Ребро считаем
рассмотренным.

Выполняем пункт
3.

13

Пример
3.7

Рис.
3.7

Остов
– это подграф
(частичный граф), который может быть
построен из графа удалением некоторых
ребер и который является деревом.

В общем случае для
графа можно построить несколько остовов.
Для приведенного ниже графа построен
один из возможных вариантов остова.

Пример 3.8.

Рис.
3.8

Для несвязного
графа рассматриваются отдельные его
компоненты. Остов такого графа –
совокупность его компонент.

12

Пример
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₅}

3.4. Алгоритмы
нахождения подграфов

Циклом
называется
замкнутый маршрут в неориентированном
графе. Для ориентированного графа
определяется аналогично понятие контур
– замкнутый
путь.

9

Пример
3.6.
В графе
(рис.3.6) каждому ребру присвоен свой
номер. Выделим соответствующее ему
число циклов. Для нашего примера циклами
C_i
являются замкнутые маршруты, образованные
ребрами :
C₁={1,
2, 5, 4}, C₂={5,
6, 7}, C₃={3,
6, 2}, C₄={1,
2, 6, 7, 4} и т. д. Среди этих циклов найдутся
такие, которые включают в себя другие
циклы. Так, цикл C₄
состоит из
циклов C₁
и C₂ ,
у которых имеется общее ребро 5, не
вошедшее в цикл 4. Говорят, что цикл 4
получен линейной комбинацией циклов 1
и 2, т. е. является линейно зависимым от
них.

Рис. 3.6

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

Присвоим
каждому ребру графа номерj,
j=1,m
и сопоставим
каждому циклу С_i
двоичный
m-разрядный
вектор V_i
,
компоненты
v_ij
которого
определяются следующим образом:
v_ij
=
0, если
ребро j
не входит в цикл
C_i
, v_ij
= 1 – в противном случае.

Тогда
линейной комбинацией векторов V_i
является
результат векторной
операции сложения по модулю два
этих векторов.

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

10

На
языке теории множеств это означает
объединение множеств C_i
без их
пересечения, что соответствует операции
«симметрическая
разность»
двух множеств.

j	1	2	3	4	5	6	7
V1	1	1	0	1	1	0	0
	
V2	0	0	0	0	1	1	1
V4	1	1	0	1	0	1	1

В нашем примере
общим является ребро 5, которое исключено
из цикла 4.

Линейно-независимым
от совокупности
других циклов называется цикл, который
не может быть построен линейной
комбинацией этих циклов.

Максимальное
множество линейно-независимых циклов
образует систему
независимых циклов;
мощность

этого
множества называется цикломатическим
числом. Это
число определяется по формуле Эйлера

=m-n+p
(3.2)

Соседние файлы в папке XLAM

• #
• #

Рассмотрим базовую задачу.
Условие:
Дан неориентированный граф G, имеющий N вершин и M ребер. Чтобы все рассмотренные подходы имели практических смысл, ограничим N<=1000.
Необходимо найти количество компонент связности данного графа. Формат входных данных: В первой строке входного файла находятся N и M, разделенные пробелом. Далее идет M строк, содержащих пару вершин, между которыми находится ребро. Вершины нумеруются с 1.
Формат выходных данный: В единственной строке выдать количество компонент связности графа.

Пример:
input.txt
15 11
1 2
2 3
2 11
10 11
11 12
11 15
4 12
12 13
8 14
7 14
5 6
output.txt
4

1. const int SIZE = 1e3 + 10;
2. vector<int> adj[SIZE];
3. bool usd[SIZE];
4. ...
5. void dfs(int cur) {
6.   usd[cur] = true;
7.   for (int i=0;i<adj[cur].size();++i) {
8.     int nxt = adj[cur][i];
9.     if (!usd[nxt])
10.       dfs(nxt);
11.   }
12. }
13. int connected_components_amount_dfs() {
14.   int cnt = 0;
15.   for (int i=1; i<=n; ++i) {
16.     if (!usd[i]) {
17.       dfs(i);
18.       ++cnt;
19.     }
20.   }
21.   return cnt;
22. }

* This source code was highlighted with Source Code Highlighter.

Граф храним в виде списка смежности(строка 2). Общая сложность решения $latex O(N + M)$.
Решение

2. DSU подобная структура(ленивый подход)
Будем делать конденсацию компоненты в одну вершину. Идея следующая: будем последовательно обрабатывать ребра. Каждая компонента связности будет представлена одной своей вершиной(титульная). При этом неважно какой. По ходу обработки ребер титульная вершина компонент может меняться.
В итоге для нахождения количества компонент связности нужно найти количество титульных вершин.

1. const int SIZE = 1e3 + 10;
2. int p[SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_dsu() {
6.  
7.   scanf("%d %d", &n, &m);
8.  
9.   for (int i=1;i<=n;++i) {
10.     p[i] = i;
11.   }
12.  
13.   for (int i=0;i<m;++i) {
14.     scanf("%d %d", &f, &s);
15.     int par = p[f];
16.     for (int j=1;j<=n;++j) {
17.       if (p[j] == par)
18.         p[j] = p[s];
19.     }
20.   }
21.   for (int i=1;i<=n;++i)
22.     usd[p[i]] = true;
23.   int cnt = 0;
24.   for (int i=1;i<=n;++i) {
25.     if (usd[i]) ++cnt;
26.   }
27.   return cnt;
28. }

* This source code was highlighted with Source Code Highlighter.

Заметим, что сам граф непосредственно вообще никак не хранится. Общая сложность $latex O(M*N)$ 
Решение

3. Система непересекающихся множеств (DSU)
Реализацию, представленную выше можно существенно усовершенствовать. При добавлении нового ребра будем “мерджить меньшее подмножество к большему” + сжимать пути. У emaxx’а рассматривается доказательство того, что ассимптотика обработки одного ребра равна $latex O(alpha (N))$, где $latex alpha (N)$ – обратная функция Аккермана.

1. const int SIZE = 1e3 + 10;
2.  
3. int p[SIZE];
4. int size[SIZE];
5.  
6. int par(int x) {
7.   return p[x] == x ? x : p[x] = par(p[x]);
8. }
9. int connected_components_amount_dsu() {
10.  
11.   scanf("%d %d", &n, &m);
12.  
13.   for (int i=1;i<=n;++i) {
14.     p[i] = i;
15.     size[i] = 1;
16.   }
17.  
18.   for (int i=0;i<m;++i) {
19.     scanf("%d %d", &f, &s);
20.     f = par(f); s = par(s);
21.     if (f != s) {
22.       if (size[f] > size[s])
23.         swap(f,s);
24.       p[f] = s;
25.       size[s] += size[f];
26.     }
27.   }
28.   bool usd[SIZE];
29.   memset(usd, 0, sizeof(usd));
30.   for (int i=1;i<=n;++i)
31.     usd[par(i)] = true;
32.   int cnt = 0;
33.   for (int i=1;i<=n;++i) {
34.     if (usd[i]) ++cnt;
35.   }
36.  
37.   return cnt;
38. }

* This source code was highlighted with Source Code Highlighter.

Как и прежде сам граф не хранится в виде матрицы смежности. Общая сложность $latex O(M * alpha (N))$

4. Алгоритм Флойда.
Этот подход для самых ленивых, правда он требует хранить граф явно в виде матрицы смежности.
Запускаем алгоритм Флойда и строим матрицу достижимости для каждой пары вершин. В результате если первоначально adj[u][v] указывало на наличие ребра между u и v, то после работы алгоритма adj[u][v] будет указывать на наличие пути между u и v. После чего можно написать DFS двумя вложенными циклами.

1. const int SIZE = 1e3 + 10;
2. int adj[SIZE][SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_floyd() {
6.  
7.   for (int k=1;k<=n;++k){
8.     for (int i=1;i<=n;++i){
9.       for (int j=1;j<=n;++j){
10.         if (adj[i][k] + adj[k][j] == 2)    
11.           adj[i][j] = 1;
12.       }
13.     }
14.   }
15.  
16.   int cnt = 0;
17.   for (int i=1;i<=n;++i) {
18.     if (!usd[i]) {
19.       ++cnt;
20.       usd[i] = true;
21.       for (int j=1;j<=n;++j) {
22.         if (adj[i][j] && !usd[j])
23.           usd[j] = true;
24.       }
25.     }
26.   }
27.   return cnt; 
28. }

* This source code was highlighted with Source Code Highlighter.

Алгоритм ужасно долгий, но зато пишется довольно просто. Общая сложность $latex O({ N }^{ 3 }) $
Решение

Собственно пока и все. Мы рассмотрели 3 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.

Сообщения без ответов | Активные темы | Избранное

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения