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

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

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

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

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

Авторы:

Погребной Array

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

Скачать PDF