Маршрут в графе
Маршрут в графе — это последовательность вершин и рёбер, по которым можно двигаться от одной вершины к другой. Чтобы правильно решать задачи, важно различать маршрут, цепь и путь: эти понятия отличаются тем, какие вершины и рёбра разрешено повторять.
Что такое маршрут
Сначала вспомним устройство графа: вершины обозначают точки или объекты, а рёбра — связи между ними. Подробно это разобрано на странице «Граф и его элементы». В неориентированном графе по ребру можно двигаться в любом направлении, а в ориентированном — только по направлению стрелки.
Маршрут — это последовательность вершин \(v_0,v_1,\ldots,v_k\), в которой каждые соседние вершины соединены ребром графа. В маршруте разрешено повторять и вершины, и рёбра.
Например, запись \(A\to B\to C\to B\to D\) задаёт маршрут, если в графе есть рёбра \(AB\), \(BC\), \(CB\) и \(BD\). Вершина \(B\) здесь встречается дважды, а ребро \(BC\) фактически используется в прямом и обратном направлениях. Для неориентированного графа это допустимо.
Первая вершина маршрута называется началом, последняя — концом. Число пройденных рёбер называется длиной маршрута. Если маршрут записан через \(k+1\) вершин, его длина равна \(k\).
Не следует путать длину маршрута с количеством различных вершин. Повторная остановка в уже посещённой вершине снова увеличивает длину на единицу. В задачах на длину маршрута это правило применяется напрямую.
Маршрут, цепь и путь
Маршрут — самое общее понятие. Из него получают более строгие виды движения, добавляя ограничения на повторы.
| Вид движения | Что нельзя повторять | Что можно повторять |
|---|---|---|
| Маршрут | Ничего не запрещено | Вершины и рёбра |
| Цепь | Рёбра | Вершины |
| Простой путь | Вершины | Ничего из вершин; рёбра также не повторяются |
Цепь — маршрут, в котором каждое ребро используется не более одного раза. Вершина при этом может встретиться повторно, если движение входит в неё по одному ребру, а выходит по другому.
Простой путь — маршрут, в котором никакая вершина не повторяется. Поэтому в простом пути автоматически не повторяются и рёбра.
Любой простой путь является цепью, а любая цепь является маршрутом. Обратные утверждения неверны: маршрут может содержать повторы, а цепь может вернуться в уже посещённую вершину.
Если движение является простым путём, то оно является и цепью, и маршрутом. Если движение является цепью, то оно является маршрутом. Маршрут не обязан быть цепью или простым путём.
На изображённом графе \(A\to B\to C\to D\) — простой путь длины 3. Последовательность \(A\to B\to E\to B\to C\) — цепь длины 4: ребро \(BE\) используется один раз, но вершина \(B\) повторяется. Последовательность \(A\to B\to E\to B\to A\) — маршрут, но не цепь: ребро \(AB\) пройдено дважды, сначала от \(A\) к \(B\), затем обратно.
Какой из вариантов является простым путём?
Как проверять запись маршрута
При решении задания проверяйте запись в определённом порядке. Сначала убедитесь, что каждая пара соседних вершин соединена ребром и что направление движения разрешено. Затем посчитайте переходы — это длина. После этого ищите повторы и определяйте вид движения.
- Выпишите вершины по порядку: \(v_0,v_1,\ldots,v_k\).
- Проверьте каждую пару \(v_i,v_{i+1}\) по рисунку, списку или матрице смежности.
- Посчитайте количество переходов между соседними вершинами.
- Отметьте повторяющиеся рёбра: если их нет, движение является цепью.
- Отметьте повторяющиеся вершины: если их нет, движение является простым путём.
Подчёркивайте вершины и рёбра при проверке. Если вершина уже встречалась, поставьте рядом второй знак; если повторилось ребро, это сразу исключает цепь.
Разобранный пример
Пусть в графе есть рёбра \(AB\), \(BC\), \(CE\), \(EB\), \(BD\) и \(DA\). Рассмотрим запись \(A\to B\to C\to E\to B\to D\) и определим её вид и длину.
Показать решение Решение
Запись задаёт цепь длины 5, потому что ни одно ребро не повторяется. Это не простой путь, поскольку вершина \(B\) встречается дважды. Одновременно это, конечно, маршрут: цепь является частным случаем маршрута.
Замкнутые маршруты и ориентированный граф
Если начало и конец совпадают, маршрут называют замкнутым маршрутом. Например, \(A\to B\to C\to A\) замкнут, а \(A\to B\to C\to D\) — нет. Замкнутый маршрут может быть обычным маршрутом, замкнутой цепью или более специальным циклом — это зависит от повторов рёбер и вершин.
В ориентированном графе одного наличия пары вершин недостаточно: нужно проверить стрелку. Переход \(A\to B\) разрешён, если есть дуга именно из \(A\) в \(B\). Обратный переход \(B\to A\) может быть запрещён. При работе с матрицей смежности это означает проверку элемента в нужной строке и столбце, а при списке смежности — поиск следующей вершины в списке исходящих дуг.
1. Считать длиной число вершин, а не число рёбер. 2. Считать, что повтор вершины запрещает любой маршрут: он запрещён только для простого пути. 3. Путать повтор вершины с повтором ребра: цепь допускает первое, но запрещает второе. 4. В ориентированном графе идти против стрелки. 5. Проверять только начало и конец, не проверяя каждый соседний переход.
Как находить маршрут по условию
В задачах может требоваться найти маршрут заданной длины, перечислить все пути или выяснить, можно ли попасть из одной вершины в другую. Для небольшого графа удобно перебирать варианты по шагам: после каждой вершины записывать все доступные продолжения, а затем отбрасывать варианты, нарушающие условие.
Если требуется простой путь, помечайте уже использованные вершины и не возвращайтесь к ним. Если требуется цепь, помечайте рёбра, но повторное посещение вершины допускайте. Для больших графов используют алгоритмы поиска в глубину или ширину, однако на экзамене обычно достаточно аккуратного перебора по схеме графа.
Длина = число переходов. Маршрут допускает все повторы; цепь запрещает повтор рёбер; простой путь запрещает повтор вершин.
Проверьте себя
Главное
- Маршрут — последовательность соседних вершин; повторять можно и вершины, и рёбра.
- Длина маршрута равна числу пройденных рёбер, то есть числу переходов.
- Цепь не повторяет рёбра, но может повторять вершины.
- Простой путь не повторяет вершины и потому автоматически не повторяет рёбра.
- В ориентированном графе каждый переход нужно проверять с учётом направления стрелки.