§ 13. Пути в графах

Определения и обозначения

Путь — последовательность вершин графа, в которой каждые соседние вершины соединены ребром. Например, запись A–B–C означает переход из A в B, а затем из B в C; оба нужных ребра должны существовать. Это понятие позволяет описывать возможное движение по графу.

Длина пути — количество рёбер, входящих в путь. В записи A–B–C–D три ребра, поэтому длина пути равна 3, хотя вершин четыре. По длине можно сравнивать, сколько переходов требуется для разных маршрутов.

Простой путь — путь, в котором ни одна вершина не повторяется. Например, A–B–C–D может быть простым, если все его соседние вершины соединены рёбрами и обозначения не повторяются. Простые пути удобно перечислять и анализировать, потому что в них нет возвращений к уже посещённым вершинам.

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

Как это устроено

Чтобы последовательность вершин была путём, нужно проверить каждую пару, стоящую рядом. Например, для A–B–D–E проверяют рёбра AB, BD и DE: одного отсутствующего ребра достаточно, чтобы последовательность перестала быть путём. Проверка нужна потому, что запись задаёт не просто набор посещённых вершин, а непрерывное движение по графу.

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

Начальная вершина стоит первой в записи, а конечная — последней. Так путь из A в D записывают, например, A–B–D, если рёбра AB и BD есть в графе. Порядок важен: запись D–B–A показывает движение в обратном направлении, а в ориентированном графе обратные переходы могут быть запрещены.

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

Чтобы выбрать кратчайший путь, сравнивают длины всех подходящих путей между заданными концами. Если все рёбра равнозначны, достаточно посчитать переходы; если рёбра имеют разные длины, нужно сложить значения на рёбрах каждого маршрута. Например, маршрут из трёх дорог общей длиной 12 может оказаться длиннее маршрута из четырёх дорог общей длиной 9, поэтому число рёбер не всегда решает задачу.

Основные характеристики путей в графе

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

Разбор задач

Задача 1. Для примера задан граф, в котором есть рёбра AB, BD и DE. Нужно проверить последовательность A–B–D–E и найти её длину. Названия рёбер здесь записаны без тире: AB соединяет A и B.

1. Проверяем переход A–B: ребро AB есть.
2. Проверяем переход B–D: ребро BD есть.
3. Проверяем переход D–E: ребро DE есть. Все соседние вершины соединены, значит, последовательность образует путь.
4. Считаем рёбра: AB, BD и DE — всего три.

Ответ: A–B–D–E — путь длины 3.

Задача 2. В заданном для примера графе есть рёбра AB, AC, BC, BD и CD. Запишем все простые пути длины 3 из A в D. Длина 3 означает, что нужно сделать три перехода, а простой путь не должен повторять вершины.

1. Из A можно перейти в B или C, потому что есть рёбра AB и AC.
2. Если первым выбрать B, то для продолжения к D через третью вершину подходит C: получаем A–B–C–D.
3. Если первым выбрать C, можно пройти через B: получаем A–C–B–D. Других вариантов длины 3 из заданных рёбер нет.
4. Проверяем простоту: в обоих путях A, B, C и D встречаются по одному разу, все переходы существуют.

Ответ: A–B–C–D и A–C–B–D.

Задача 3. На дорогах указаны длины: AB = 4, AC = 2, CB = 1, BF = 5, CD = 4, DF = 2, CF = 8. Нужно найти кратчайший путь из A в F. Поскольку дороги имеют разные длины, сравниваем суммы, а не только количество рёбер.

1. Рассматриваем маршруты через доступные соседние города. Например, A–B–F имеет длину 4 + 5 = 9.
2. Маршрут A–C–D–F имеет длину 2 + 4 + 2 = 8.
3. Маршрут A–C–B–F тоже имеет длину 2 + 1 + 5 = 8; прямой вариант A–C–F равен 2 + 8 = 10.
4. Сравниваем найденные суммы: наименьшая равна 8. Здесь два маршрута достигают этой длины.

Ответ: кратчайшие маршруты — A–C–D–F и A–C–B–F, длина каждого равна 8.

Типичные ошибки

Ошибка — считать длиной пути число вершин. Её допускают, потому что при чтении записи внимание часто сосредоточено на обозначениях вершин, а не на переходах между ними. Проверь себя: пересчитай рёбра; у пути из четырёх вершин длина равна трём.

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

Ошибка — считать любой маршрут простым и не замечать повторов. Повтор вершины легко пропустить в длинной записи, особенно если обозначения похожи. Прочитай последовательность по порядку и отметь каждую вершину: в простом пути ни одна отметка не встречается дважды.

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

Связь с другими темами

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

Что запомнить

• Путь состоит из последовательности вершин, соединённых рёбрами.
• Каждая пара соседних вершин пути должна быть соединена ребром.
• Длина пути равна числу пройденных рёбер.
• Первую и последнюю вершины называют концами пути.
• В простом пути вершины не повторяются.
• Кратчайший путь имеет минимальную длину среди всех путей между заданными вершинами.