Современные сетевые системы (группы БПЛА, социальные сети, сетевые производственные цепочки, транспортно-логистические сети, сети связи, криптовалютные сети) отличаются многоэлементностью и динамикой связей между ее элементами. Ряд дискретных задач по построению оптимальных подструктур сетевых систем, описываемых в виде различных классов графов относятся к NP-полным задачам. При этом изменчивость и динамичность структур сетевых систем приводит к «дополнительному» усложнению поиска решения задач дискретной оптимизации. Вместе с тем для некоторых подклассов динамических графов, которыми моделируются структуры сетевых систем, можно выделить условия разрешимости ряда NP-полных задач. К такому подклассу динамических графов относятся предфрактальные графы. В статье исследованы NP-полные задачи на предфрактальных графах: гамильтонов цикл, остов с максимальным числом висячих вершин, монохроматический треугольник, клика, независимое множество. Выделены условия, при которых для некоторых задач возможно получить ответ о существовании и построить полиномиальные (при фиксировании числа вершин затравки) алгоритмы поиска решений.
Modern network systems (unmanned aerial vehicles groups, social networks, network production chains, transport and logistics networks, communication networks, cryptocurrency networks) are distinguished by their multi-element nature and the dynamics of connections between its elements. A number of discrete problems on the construction of optimal substructures of network systems described in the form of various classes of graphs are NP-complete problems. In this case, the variability and dynamism of the structures of network systems leads to an "additional" complication of the search for solutions to discrete optimization problems. At the same time, for some subclasses of dynamical graphs, which are used to model the structures of network systems, conditions for the solvability of a number of NP-complete problems can be distinguished. This subclass of dynamic graphs includes pre-fractal graphs. The article investigates NP-complete problems on pre-fractal graphs: a Hamiltonian cycle, a skeleton with the maximum number of pendant vertices, a monochromatic triangle, a clique, an independent set. The conditions under which for some problems it is possible to obtain an answer about the existence and to construct polynomial (when fixing the number of seed vertices) algorithms for finding solutions are identified.
The authors declare that there are no conflicts of interest present.