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

Матричный алгоритм решения задачи разрезания двудольных графов

Предложен алгоритм решения задачи разрезания двудольного графа на заданную совокупность минимально связанных подграфов. Алгоритм использует матричное представление двудольного графа и учитывает его специфику. Это позволило свести задачу разрезания к задаче линейного математического программирования. Алгоритм может работать как с произвольно сформированным, так и улучшенным исходным вариантом разрезания двудольного графа.

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

двудольные графы, разрезание, вершины, матрицы связности, линейное математическое программирование

Авторы:

Ан. В. Погребной

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

Скачать bulletin_tpu-2012-320-5-04.pdf