Построение ориентированного графа (орграфа) сети

ЗАДАЧА 2

Условие

Система автодорог представлена двухполюсной транспортной сетью. Определить, чему равен максимальный поток автомашин (количество машин в час) для данной системы автодорог, если пропускные способности дорог заданы в матрице.

Таблица 1

Построение ориентированного графа (орграфа) сети

Задача сводится к отысканию максимального значения потока в двухполюсной транспортной сети, которая задана матрицей пропускных способностей (табл. 1).

Построим орграф, соответствующий матрице пропускных способностей двухполюсной транспортной сети (табл.1). Каждый элемент этой матрицы равен пропускной способности дуги u_ij, если из вершины x_i выходит дуга в вершину x_j, и 0 – в противном случае.

Над каждой дугой проставим ее пропускную способность, а в скобках – начальное значение потока, равное нулю (0) (рис. 1). Тогда величина потока в цепи равна нулю: V = 0.

Рис. 1

1.Рассмотрим цепь (s x ₁ x ₂ t).

Цепь является увеличивающей, так как все дуги, входящие в нее допустимые (увеличивающие):

(s x ₁) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 9.

(x ₁ x ₂) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 6.

(x ₂ x _t) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 10.

Следовательно, данная цепь увеличивающая.

2. Вдоль дуги (s x ₁) поток можно увеличить на величину

= 9 - 0 = 9.

Вдоль дуги (x ₁ x ₂) поток можно увеличить на величину

= 6 - 0 = 6.

Вдоль дуги (x ₂ x _t) поток можно увеличить на величину

= 10 - 0 = 10.

3. δ = min{9, 6, 10} = 6. Вдоль цепи (s x ₁ x ₂ t) поток можно увеличить на δ = 6, увеличивая его на δ = 6 по каждой увеличивающей дуге (рис. 2). Дуга (x ₁ x ₂) стала насыщенной.

Рис. 2

После такого изменения, величина потока стала равной

V = 0+6 = 6:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 6 + 0 = 6 и V_t = 6 + 0 = 6.

Условие сохранения потока выполняется.

1. Рассмотрим цепь (s x ₁ x ₄ t).

Цепь увеличивающая, так как все дуги допустимые (увеличивающие):

(s x ₁) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 6 < 9.

(x ₁ x ₄) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 3.

(x ₄ t) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 7.

2. Вдоль дуги (s x ₁) поток можно увеличить на величину

= 9 - 6 = 3.

Вдоль дуги (x ₁ x ₄) поток можно увеличить на величину

= 3 - 0 = 3.

Вдоль дуги (x ₄ t) поток можно увеличить на величину

= 7 - 0 = 7.

3. δ = min {3, 4, 7} = 3. Вдоль цепи (s x ₁ x ₄ t) поток можно увеличить на δ = 3, увеличивая его на δ = 3 по каждой увеличивающей (рис. 3). Дуги (sx ₁) и (x ₁ x ₄) стали насыщенными.

После такого изменения, величина потока увеличилась на 3 и стала равнойной V = 6 + 3 = 9:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 9 + 0 = 9 или V_t = 6 + 3 = 9.

Условие сохранения потока выполняется.

1. Рассмотрим цепь (s x ₃ x ₄ t).

Цепь увеличивающая, так как все дуги допустимые (увеличивающие).

(s x ₃) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 8.

(x ₃ x ₄) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 0 < 4.

(x ₄ t) – допустимая (увеличивающая) дуга, так как направление дуги совпадает с направлением потока и поток по ней меньше пропускной способности: 3 < 7.

2. Вдоль дуги (s x ₃) поток можно увеличить на величину

= 8 - 0 = 8.

Вдоль дуги (x ₃ x ₄) поток можно увеличить на величину

= 4 - 0 = 4.

Вдоль дуги (x ₄ t) поток можно увеличить на величину

= 7 - 3 = 4.

3. δ = min{8, 4, 4} = 4. Вдоль цепи (s x ₃ x ₄ t) поток можно увеличить на δ = 4, увеличивая его на δ = 4 по каждой увеличивающей (рис. 4). Дуги (x ₃ x ₄) и (x ₄ t) стали насыщенными.

После такого изменения, величина потока увеличилась на 4 и стала равной V = 9+4 = 13:

Величина потока, выходящего из вершины s равна величине потока, входящего в вершину t:

V_s = 9 + 4 = 13 или V_t = 6 + 7 = 13.

Условие сохранения потока в вершинах выполняется.

Больше увеличивающих цепей нет. Минимальный раз рез (пунктирная линия), соответствующий этому потоку, включает дуги: (x ₁ x ₂), (x ₁ x ₄), (x ₃ x ₄),

и его пропускная способность равна: C (U) = 6 +3 + 4 = 13.

Величина максимального потока равна величине минимального разреза:

V = 13, C = 13.