Задания № 8, 13 · ЕГЭ

Длина маршрута

Как считают длину маршрута в графе

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Длина маршрута

Длина маршрута — число рёбер в маршруте невзвешенного графа или сумма весов всех пройденных рёбер во взвешенном графе. Если маршрут проходит по рёбрам \(e_1,e_2,\ldots,e_k\), то в невзвешенном графе его длина равна \(k\), а во взвешенном — сумме весов этих рёбер.

Как вычисляют длину

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

\[L=\begin{cases}k, & \text{если граф невзвешенный},\\ w_1+w_2+\cdots+w_k, & \text{если граф взвешенный},\end{cases}\]

№

Пример

Маршрут \(A\to B\to C\to D\) содержит три ребра. В невзвешенном графе его длина равна \(3\). Если веса этих рёбер равны \(4\), \(2\) и \(5\), то длина во взвешенном графе равна \(4+2+5=11\).

Не путайте длину и кратчайший путь

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

Проверь себя

Маршрут проходит по рёбрам с весами \(3\), \(7\), \(3\) и затем повторно по ребру с весом \(7\). Какова его длина?

Главное за минуту

Главное

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