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

Взвешенный граф

Граф, в котором рёбра имеют длины, стоимости или другие числовые характеристики

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

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

Взвешенный графСлово «взвешенный» связано с понятием веса — числовой оценки ребра.

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

Вес маршрута

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

\[w(P)=w(e_1)+w(e_2)+\dots+w(e_k)=\sum_{i=1}^{k}w(e_i)\]1

Здесь \(P\) — маршрут, \(e_1, e_2, \dots, e_k\) — его рёбра, а \(w(e_i)\) — вес соответствующего ребра. Такое значение называют длиной маршрута или его суммарным весом.

№

Пример

Пусть маршрут из вершины A в вершину D проходит по рёбрам A—B с весом 4, B—C с весом 2 и C—D с весом 5. Общий вес маршрута равен \(4+2+5=11\). Если веса обозначают километры, маршрут имеет длину 11 км; если рубли — стоимость 11 рублей в условных единицах.

Не путайте

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

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

Маршрут проходит по рёбрам с весами 3, 7 и 2. Чему равен его общий вес?

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

Главное

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