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

Аннотация

Трудноразрешимые задачи на графах, такие как перечисления, выделение подграфов с заданными характеристиками, становятся особо актуальными на больших графах и сетях. При этом изменчивость и динамичность сетевых структур приводит к «дополнительному» усложнению поиска решения задач дискретной оптимизации. Для решения таких задач предлагаются частные постановки с ограничениями, и выделяются подклассы графов, для которых можно найти решения при определенных условиях. В работе предлагается класс предфрактальных графов и исследуются частные постановки NP-полных задач: изоморфизм подграфу, остов ограниченной степени, остов с максимальным числом висячих вершин, сбалансированный полный двудольный подграф, двудольный подграф, планарный подграф. Выделены условия, при которых для некоторых подзадач возможно получить ответ о существовании и построить полиномиальные алгоритмы поиска решений. Для примера предложены алгоритмы поиска остовных деревьев и упаковки двудольных графов. Разработанные алгоритмы являются полиномиальными и основаны на известных алгоритмах, которые используются в виде процедур. В работе фактически предлагается использовать класс предфрактальных графов в качестве инструмента исследования NP-полных задач и выделения условий их разрешимости. Разработка полиномиальных алгоритмов для динамических графов позволит решать с улучшенными характеристиками такие известные прикладные задачи как выделение подграфов в больших динамических сетях — выделение сообществ в социальных сетях; решение многокритериальных задач в транспортно-логистических системах большой размерности; поиск и выделение ddos-атак в криптовалютных системах и многие другие задачи.