Компонента связности графа
Материал из Википедии — свободной энциклопедии
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 26 сентября 2012;
проверки требуют 6 правок.
Несвязный граф с тремя компонентами связности
Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Для ориентированных графов определено понятие сильной компоненты связности
Алгоритм [править]
Для поиска компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным (относительно количества вершин и ребер).
См. также [править]
- Связный граф
- Вполне несвязный граф
- Словарь терминов теории графов
- Компонента сильной связности в орграфе
- Теория перколяции
Ссылки [править]
Видеозапись лекции посвященной связности графов
 |
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
 |
Для улучшения этой статьи по математике желательно?:
|
