- Компонента связности графа
-
Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Для ориентированных графов определено понятие сильной компоненты связности
Алгоритм
Для поиска компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным (относительно количества вершин и ребер).
См. также
- Связный граф
- Вполне несвязный граф
- Словарь терминов теории графов
- Компонента сильной связности в орграфе
- Теория перколяции
Ссылки
Видеозапись лекции посвященной связности графов
Для улучшения этой статьи по математике желательно?: - Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Категория:- Теория графов
Wikimedia Foundation. 2010.