Изучение поперечных сечений сети и нахождение ограниченного поперечного сечения. Сущность понятия "поток сети". Характеристика теоремы Форда-Фалкерсона и ее решение. Особенности построения орграфа приращений и максимального потока для транспортной сети.
Московский Государственный Институт Делового Администрирования Работу выполнила: Болотина ЮлияВ задаче, которую я рассматриваю, да и вообще в задачах на данную тему фундаментальную роль играет изучение поперечных сечений сети (то есть множеств дуг, которые соединяют вершины двух не пересекающихся множеств вершин) и нахождение ограниченного поперечного сечения, которое является самым узким местом. Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ), называемое пропускной способностью дуги, и существует: 1) ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети; 2) ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети. Дуга транспортная сеть максимальный поток называется насыщенной потоком f, если (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).) Функция , определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если: •для любой дуги величина , называемая потоком по дуге , удовлетворяет условию ;Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами.
План
Содержание
Введение
Теоретическая часть
Теорема Форда-Фалкерсона
Алгоритм решения
Поток в транспортной сети
Орграф приращений
Алгоритм построения максимального потока в транспортной сети
Практическая часть
Заключение
Список используемой литературы
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
