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

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

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

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

обыкновенные графы, инварианты, подграфы, оценка компактности, компактные подграфы, эффект обособления вершин

Авторы:

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

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

Скачать bulletin_tpu-2013-322-5-39.pdf