Транспортные сети. Задача о максимальном потоке в сети

Просмотрим V6

Изменение потока:

Вносим изменения потока. Дуга (S,V3) стала насыщенной.

 

 

 

 

 

 

Поток f=21 является максимальным, а множество дуг составляют минимальный разрез сети. Минимальный разрез на рисунке обозначен волнистой линией.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

 

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

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ), называемое пропускной способностью дуги, и существует:

1) ровно одна вершина  , в которую не заходит ни одна дуга, называемая источником или началом сети;

2. ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

1. А.М. Аллавердиев, И.В. Платонова «Прикладная  математика. Элементы теории графов»  М.2000

2. Лекции по прикладной математике  И.В. Платоновой

3. В.Н. Нефедов, В.А. Осипова «Курс  дискретной математики» М. 1992

4. С.В. Судоплатов, Е.В. Овчинникова  «Элементы дискретной математики»  М. 2002