Preview

Моделирование и анализ информационных систем

Расширенный поиск

Потоки в обобщенных сетях со связанными дугами

https://doi.org/10.18255/1818-1015-2012-2-41-52

Полный текст:

Аннотация

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

Об авторе

Владимир Александрович Скороходов
Южный федеральный университет
Россия
факультет математики, механики и компьютерных наук, кафедра алгебры и дискретной математики, доцент


Список литературы

1. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003. 8. С. 3–8.

2. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 2001. 279 с.

3. Берж К. Теория графов и ее применения. –М.:Изд–во иностранной литературы, 1962. 319с.

4. Кофман А. Введение в прикладную комбинаторику. –М.: Наука, 1975. 480с.

5. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003. 2. С. 3–5.

6. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003. 8. С. 9–12.


Для цитирования:


Скороходов В.А. Потоки в обобщенных сетях со связанными дугами. Моделирование и анализ информационных систем. 2012;19(2):41-52. https://doi.org/10.18255/1818-1015-2012-2-41-52

For citation:


Skorokhodov V.A. Flows in Generalized Nets with Related Arcs. Modeling and Analysis of Information Systems. 2012;19(2):41-52. (In Russ.) https://doi.org/10.18255/1818-1015-2012-2-41-52

Просмотров: 380


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)