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

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

  • автор:

Компонента связности графа

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

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

Алгоритм

Для поиска компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным (относительно количества вершин и ребер).

См. также

  • Связный граф
  • Вполне несвязный граф
  • Словарь терминов теории графов
  • Компонента сильной связности в орграфе
  • Теория перколяции

Ссылки

  • Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
  • Теория графов

Wikimedia Foundation . 2010 .

  • Жадный алгоритм Радо — Эдмондса
  • Связный граф

Полезное

Смотреть что такое «Компонента связности графа» в других словарях:

  • Компонента сильной связности графа — Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две пары вершин s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными… … Википедия
  • Компонента — Компонент (от лат. componens, родительный падеж componentis составляющий) составная часть, элемент чего либо. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике сложилось употребление в… … Википедия
  • ГРАФА СВЯЗНОСТЬ — одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к рых (вместе с… … Математическая энциклопедия
  • ГРАФА АВТОМОРФИЗМ — изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. группой… … Математическая энциклопедия
  • Компонента сильной связности в орграфе — Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.… … Википедия
  • Связность графа — Связный граф граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует по крайней мере один путь. Содержание 1 Примеры применения 2 Связность для орграфов … Википедия
  • Компонент — Компонента составная часть чего либо целого. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике Компонента связности Компонента связности графа Компонента вектора или тензора, см.… … Википедия
  • КС — Компонента связности графа Конституционный суд Контактная сеть Counter Strike Кубок Стэнли Корреспондентский счёт (к/с) Качугин, Солодовников (по другим данным Керосиновая смесь) Координационный совет Кран Самоходный (см. также Подъёмный кран#По… … Википедия
  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Научный форум dxdy

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

Re: Число компонент связности
26.07.2018, 18:55
Можете выписать определения компоненты связности и связного графа?
Re: Число компонент связности
26.07.2018, 19:27

Последний раз редактировалось gogoshik 26.07.2018, 20:14, всего редактировалось 5 раз(а).

'$

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

https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png$

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

https://dxdy-04.korotkov.co.uk/f/b/7/1/b7120a8b9c08ac2d9901bf619d5af13782.png^*$

Определение . Компонентой связности называется класс эквивалентности относительно связности.

Определение https://dxdy-03.korotkov.co.uk/f/2/4/2/24297faf22c5ee6d9ea69ef348c48ba582.png^*^*$. Рассмотрим подграфы $G_i(V_i, E_i)$графа $G$, порожденные множествами $V_i$, т.е. для $u, v \in V_i $выполняется $\left\lbrace u, v \right\rbrace \in E_i \Leftrightarrow \left\lbrace u, v \right\rbrace \in E$. Так как любые две вершины из $V_i $связаны путем в $G$, то этот путь будет связывать их и в $G_i$. Следовательно, $G_i$— связный граф. Нетрудно проверить, что множества $E_i $образуют разбиение множества $E$(возможен случай $E_i = \varnothing$для некоторых $i$, в этом случае $G_i(V_i, E_i)$— тривиальный) и для графа $G$будет выполняться $G(V, E) = G_1(V_1, E_1) \sqcup . . . \sqcup G_k(V_k, E_k)$— дизъюнктное объединение графов $G_1(V_1, E_1), . . . , G_k(V_k, E_k)$. При этом подграфы $G_1, . . . , G_k$называются компонентами связности графа $G$.

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

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

Поиск компонент связности

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

Граф с тремя компонентами связности

Граф на иллюстрации содержит три компоненты связности, закрашенные разными цветами. Можно заметить, что даже одна вершина, изолированная от остального графа, составляет компоненту связности.

Общее понятие связности распространяется только на неориентированные графы. Для описания ориентированных графов используются понятия сильной и слабой связности, но они выходят за границы материала этой лекции.

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

Для поиска компонент связности используется обычный DFS практически без модификаций (можно использовать и BFS). При запуске обхода из одной вершины, он гарантированно посетит все вершины, до которых возможно добраться, то есть, всю компоненту связности, к которой принадлежит начальная вершина. Для нахождения всех компонент просто попытаемся запустить обход из каждой вершины по очереди, если мы ещё не обошли её компоненту ранее.

Реализация

Приведём два варианта реализации с разным способом хранения компонент связности.

Простейший вариант: просто заполнить массив \(comp\), где \(comp[i]\) — номер компоненты связности, к которой принадлежит вершина \(i\).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36


#include  using namespace std; vectorint> graph[100000]; bool used[100000]; int comp[100000]; void dfs(int v, int c_num)  //c_num - номер текущей компоненты связности. used[v] = true; comp[v] = c_num; for (int u: graph[v])  if (!used[u])  dfs(u, c_num); > > > int main()  //Ввод графа. int c_num = 1; //Номер очередной компоненты. //Нумеровать можно как с 0, так и с 1, как вам удобнее. for (int i = 0; i  n; i++)  if (!used[i])  //если мы ещё не посетили эту вершину, обходя одну из предыдущих dfs(i, c_num); c_num++; > > for (int i = 0; i  n; i++)  cout  <"Vertex "  <i + 1  <" belongs to component "  <comp[i]  <endl; > > 


Другой вариант: явно хранить для каждой компоненты вектор из вершин, входящих в неё. Компоненты (векторы) хранить в векторе (из векторов).








1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40


#include  using namespace std; vectorint> graph[100000]; bool used[100000]; vectorvectorint>> comps; void dfs(int v)  //информацию о компоненте в DFS больше передавать не нужно, //он просто будет добавлять вершины в последний вектор в comps. used[v] = true; comps.back().push_back(v); for (int u: graph[v])  if (!used[u])  dfs(u); > > > int main()  //Ввод графа. for (int i = 0; i  n; i++)  if (!used[i])  comps.push_back(vectorint>()); //добавляем в comps новый пустой вектор, //в который DFS будет записывать посещённые вершины. dfs(i); > > for (vectorint>& comp: comps)  cout  <"Component: "; for (int v: comp)  cout  <v + 1  <", "; > cout  <endl; > > 


brestprog


Олимпиадное программирование в Бресте и Беларуси


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


Данный код считает максимальную компоненту связности. Как найти их количество? 
Например, 
3 
0 0 0 
0 0 1 
0 1 0 
Эта программа выводит 3, а количество будет равно 2.








    

  • Вопрос задан более трёх лет назад
    • 

  • 4507 просмотров
    • 



Комментировать








Решения вопроса 0


Ответы на вопрос 2


Rsa97


Для правильного вопроса надо знать половину ответа


Выбираете первую вершину графа, отмечаете её и все связанные с ней точки (прямо или чрез другие вершины). Получаете первую компоненту. Выбираете следующую непомеченную вершину графа, от неё получаете вторую компоненту и т.д., пока не останется непомеченных вершин.


Ответ написан более трёх лет назад


Нравится 2  2 комментария





Похожие публикации:
    

  1. Как проверить подлинность наушников airpods
    2. 

  2. Как сделать так чтобы компьютер видел принтер
    3. 

  3. Как удалить в реестре ссылки на параметры
    4. 

  4. Какие мосты ставят на уаз буханка
    5.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *