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

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

Для взвешенных обыкновенных графов введена оценка компактности подграфов. На основе этой оценки определён ряд инвариантов, характеризующих структуру графа с учётом неравномерности распределения значений весов по рёбрам. Основное внимание уделено понятию компактного подграфа. Предложен алгоритм выделения компактных подграфов и вычисления на их основе инвариантов. Подмечено важное свойство компактных подграфов - способность отражать эффект обособления подмножеств вершин с высокой оценкой компактности.

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

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

Авторы:

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

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

Скачать PDF