Том 322 № 5 (2013): Управление, вычислительная техника и информатика
Инвариант графа на основе компактных подграфов и алгоритм его вычисления
Для взвешенных обыкновенных графов введена оценка компактности подграфов. На основе этой оценки определён ряд инвариантов, характеризующих структуру графа с учётом неравномерности распределения значений весов по рёбрам. Основное внимание уделено понятию компактного подграфа. Предложен алгоритм выделения компактных подграфов и вычисления на их основе инвариантов. Подмечено важное свойство компактных подграфов - способность отражать эффект обособления подмножеств вершин с высокой оценкой компактности.
Ключевые слова:
обыкновенные графы, инварианты, подграфы, оценка компактности, компактные подграфы, эффект обособления вершин