рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Производство
- /
- Пропускная способность дуги ограничена для суммы всех видов продуктов через эту дугу
Реферат Курсовая Конспект
Пропускная способность дуги ограничена для суммы всех видов продуктов через эту дугу
Пропускная способность дуги ограничена для суммы всех видов продуктов через эту дугу - раздел Производство, П...
Потоки в сетях.
Варианты задач:
1) Пусть каждой дуге графа приписана не только пропускная способность 
, - верхняя граница потока через дугу ( 
) по так же 
- нижнюю границу потока через дугу Если задать стоимость единицы потока , протекающего по дуге, то возникает задача нахождения допустимого потока минимальной стоимости (от s и t).
2) Ищутся max потоки между каждой паройвершин. Она может быть решена как
« отдельных » от s и t задач, но это трудоёмкий процесс. При нахождении
путей между каждой парой вершин графа не обязательно решать каждую задачу индивидуально .
3)Если вместо 1 источника и 1 стока рассмотреть несколько источников и стоков, причем между различными источниками и стоками протекают потоки различных продуктов, то имеем задачу с многопродуктовым потоком.
Пропускная способность дуги (
) ограничена для суммы всех видов продуктов через эту дугу.
4) Если исходить оттого, что поток на входе = потоку на выходе, то выходит поток дуги
= входному потоку, умноженному на некоторое неотрицательное число, то получим задачу о потоках с «выигрышами». В такой задаче потоки могут и « порождаемые» и «погашаемые» самим графом, а поток, входящий в S и потом покидающий t, могут изменяться совершенно независимо.
Задачи о MAX потоке
(1) – уравнение сохранения потока : Поток, втекающий в вершину, равен потоку,… (2) – ограниченны на пропускные способности для каждой дуги G.Задача: найти множество потоков по дугам, чтобы величина…Алгоритм расстановки пометок для задачи о max (от s и t) потоке.
Вершина может находиться в одном из 3 состояний : вершине приписана пометка и вершина присмотрена (т.е. она имеет отметку и не смежные с ней вершины… Шаг1 Присвоить вершине s пометку (+s, ). Вершине s присвоена пометка, и она… Шаг2 Взять некоторую непросмотренную вершину с пометкой: пусть ее пометка будет (,.– Конец работы –
Используемые теги: Пропускная, способность, дуги, ограничена, суммы, всех, видов, продуктов, через, эту, дугу0.143
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Пропускная способность дуги ограничена для суммы всех видов продуктов через эту дугу
Что будем делать с полученным материалом:
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.194 сек.
Новости и инфо для студентов