Page 59 - 4386

6.1 Нормалізований граф, вага шляху

Іноді дугам графа e призначують дійсні числа с , які
i
i
називаються значенням вартості. Число с описує, наскільки
i
важко пройти дугу із однієї вершини в іншу, також його можна

інтерпретувати у сенсі грошової вартості або розглядати як

геометричну довжину, час переходу тощо. У кожному

конкретному випадку вибирається саме те тлумачення с , яке
i
ближче підходить до змісту конкретної задачі. У певних

практичних задачах можуть виникати від'ємні значення вартості:

для прикладу, транспортний засіб, що рухається із одного пункту

в інший, витрачає чи заробляє під час цього гроші; тож грошові

витрати можна вважати додатною вартістю, а прибуток –

від'ємною.

Дуги графа e , яким призначені дійсні числа с називаються
i
i
зваженими.

Граф G, що описується трійкою вигляду G=(V, E, С), де

С={с }, i=1, 2, 3, ..., m – множина характеристик дуг, називається
i
нормалізованим графом або графом зі зваженими дугами.

Приклад такого графа наведений на рис. 6.2.

Рисунок 6.2 – Нормалізований граф

58