АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Множество L Í Uназывается сечением сети N, если для всякого пути W, ведущего из I в S, выполняется условие

Множество 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-09-27 | Просмотры: 335 | Нарушение авторских прав