Система — это множество элементов и связей между ними, и ее свойства во многом определяются структурой связей. Чтобы построить хорошую систему, необходимо уметь выбирать для нее хорошую (оптимальную) структуру.

Выбор рациональной структуры системы, связи между элементами которой формируются за счет потоков (информационных или материальных), часто сводится к задаче об оптимальной связывающей сети. Исходные данные задачи — абоненты и граф потоков (информации, товаров) между ними. Соединять абонентов напрямую неэффективно, и потоки идут через сеть промежуточных маршрутизаторов. Затраты маршрутизатора зависят от входящих и исходящих потоков, и задача в том, чтобы построить самую дешевую связывающую сеть. Эта задача считается очень сложной, ведь уже для 30-ти абонентов вариантов сетей больше, чем атомов во вселенной!

Известно, что дешевые сети компактны. Например, легко построить самое компактное дерево. Однако для более точного решения задачи о связывающей сети необходимо уметь строить и наименее компактные деревья. Эта задача оказывается более сложной, однако ученым Института проблем управления им. В.А. Трапезникова РАН удалось предложить эффективные приближенные алгоритмы и экономные точные алгоритмы ее решения.

Компактное дерево (слева) и «разбросанное»...

Компактное дерево (слева) и «разбросанное» дерево (справа)

Одним из приложений теории является поиск материалов с заданными физико-химическими свойствами. Например, чтобы найти наилучший полимерный материал для газоразделительной мембраны, необходимо связать химическую структуру полимера с коэффициентом газопроницаемости полимера, а также с коэффициентом растворимости в нем различных газов. Ученым удалось объяснить коэффициент растворимости геометрической формой отдельной полимерной цепи.

Алгоритм моделирования полимерной цепи

Алгоритм моделирования полимерной цепи

Еще одно приложение — алгоритмы быстрого деления сети передачи электрической энергии для предотвращения развития каскадных аварий. Разработанный учеными алгоритм за секунды находит наилучшую структуру деления огромной сети с десятками тысяч узлов. В будущем он будет полезен при анализе и синтезе структуры других типов транспортных сетей.

Подробнее с результатами исследования можно ознакомиться в следующих публикациях:

GoubkoM., Miloserdov O., Yampolskii Yu., Alentiev A., Ryzhikh V. A novel model to predict infinite dilution solubility coefficients in glassy polymers // Journal of Polymer Science Part B: Polymer Physics, Vol. 55, No 3. P. 228–244

M. Goubko, Minimizing Wiener Index for Vertex-Weighted Trees with Given Weight and Degree Sequences, MATCH Commun. Math. Comput. Chem., 2016, V. 75, No 1, P. 3-27

Губко М.В., Гинз В.Н. Двухэтапный алгоритм для задачи оптимального деления электрической сети / Материалы 13-й Всероссийской школы-конференции молодых ученых «Управление большими системами» (УБС'2016, Самара). М.: ИПУ РАН, 2016. С. 252-262