Вероятность и статистика · Графы и деревья

Связность, путь, цепь и цикл

Как договориться о терминах обхода графа и находить кратчайшее расстояние.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

Точные различия между маршрутом, путём, цепью и циклом нужны для задач о достижимости, компонентах сети и кратчайшем расстоянии. Без них легко принять число записанных вершин за длину или спутать замкнутый обход с циклом.

Главная идея. Маршрут — последовательность допустимых переходов по рёбрам; цепь не повторяет рёбра, простой путь не повторяет вершины, а цикл замыкает простой путь. Связность означает существование пути, а не прямого ребра.

План рассуждения и проверка понимания

Выпишите последовательность вершин и проверьте, что каждая соседняя пара действительно соединена допустимым ребром нужного направления.
Отметьте повторяющиеся рёбра и вершины, чтобы правильно назвать объект маршрутом, цепью, простым путём или циклом.
Для расстояния посчитайте рёбра кратчайшего простого пути; если пути нет, сначала разделите граф на компоненты связности.

Частая ошибка. Называть граф связным только тогда, когда каждая пара вершин соединена одним ребром, и считать длиной пути количество записанных вершин вместо числа переходов.

Как проверить себя. Для связности достаточно любой последовательности рёбер между вершинами; в записи A–B–C–D четыре вершины, но три ребра, поэтому длина невзвешенного пути равна трём.

Схема к теме

Наглядная модель: Связность, путь, цепь и цикл

Как договориться о терминах обхода графа и находить кратчайшее расстояние.

Связность, путь, цепь и цикл → связность
Связность, путь, цепь и цикл → путь
Связность, путь, цепь и цикл → цепь
Связность, путь, цепь и цикл → цикл

Схема связывает понятие «Связность, путь, цепь и цикл» с его ключевыми признаками. Вывод: Свяжите определение, условия и обозначения: тогда формула станет краткой записью уже понятной идеи.

Проверка пониманияОбъясните тему своими словами

Возьмите маршрут с повторным посещением вершины и объясните, какие повторы нужно удалить, чтобы получить простой путь, и почему удаление петли не мешает достижимости конечной вершины.

В хорошем объяснении есть:

Различены повтор вершины и повтор ребра, а термины использованы согласно статье.
Длина посчитана по рёбрам, а связность не перепутана с полнотой графа.

Последовательность переходов

Маршрут в графе — последовательность вершин, где соседние соединены ребром, вместе с соответствующими рёбрами. Повторения разрешены. Цепью здесь называем маршрут без повторения рёбер; простым путём — маршрут без повторения вершин. Цикл — замкнутый простой путь, у которого совпадают лишь первая и последняя вершины. В простом неориентированном графе цикл содержит хотя бы три ребра.

Терминология разных учебников отличается: слово «путь» иногда допускает повторения. Поэтому в задачах важно уточнение. Длина невзвешенного маршрута — количество пройденных рёбер, а не число записанных вершин.

Связность и компоненты

Граф связен, если между любой парой его вершин есть путь. Если нет, вершины разбиваются на компоненты связности — максимальные связные части. Изолированная вершина тоже образует компоненту. Кратчайший маршрут между достижимыми вершинами можно выбрать простым: петлю с повторным возвращением можно убрать.

Три примера

При рёбрах $AB,BC,CD$ маршрут $A-B-C-D$ имеет длину 3. В записи четыре вершины, но переходов только три.
В треугольнике $AB,BC,CA$ маршрут $A-B-C-A$ — цикл длины 3. Маршрут $A-B-A$ повторяет ребро и не является цепью.
В графе с рёбрами $AB,BC,DE$ и отдельной вершиной $F$ три компоненты: $\{A,B,C\}$ , $\{D,E\}$ и $\{F\}$ .

Частые ошибки

Связность не требует ребра между каждой парой — достаточно последовательности переходов. Замкнутый маршрут не обязательно цикл: он может многократно посещать вершины и рёбра. Если рёбра имеют веса, кратчайший по числу рёбер путь может оказаться не самым коротким по расстоянию или времени. В ориентированном графе дополнительно учитывается направление каждого перехода.

Формула, смысл и ограничения

Главные формулы с расшифровкой

d(u,v)=\min\{\text{число рёбер пути из }u\text{ в }v\}

Формула словами: Расстояние в невзвешенном графе; при отсутствии пути расстояние считают бесконечным.

От простого к сложному

Проверьте себя

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

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.