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

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

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

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

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

Авторы:

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

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

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

Для оптимальной работы сайта журнала и оптимизации его дизайна мы используем куки-файлы, а также сервис для сбора и статистического анализа данных о посещении Вами страниц сайта (Яндекс Метрика). Продолжая использовать сайт, Вы соглашаетесь на использование куки-файлов и указанного сервиса.