Длина (вес) ребра графа

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

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

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

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

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

Пример графа с подписанными длинами рёбер и соответствующая ему весовая матрица показаны на рисунке.

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

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