Автор: Замбицкий Д.К., Лозовану Д.Д.
Название: Алгоритмы решения оптимизационных задач на сетях
Издательство: Кишинев: Штиинца
Год: 1983
Язык: Русский
Формат: djvu
Размер: 21,9 Мб
Качество: среднее, текстовый слой, оглавление.
Кол-во страниц: 117

Описание: Задача построения во взвешенном ориентированном графе минимального или максимального (по сумме длин дуг) выходящего леса, когда задано множество базовых вершин (откуда растет этот лес), является задачей с полиматроидной структурой. Для решения этой эадачи Эдмондс разработал эффективный алгоритм, а Фалкерсон предложил интересную его модификацию для проблемы оптимальной упаковки ориентированных корневых разрезов, к которой можно свести упомянутую задачу. В этой изложены эффективные алгоритмы определения в сети оптимальных конфигураций в виде выходящих лесов и алгоритмы решения некоторых задач размещения пунктов обслуживания систем. В книге рассматриваются эффективные алгоритмы решения некоторых сетевых оптимизационных задач, имеющих прикладное значение. В этой книге термин граф (орграф) используется только при рассмотрении чисто комбинаторных результатов, а термин сеть, когда будем иметь дело с потоками. Книга адресована специалистам по прикладной математике, занимающимся теорией графов и ее приложениями, доступна студентам университетов и втузов соответствующих специальностей.