Связный граф
Связный граф — это граф, в котором из любой вершины можно попасть в любую другую по пути, проходящему по рёбрам графа. Иными словами, все вершины графа соединены между собой хотя бы косвенно.
Путь может проходить через несколько промежуточных вершин. Не требуется, чтобы каждая пара вершин была соединена одним ребром: достаточно цепочки рёбер. Например, если вершина \(A\) соединена с \(B\), а \(B\) — с \(C\), то между \(A\) и \(C\) существует путь \(A-B-C\).
Здесь \(V\) — множество вершин, а запись \(u\leadsto v\) означает существование пути из вершины \(u\) в вершину \(v\). Для проверки связности обычно выбирают любую вершину и выполняют поиск в ширину или поиск в глубину. Если удалось посетить все вершины, граф связный. Если некоторые вершины остались непосещёнными, граф несвязный.
В графе есть рёбра \(A-B\), \(B-C\) и \(C-D\). Из \(A\) можно попасть в \(D\) по пути \(A-B-C-D\), а из любой другой вершины — в любую оставшуюся. Следовательно, граф связный.
Связный граф не обязан содержать ребро между каждой парой вершин. Граф, в котором такие рёбра есть, называется полным. Кроме того, в несвязном графе каждая отдельная часть является компонентой связности.
Граф имеет вершины \(A\), \(B\), \(C\), \(D\) и рёбра \(A-B\), \(B-C\). Является ли он связным?
Главное
- Связный граф — граф, в котором между любыми двумя вершинами существует путь.
- Чтобы проверить связность, достаточно запустить поиск из одной вершины и проверить, посещены ли все вершины.
- Если часть вершин недостижима, граф несвязный и распадается на компоненты связности.