М.Ш. Левин

О разбиении графа на основе клик

Данная статья посвящена задаче разбиения графа на основе клик. Рассматриваются основные типы постановок задачи: (а) задача с максимизацией числа ребер (или суммы весов ребер) в полученных в разбиении исходного графа кликах, (б) задача с минимизацией числа ребер (или суммы весов ребер) между полученными в разбиении исходного графа кликами, (в) задача разбиения исходного графа с ограничением на число клик. Указанные задачи представляют собой специальный класс задач комбинаторной кластеризации. Дополнительно предлагаются новые многокритериальные постановки на основе использования векторных весов. Приведены краткие обзоры методов выделения клик в графах и методов решения задачи разбиения графа на основе клик. Проиллюстрирована задача построения траектории клики на основе динамического графа. Численные примеры иллюстрируют рассмотренные задачи.

КЛЮЧЕВЫЕ СЛОВА: разбиение графа, кластеризация, клика, комбинаторная оптимизация, комбинаторная кластеризация