Иногда дугам графа сопоставляют числа ai сi , называемые весом или длиной, или стоимостью или ценой. В каждом конкретном случае выбирается то слово, которое ближе подходит по смыслу задачи.
Граф G, описываемый тройкой вида
G = (X, A, С),
где Х = { хi }, i =1, 2, 3, ..., n – множество вершин,
А = { ai }, i = 1, 2, 3, ..., m – множество дуг,
С = {Ci}, i = 1, 2, 3, ..., m – множество характеристик дуг, называется графом со взвешенными дугами.
Пример такого графа приведен на рис. 8.2,а. При рассмотрении пути M, представленного последовательностью дуг(a1, a2, ..., aq), за его вес (или длину, или стоимость) принимается число L(M), равное сумме весов всех дуг, входящих в путь, т. е. L(M)= (ci) для всех ai M.
Длиной (или мощностью) пути называется число дуг, входящих в него. Чаще всего термин "длина" употребляется, когда все дуги, входящие в путь, имеют веса, равные 1, т. е. когда вес пути совпадает с его длиной (мощностью).
Рис. 8.2. Взвешенные графы: а – граф со взвешенными дугами; б – граф со взвешенными вершинами; в – взвешенный граф
Граф со взвешенными вершинами – это граф, описываемый тройкой
G = ( X, А, V ),
где Х = { хi }, i = 1, 2, ..., n – множество вершин графа;
А = { ai }, i = 1, 2, ..., m – множество дуг графа;
V ={ vi }, i = 1, 2, ..., n – множество характеристик вершин.
В качестве характеристик вершин могут выступать "стоимость", "мощность", "вес" и т. п. Пример такого графа приведен на рис. 8.2,б. Для графа со взвешенными вершинами в случае представления пути последовательностью вершин весом пути является сумма весов, входящих в этот путь вершин.
И наконец, взвешенный граф определяется четверкой вида G = (Х, А, V, С), т. е. и дуги, и вершины этого графа имеют некоторые характеристики.
Область применения взвешенных графов в качестве моделей довольно обширна: транспортные задачи, задачи оптимизации сети связи и системы перевозок и др. Одной из известнейших оптимизационных задач является нахождение кратчайших путей в графе со взвешенными дугами.