Связность графа
Связность графа показывает, можно ли попасть из одной вершины в другую, двигаясь по рёбрам. В этой теме разберём проверку достижимости вершин и алгоритм выделения компонент связности — групп вершин, соединённых путями.
Основные понятия
Граф состоит из вершин и рёбер, соединяющих некоторые пары вершин. В задачах экзамена чаще всего рассматривают неориентированные графы: по каждому ребру можно двигаться в обе стороны. Перед решением полезно вспомнить, что такое простой путь: это последовательность вершин, в которой соседние вершины соединены рёбрами, а вершины не повторяются.
Две вершины неориентированного графа называются связанными, если существует путь из одной вершины в другую. Иначе вершины несвязны.
Вершина \(v\) достижима из вершины \(u\), если существует маршрут из \(u\) в \(v\). В неориентированном графе достижимость симметрична: если \(v\) достижима из \(u\), то и \(u\) достижима из \(v\).
Граф называется связным, если любые две его вершины связаны путём. Если хотя бы для одной пары вершин путь отсутствует, граф несвязный. Подробнее термин разобран на странице «Связный граф».
Отдельная вершина без рёбер образует связный граф сама по себе: из неё в неё можно попасть путём длины \(0\). Поэтому изолированная вершина является отдельной компонентой связности.
Компоненты связности
Компонента связности — это максимальное множество вершин, в котором любая вершина связана с любой другой. Максимальность означает, что нельзя добавить в это множество ещё одну вершину графа, сохранив свойство связности. См. также страницу «Компонента связности».
Компоненты связности не пересекаются: каждая вершина принадлежит ровно одной компоненте. Все рёбра графа соединяют вершины внутри одной компоненты, потому что ребро само является путём длины \(1\). Между разными компонентами рёбер нет.
Компоненты связности разбивают множество вершин графа на непересекающиеся группы. Граф связен тогда и только тогда, когда у него ровно одна компонента связности.
В графе есть вершины 1, 2, 3, 4. Рёбра: 1–2 и 2–3. Сколько компонент связности?
Как проверить достижимость
Чтобы проверить, достижима ли вершина \(t\) из вершины \(s\), можно начать с \(s\) и последовательно переходить по рёбрам в ещё не посещённые вершины. Все найденные вершины помечают. Если в процессе встретилась \(t\), путь существует; если поиск закончился, а \(t\) не отмечена, пути нет.
Такой обход выполняют поиском в ширину или поиском в глубину. Для школьных задач удобно мыслить по алгоритму поиска в ширину: сначала рассматриваются вершины на расстоянии одного ребра, затем на расстоянии двух и так далее. Для самого факта достижимости порядок обхода не важен.
- Выбрать начальную вершину \(s\) и отметить её.
- Рассмотреть все рёбра из отмеченных вершин.
- Отметить каждую ещё не отмеченную соседнюю вершину.
- Повторять шаги 2–3, пока появляются новые вершины.
- Проверить, отмечена ли целевая вершина \(t\).
где \(R(s)\) — множество вершин, которые удалось посетить, начиная из \(s\). Если граф представлен матрицей смежности, в строке вершины \(u\) проверяют столбцы \(v\): значение \(1\) означает наличие ребра \(u\)–\(v\).
Отметьте стартовую вершину кружком или галочкой и каждый раз обводите всех её ещё не отмеченных соседей. Не проходите одну и ту же вершину повторно: это не меняет достижимость и только увеличивает риск ошибки.
Выделение компонент связности
Чтобы найти все компоненты, одного обхода недостаточно, если граф несвязный. После завершения обхода из одной вершины выбирают любую ещё не посещённую вершину и запускают новый обход. Все вершины, найденные за один запуск, составляют одну компоненту.
1visited := пустое множество 2components := 0 3для каждой вершины s: 4 если s не посещена: 5 components := components + 1 6 запустить обход из s 7 при обходе отмечать все достигнутые вершины 8вывести components
Обход из вершины \(s\) посещает все и только те вершины, которые связаны с \(s\). Поэтому он выделяет одну компоненту целиком и не захватывает вершины других компонент. Каждый новый запуск начинается в другой компоненте, а после обработки всех вершин число запусков равно числу компонент связности.
Разобранный пример
Дан неориентированный граф с вершинами \(1,2,3,4,5,6,7\) и рёбрами \(1\)–\(2\), \(2\)–\(3\), \(4\)–\(5\), \(5\)–\(6\). Требуется определить число компонент и проверить достижимость вершины 7 из вершины 1.
Составим списки соседей: у 1 сосед 2; у 2 — 1 и 3; у 3 — 2; у 4 — 5; у 5 — 4 и 6; у 6 — 5; у 7 соседей нет.
Показать решение Разбор
Ответ: компоненты связности — \({1,2,3}\), \({4,5,6}\) и \({7}\); число компонент равно \(3\); вершина 7 из вершины 1 недостижима.
Частые ошибки
Наличие ребра между двумя вершинами — частный случай пути, но путь может содержать много рёбер. Если из 1 можно попасть в 2, а из 2 — в 3, то 3 достижима из 1, даже если прямого ребра 1–3 нет.
Один обход отвечает на вопрос о вершинах, достижимых из выбранного старта, но не всегда находит весь граф. Для числа компонент нужно запускать обход из каждой ещё не посещённой вершины.
Вершина без рёбер всё равно является компонентой связности из одной вершины. Её нельзя пропускать при подсчёте.
Для ориентированного графа направление стрелок важно: достижимость из \(u\) не обязана означать достижимость из \(v\). Правила этой страницы относятся прежде всего к неориентированным графам.
Связанные идеи
Если связный граф не содержит циклов, он является деревом. Удаление некоторых рёбер может разделить граф на компоненты; особенно важны рёбра, называемые мостами. Для задач, где требуется пройти по рёбрам в определённом порядке, понадобятся замкнутый маршрут и цепь в графе, но сама связность отвечает только на вопрос о существовании пути.
Быстрая проверка
Главное
- Две вершины связаны, если между ними существует путь; достижимость проверяют обходом графа.
- Компонента связности — максимальная группа попарно связанных вершин.
- Чтобы найти все компоненты, запускают обход из каждой непосещённой вершины.
- Число запусков обхода равно числу компонент связности.
- Изолированная вершина образует компоненту из одной вершины.
- Граф связен тогда и только тогда, когда у него одна компонента.