ГРАФ ВЗВЕШЕННЫЙ

— граф, в котором каждой дуге и поставлено в соответствие некоторое число с (и), называемое ее весом. Вес дуги может иметь различные физ. или экономич. интерпретации: длина дуги, стоимость или время перемещения по ней, пропускная способность — в экономич. приложениях, вероятность безотказной работы — в теории надежности, напряжение или ток — в электр. цепях, передача звена — в системах автоматического управления. В различных приложениях может принимать положительные и отрицательные, целые и дробные значения. К наиболее известным задачам на Г. в. относятся задача о кратчайшем пути, о максимальном потоке, о кратчайшей связывающей сети, задача о коммивояжере и другие. В некоторых приложениях рассматриваются графы с несколькими весами каждой дуги. Так, напр., в сетевой транспортной задаче каждой дуге может соответствовать два веса — длина дуги и ее пропускная способность.

Лит. см. к ст. Графов теория. В. А. Трубин.