Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://earchive.tpu.ru/handle/11683/5076
Название: Исследование полиномиальности метода вычисления интегрального описателя структуры графа
Другие названия: Polynomiality of method for computing graph structure integral descriptor
Авторы: Погребной, Владимир Кириллович
Погребной, Александр Владимирович
Ключевые слова: интегральный описатель структур; изоморфизм; графы; абстрактные структуры; устойчивые группы; вершины; интеграция; полиномиальные алгоритмы; коды; область интеграции; integral structure descriptor; graph isomorphism; abstract graph structure; stable group of vertices; code integration area; algorithm polynomiality
Дата публикации: 2013
Издатель: Томский политехнический университет
Библиографическое описание: Погребной В. К. Исследование полиномиальности метода вычисления интегрального описателя структуры графа / В. К. Погребной, А. В. Погребной // Известия Томского политехнического университета [Известия ТПУ]. — 2013. — Т. 323, № 5 : Управление, вычислительная техника и информатика. — [С. 146-151].
Аннотация: Актуальность исследования определяется большой потребностью в разработке эффективных методов инвариантного описания и анализа абстрактных структур графовых моделей. Цель работы заключается в обосновании полиномиальности предложенного авторами метода вычисления интегрального описателя абстрактной структуры графа. Методы исследования основываются на использовании аппарата теории графов и методов свободной и зависимой интеграции кодов структурных различий графов. В результате исследования введено понятие устойчивых групп вершин в графе и сформулированы условия возникновения и существования таких групп в процессе интеграции кодов структурных различий при вычислении интегрального описателя структуры - Integral structure descriptor (ISD). Для устойчивых групп установлен ряд свойств, которые раскрывают правомерность применения основных правил метода ISD и его полиномиальности. На основе выделенных свойств установлено, что условия существования устойчивых групп обусловлены жесткими ограничениями, а вершины разных устойчивых групп не могут порождать новые устойчивые группы. Установлен также фактор полной обособленности устойчивых групп, что в значительной мере предопределило эффективность алгоритма вычисления интегрального описателя структуры графа. Полиномиальность метода показана для наиболее трудного случая, когда графы являются однородными и содержат устойчивые группы. Для экспериментальных исследований метода ISD на языке Java разработано программное средство GraphISD и приведены некоторые результаты его работы.
The relevance of the research is caused by the necessity of developing the efficient method of invariant description and analysis of abstract structures of graph models. The aim of the research is to substantiate the polinomiality of the method for computing the integral descriptor of graph abstract structure proposed by the authors. The research techniques are based on application of machinery of graph theory and methods of free and dependent integration of codes of graph structural differences. The authors have introduced the notion of stable group of vertices in graph and stated the conditions of occurrence and existence of such groups at integration of structural differences codes when computing the integral structure descriptor. A number of features which disclose the appropriateness of application of the main rules of the integral structure descriptor and its polinomiality was determined for stable groups. It was ascertained on the basis of the defined features that the conditions for stable group existing are conditioned by hard limits; the vertices of different stable groups can not generate new stable groups. The authors have also defined the factor of full isolation of stable groups that predetermined considerably the efficiency of algorithm for computing the full graph structure descriptor. Polinomiality of the technique is demonstrated for the most complex case when graphs are homogeneous and contain stable groups. The authors developed Java GraphISD software for the experimental investigations of integral structure descriptor technique and introduced the results of its operation.
URI: http://earchive.tpu.ru/handle/11683/5076
ISSN: 1684-8519
Располагается в коллекциях:Известия ТПУ

Файлы этого ресурса:
Файл Описание РазмерФормат 
bulletin_tpu-2013-323-5-24.pdf284,51 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.