Выделение условий разрешимости NP-полных задач для класса предфрактальных графов

Аннотация

Современные сетевые системы (группы БПЛА, социальные сети, сетевые производственные цепочки, транспортно-логистические сети, сети связи, криптовалютные сети) отличаются многоэлементностью и динамикой связей между ее элементами. Ряд дискретных задач по построению оптимальных подструктур сетевых систем, описываемых в виде различных классов графов относятся к NP-полным задачам. При этом изменчивость и динамичность структур сетевых систем приводит к «дополнительному» усложнению поиска решения задач дискретной оптимизации. Вместе с тем для некоторых подклассов динамических графов, которыми моделируются структуры сетевых систем, можно выделить условия разрешимости ряда NP-полных задач. К такому подклассу динамических графов относятся предфрактальные графы. В статье исследованы NP-полные задачи на предфрактальных графах: гамильтонов цикл, остов с максимальным числом висячих вершин, монохроматический треугольник, клика, независимое множество. Выделены условия, при которых для некоторых задач возможно получить ответ о существовании и построить полиномиальные (при фиксировании числа вершин затравки) алгоритмы поиска решений.