Описать ограничения для графа (рисунок 9)

Предмет: Математика
Раздел: Теория графов, оптимизационные задачи (например, задача о потоке, маршрутизации или линейного программирования на графах)

Для данного ориентированного графа с вершинами и дугами, обозначенными как a_i, можно записать ограничения, которые обычно описывают поток через граф или условия маршрутизации.

Обозначим переменные x_i — поток или значение, соответствующее дуге a_i.

Ограничения для графа:

1. Ограничения на потоки в вершинах (условия сохранения потока):

Для каждой вершины сумма входящих потоков должна равняться сумме исходящих потоков, кроме начальной и конечной вершины.

• Для вершины 1 (исток):

 x_1 + x_2 + x_3 = \text{исходящий поток из вершины 1} 

Но так как из 1 есть только исходящие дуги, то поток на входе равен 0, а на выходе сумма потоков по дугам a_1, a_2, a_3.

Можно записать:

 x_1 + x_2 + x_3 = F 

где F — общий поток.

• Для внутренних вершин (например, вершина 2):

Сумма входящих потоков равна сумме исходящих потоков:

 x_1 = x_4 + x_5 + x_{10} 

Аналогично для других вершин:

• Вершина 3:

 x_2 = x_6 + x_7 

• Вершина 4:

 x_3 = x_8 + x_9 

• Вершина 5:

 x_4 = x_{11} + x_{12} 

• Вершина 6:

 x_5 + x_6 + x_{10} = x_{11} + x_{12} + x_{13} 

• Вершина 7:

 x_7 + x_8 = x_{14} + x_{15} 

• Вершина 8:

 x_9 = x_{16} + x_{17} 

• Вершина 9:

 x_{11} + x_{12} = x_{18} + x_{19} 

• Вершина 10:

 x_{13} + x_{14} = x_{19} + x_{20} 

• Вершина 11:

 x_{15} + x_{16} = x_{21} 

• Вершина 12:

 x_{18} + x_{19} = x_{22} + x_{23} 

• Вершина 13:

 x_{20} + x_{21} = x_{24} 

• Для вершины 14 (сток):

Поток на входе равен сумме входящих потоков:

 x_{22} + x_{23} + x_{24} = F 

2. Ограничения на неотрицательность потоков:

Потоки по дугам не могут быть отрицательными:

 x_i \geq 0, \quad i = 1, 2, ..., 24 

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