Определения. Сетью (графом) G может быть назван любой объект, который можно представить как совокупность множества узлов N и множества дуг A

Сетью (графом) G может быть назван любой объект, который можно представить как совокупность множества узлов N и множества дуг A, соединяющих их. G = {N, A}. Каждый элемент множества A есть пара (i, j) элементов множества N. Примеры графического представления сетей и задающих их множеств см. рис. 1.

Узлы также называют вершинами или точками, а дуги - ребрами, звеньями, линиями или ветвями. Граф G конечен, если конечны оба задающие его множества N и A.

Сеть (граф) G ₁, состоящую из узлов и дуг, входящих в сеть G, называют подграфом сети G; то есть G ₁ = {N ₁, A ₁ } - подграф G = {N, A}, если N ₁ N и A ₁ A. Наиболее простое представление сети получается, если использовать в качестве элементов { N }натуральные числа - номера узлов. Тогда каждая дуга характеризуется парой чисел - номерами узлов, которые она связывает.

Однако каждый узел и дуга сети характеризуются еще одной числовой величиной, смысл которой определяется в конкретных задачах. В общем случае такое поставленное в соответствие узлу число называют его интенсивностью d. Узлы называют источниками (если d > 0), стоками (если d < 0) и нейтральными узлами (если d = 0). Таким образом: N = {N₊} {N_-} {N _o }; N₊ = {n: d_n > 0 }, N_- = {n: d_n < 0 }, N_o = {n: d_n = 0 }.

Аналогично, поставленное в соответствие дуге (i, j) число той же природы, что и интенсивность узла, называют пропускной способностью дуги r_ij.

Потоком F = {f_ij: (i, j) A} в сети G называют совокупность величин f_ij - потоков в дугах, удовлетворяющих соотношениям:

f_ij - f_ji = d_i, i N; 0 £ f_{ij £} r_ij. (1)

Здесь первое выражение отражает закон сохранения потока в сети, а второе задает допустимую область изменения потоков в дугах. Во многих задачах на сетях для каждой дуги вводят дополнительную числовую характеристику - обобщенную стоимость c_ij прохождения единицы потока по дуге, не имеющую аналога для узлов. В таком случае может быть поставлена задача об оптимальном по суммарной обобщенной стоимости потоке:

c_ij f_ij ® opt (2)

при одновременном выполнении условий (1). В результате эта задача принимает вид стандартной задачи линейного (если c_ij = const), либо нелинейного (если c_ij = F (f_kl), (k, l) A) программирования.

При решении задач в дальнейшем будут упоминаться методы и алгоритмы.

Метод - путь, способ получения решения; совокупность приемов, операций, направленных на достижение некоторой цели.

Алгоритм - последовательность четко определенных правил (команд) для получения решения за конечное число шагов.

Любой алгоритм - метод; но не любой метод является алгоритмом.