Т. 323, № 5 : Управление, вычислительная техника и информатика

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

Актуальность исследования определяется большой потребностью в разработке эффективных методов инвариантного описания и анализа абстрактных структур графовых моделей. Цель работы заключается в обосновании полиномиальности предложенного авторами метода вычисления интегрального описателя абстрактной структуры графа. Методы исследования основываются на использовании аппарата теории графов и методов свободной и зависимой интеграции кодов структурных различий графов. В результате исследования введено понятие устойчивых групп вершин в графе и сформулированы условия возникновения и существования таких групп в процессе интеграции кодов структурных различий при вычислении интегрального описателя структуры - Integral structure descriptor (ISD). Для устойчивых групп установлен ряд свойств, которые раскрывают правомерность применения основных правил метода ISD и его полиномиальности. На основе выделенных свойств установлено, что условия существования устойчивых групп обусловлены жесткими ограничениями, а вершины разных устойчивых групп не могут порождать новые устойчивые группы. Установлен также фактор полной обособленности устойчивых групп, что в значительной мере предопределило эффективность алгоритма вычисления интегрального описателя структуры графа. Полиномиальность метода показана для наиболее трудного случая, когда графы являются однородными и содержат устойчивые группы. Для экспериментальных исследований метода ISD на языке Java разработано программное средство GraphISD и приведены некоторые результаты его работы.

Ключевые слова:

труды учёных ТПУ, электронный ресурс, интегральный описатель структур, изоморфизм, графы, абстрактные структуры, устойчивые группы, вершины, интеграция, полиномиальные алгоритмы, коды, область интеграции,

Авторы:

Погребной Владимир Кириллович

Погребной Александр Владимирович

Скачать PDF