Определение. Другой поток в этой же сети, показанные на рис

I 1(0)

I 1(1)

1 (0) 1 (1)

1 (0)

Рис. 6.5

Другой поток в этой же сети, показанные на рис. 6.6, имеет величину 2 и является максимальным.

1 (1)

1 (1)

1 (1) S

1 (1) 1 (1)

1 (1)

Рис. 6.6

Множество L Í U называется сечением сети N, если для всякого пути W, ведущего из I в S, выполняется условие

$ u Î E (W)(u Î L).

Если L - сечение транспортной сети N, то после удаления из N ребер множества L сеть распадается на несколько не связанных частей. При этом исток и сток сети попадают в разные части.

Пропускной способностью сечения транспортной сети называется сумма пропускных способностей ребер, входящих в это сечение.

Пропускная способность сечения L обозначаетсякак c (L).

Пропускные способности сечений всякой транспортной сети N и величину произвольного потока y в этой сети связывает следующее соотношение: y(N) c (L).

Действительно, суммарный входной поток сети, определяемый как y(N) выходит из I и затем передается по вершинам, связанным с S полностью распределяясь по ребрам из L и затем поступает в стока S. Суммарный поток, прошедший по ребрам L не превосходит пропускной способности сечения и в последующем может поступать в сток сети или повторно проходить по ребрам сечения, входящим в состав циклов сети, по которым течет ненулевой поток. Поэтому y(N) c (L).

Сечения транспортных сетей обладают следующим важным свойством: величина всякого потока в сети не превосходит пропускную способность любого сечения этой сети.

В частности, £ .

Здесь S - множество всех сечений сети.

Дата добавления: 2015-03-31