Тип публикации: статья из журнала
Год издания: 2010
Ключевые слова: реализация гиперграфа деревом, дерево соединений гиперграфа, древовидная декомпозиция задач дискретной оптимизации, полиномиальные вычисления, tree realization hypergraph, tree compounds hypergraph, tree decomposition of problem discrete optimization, Polynomial computations
Аннотация: Приводится характеризация двух классов гиперграфов: М-ациклических и древовидных. Установлена связь между этими классами: гиперграф М-ацикличен тогда и только тогда, когда двойственный к нему гиперграф является древовидным. Эта связь дает возможность объединить арсенал известных полиномиальных алгоритмов, позволяющих распознавать пПоказать полностьюринадлежность гиперграфа к указанным классам и строить деревья соединений, деревья декомпозиций и деревья реализаций гиперграфа. The characterization of two classes of hypergraphs: M-acyclic and tree has been given. The link between these two classes: a hypergraph is M-acyclic if and only if the hypergraph dual to it is a tree was established. This relationship provides an opportunity to join the arsenal of known polynomial algorithms allowing detecting hypergraph belonging to these classes and building the trees of compounds, decompositions and trees of hypergraph realization.
Журнал: Известия Томского политехнического университета. Инжиниринг георесурсов
Выпуск журнала: Т. 317, № 2
Номера страниц: 25-30
ISSN журнала: 25001019
Место издания: Томск
Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский политехнический университет"