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

Компонента связности графа $G$ (или просто компонента графа $G$ ) — максимальный (по включению) связный подграф графа $G$ .^[1]^[2]^[3]

Несвязный граф с тремя компонентами связности

Другими словами, это подграф $G(U)$ , порождённый множеством $U\subseteq V(G)$ вершин, в котором для любой пары вершин $u,v\in U$ в графе $G$ существует $(u,v)$ -цепь и для любой пары вершин $u\in U$ , $w\notin U$ не существует $(u,w)$ -цепи.

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

Алгоритм править

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

См. также править

Ссылки править

Видеозапись лекции посвященной связности графов

Примечания править

↑ Харари Ф. Теория графов / Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. С. 27.
↑ Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. — М.: Наука. Гл. ред. физ.-мат. лит., 1990. C. 24.
↑ Дистель Р. Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. С. 24.

[1] Харари Ф. Теория графов / Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. С. 27.

[2] Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. — М.: Наука. Гл. ред. физ.-мат. лит., 1990. C. 24.

[3] Дистель Р. Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. С. 24.

[1]

[2]

[3]