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