Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

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

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

Рис. 1.3.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление