Модель и метод поиска максимального структурированного потока в графе с множественными весами ребер

Аннотация

Представлена модель сети в виде графа, весами ребер которого являются подмножества из целых чисел. Данные веса характеризуют пропускную способность и ограничивают потоки через ребра. Между вершинами s и t данной сети необходимо сформировать особый вид потока, к которому предъявляются дополнительные требования: в каждом ребре маршрута от s к t необходимо выделить одинаковое подмножество смежных упорядоченных элементов, количество которых определяет величину потока. Интерес представляет задача поиска подмножества таких потоков, которые не имеют общих элементов и могут быть одновременно реализованы, а сумма их величин максимальна для данной сети. Модель и метод на основе целочисленного линейного программирования, представленные в данной статье, могут быть использованы для анализа пропускной способности графов с множественными весами ребер.