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

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

Рассмотрим базовую задачу.
Условие:
Дан неориентированный граф 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

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

Задача стара, как мир. Но тем не менее сегодня покажу несколько подходов по ее решению.

1. Поиск в глубину(DFS)
Самое классическое решение. Даже комментировать особо нечего.

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. >

Граф храним в виде списка смежности(строка 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. >

Заметим, что сам граф непосредственно вообще никак не хранится. Общая сложность $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. >

Как и прежде сам граф не хранится в виде матрицы смежности. Общая сложность $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. >

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

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

2.1. Компоненты сильной связности ориентированного графа

Cоставляем матрицу смежности A(D) размерности (N− количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины Vi и входящая в Vj, то элемент матрицы смежности, стоящий на пересечении I-той строки и J-того столбца равен 1, иначе – 0.).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.

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

1. Присваиваем P=1 (P − количество компонент связности), .

2. Включаем в множество вершин Vp Компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.

3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то P— количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем P=P+1 и переходим к п. 2.

Пример

Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин N=5.

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:

Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:

Присваиваем P=1 и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .

Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине V1, чтобы получить матрицу S2(D):

Присваиваем P=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:

Вычеркиваем из матрицы S2(D) строки и столбцы, соответствующие вершинам из V2 ,чтобы получить матрицу S3(D), которая состоит из одного элемента:

И присваиваем P=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .

Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:

В графе 18 вершин, причём степень каждой вершины равна 2 или 5, вершины обеих степеней присутствуют. Сколько компонент связности может быть в таком графе?

Так как в графе есть хотя бы одна вершина степени 5, есть хотя бы одна компонента с вершиной данной степени. Рассмотрим её. Кроме вершины степени 5 в этой компоненте не менее 5 вершин. Значит, в компоненте связности с вершиной степени 5 не менее шести вершин. Аналогично, в компоненте связности с вершиной степени 2 не менее трёх вершин. Значит, компонент не более 1 + (18 — 6) : 3 = 5.

Докажем, что любое количество компонент от 1 до 5 быть может. Сперва построим пример для 5 компонент. Пусть в одной компоненте две вершины степени 5 соединены ребром, а остальные вершины — вершины степени 2, присоединённые к обоим. Итого 6 вершин на одну компоненту. Остальные компоненты связности представлены циклами длины 3 из вершин степени 2.

Если требуется от 2 до 4 компонент, «склеим» две компоненты-цикла в одну, увеличив цикл.

Если требуется одна компонента, построим компоненту из шести вершин по примеру выше, а затем вместо ребра, соединяющего вершины степени 5, проложим путь из вершин степени 2.

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

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

Неорграф называется связным, если любая пара вершин в нем связана. Орграф называется связным, если соответствующий ему неорграф связен. Орграф называется сильно-связным, если для любой пары несовпадающих вершин v_i и v_j существуют оба маршрута (v_i ‑ v_j) и (v_j ‑ v_i).

Бинарное отношение связности в неорграфе (сильной связности в орграфе) является отношением эквивалентности на множестве вершин, поскольку оно рефлексивно, симметрично и транзитивно. И по теореме о разбиении множества на классы эквивалентности, множество вершин графа можно разбить на такие непересекающиеся подмножества, что в каждом из этих подмножеств вершины будут попарно связаны между собой и не связаны с вершинами никаких других подмножеств. Вершинно-порожденные подграфы каждого из подмножеств в этом разбиении называются компонентами графа (сильными компонентами в орграфе). Таким образом, справедливо следующее утверждение: любой неорграф разбивается единственным образом на попарно непересекающиеся компоненты (или, как говорят, в прямую сумму своих компонент, а орграф – в прямую сумму сильных компонент).

На рисунке 26 изображены два графа: неорграф (слева) связным не является и состоит из четырех компонент – <1,2,3>, <4,5>, <6,7,8>и <9>. Орграф (справа) связен, но не сильно-связен, имеет три сильные компоненты – <1,2,3>, <4>и <5>.

Свойства связных графов

1) Связный граф состоит из одной компоненты, а число компонент в несвязном графе всегда больше единицы.

2) Изолированная вершина является компонентой.

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

4) Удаление циклического ребра не нарушает связности графа.

Связный граф без циклов называется деревом. Граф, каждая компонента которого является деревом, называется лесом. На рисунке 27 изображен лес, состоящий из двух деревьев.

Теорема 3.9.1. (Оценка числа ребер в простых графах)

Пусть G =(V, E) – простой граф с в вершинами и k компонентами. Тогда число его ребер р удовлетворяет неравенству:

Доказательство: 1) рассмотрим левую часть неравенства. Если граф связен, то число его компонент k равно 1. Удалим из графа все циклические ребра, в результате этого будет получено дерево. Дальнейшее удаление ребер из дерева будет нарушать связность. Поэтому среди всех связных простых графов дерево имеет наименьшее число ребер. Но число ребер в дереве равно максимальной длине пути, построенного на в вершинах, и по свойствам путей равно (в ‑1). Тем самым, в связном графе число ребер р ³ в ‑1, что совпадает с оценкой снизу при k =1. Пусть теперь G несвязный граф. Тогда он разбивается на k связных компонент, для каждой из которых число ребер р_i ³ в_i ‑1, где i =1,2,¼, k и р_i, в_i – это число ребер и вершин в i‑ ой компоненте. Но и , а . Поэтому р ³ в‑k, и левая часть неравенства доказана.

2) Теперь рассмотрим правую часть неравенства (оценку сверху). Если граф связен, то добавим к нему новые ребра, соединяя все пары несмежных вершин. В результате этого будет получен полный граф. Дальнейшее добавление ребер к полному графу будет нарушать его простоту. Поэтому среди всех связных простых графов полный граф имеет наибольшее число ребер. Для подсчета этого числа воспользуемся теоремой о степенях вершин в графе. Поскольку каждая вершина полного графа смежна со всеми остальными его вершинами, то степень каждой вершины равна (в‑ 1), а сумма степеней всех вершин равна в ×(в ‑1). По теореме о степенях вершин это число равно удвоенному числу ребер, поэтому число ребер в полном графе равно . И число ребер в связном графе р £, что совпадает с оценкой сверху при k =1. Пусть теперь G – несвязный граф. Тогда число ребер в каждой i‑ ой компоненте р_i £. Однако, простое суммирование этого неравенства по числу компонент, как это было сделано в первом пункте доказательства, ничего не даст, поэтому выполним над графом следующую процедуру. Выберем произвольно две компоненты: i‑ ую и j‑ ую. Можно считать, что число вершин выбранных компонент в_i ³ в_j > 1. Заменим i‑ ую компоненту на полный граф с числом вершин (в_i +1), а j‑ ую компоненту – на полный граф с числом вершин (в_j ‑1). Общее число вершин в выбранных компонентах при этом не изменится, а число ребер изменится на величину, равную

Таким образом, выполненная процедура только увеличивает число ребер. Будем выполнять её над выбранными компонентами до тех пор, пока от j‑ ой компоненты не останется одна изолированная вершина. Затем выберем другую пару компонент с числом вершин больше единицы в каждой. И выполним над этой парой такую же процедуру. И т.д. до тех пор, пока не будет получен граф, в котором с (k ‑1) компонента являются изолированными вершинами и одна компонента – полный граф на (в ‑ k +1) вершинах. Число ребер в полученном графе равно , и оценка сверху доказана.

Следствие. Любой простой граф с в вершинами и числом ребер, большим, чем связен.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: