@article{Кочкаров_2021, title={Исследование некоторых трудноразрешимых задач на классе предфрактальных графов с изменяемым траекторным порождением}, url={https://journals.vsu.ru/sait/article/view/3799}, DOI={10.17308/sait.2021.4/3799}, abstractNote={<p>Трудноразрешимые задачи на графах, такие как перечисления, выделение подграфов с заданными характеристиками, становятся особо актуальными на больших графах и сетях. При этом изменчивость и динамичность сетевых структур приводит к «дополнительному» усложнению поиска решения задач дискретной оптимизации. Для решения таких задач предлагаются частные постановки с ограничениями, и выделяются подклассы графов, для которых можно найти решения при определенных условиях. В работе предлагается класс предфрактальных графов и исследуются частные постановки NP-полных задач: изоморфизм подграфу, остов ограниченной степени, остов с максимальным числом висячих вершин, сбалансированный полный двудольный подграф, двудольный подграф, планарный подграф. Выделены условия, при которых для некоторых подзадач возможно получить ответ о существовании и построить полиномиальные алгоритмы поиска решений. Для примера предложены алгоритмы поиска остовных деревьев и упаковки двудольных графов. Разработанные алгоритмы являются полиномиальными и основаны на известных алгоритмах, которые используются в виде процедур. В работе фактически предлагается использовать класс предфрактальных графов в качестве инструмента исследования NP-полных задач и выделения условий их разрешимости. Разработка полиномиальных алгоритмов для динамических графов позволит решать с улучшенными характеристиками такие известные прикладные задачи как выделение подграфов в больших динамических сетях — выделение сообществ в социальных сетях; решение многокритериальных задач в транспортно-логистических системах большой размерности; поиск и выделение ddos-атак в криптовалютных системах и многие другие задачи.</p&gt;}, number={4}, journal={Вестник ВГУ. Серия: Системный анализ и информационные технологии}, author={Кочкаров, Расул Ахматович}, year={2021}, month={дек.}, pages={66-82} }