2.1. Весаи длина пути

Иногда дугам графа G сопоставляются (приписываются) числа — дуге ставится в соответствие некоторое число , называемое весом, или длиной, пли стоимостью (ценой) дуги.

При рассмотрении пути , представленного последовательностью дуг за его вес (или длину, или стоимость) принимается число , равное сумме весов всех дуг, входящих в , т.е.

Таким образом, когда слова «длина», «стоимость», «цена» и «вес» применяются к дугам, то они эквивалентны по содержанию, и в каждом конкретном случае выбирается такое слово, которое

Рис. 1.3.

ближе подходит по смыслу и совпадает с принятым в литературе.

Длиной (или мощностью) пути называется число дуг, входящих в него.