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

2-03-2022, 09:00

Компонента связности графа G {displaystyle G} (или просто компонента графа G {displaystyle G} ) — максимальный (по включению) связный подграф графа G {displaystyle G} .

Другими словами, это подграф G ( U ) {displaystyle G(U)} , порождённый множеством U ⊆ V ( G ) {displaystyle Usubseteq V(G)} вершин, в котором для любой пары вершин u , v ∈ U {displaystyle u,vin U} в графе G {displaystyle G} существует ( u , v ) {displaystyle (u,v)} -цепь и для любой пары вершин u ∈ U {displaystyle uin U} , w ∉ U {displaystyle w otin U} не существует ( u , w ) {displaystyle (u,w)} -цепи.

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

Алгоритм

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


  • Плюрисубгармоническая функция
  • Задача изоморфизма порождённому подграфу
  • Ядро (теория графов)
  • Хеммингова сфера
  • Симметричное отношение

  •  

    • Яндекс.Метрика
    • Индекс цитирования