Проектирование сети, фундаментальные разрезы, матроиды

Abstract

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

Вивчаються властивості матриць, рядками яких є значення 0 або 1, як характеристичні вектори фундаментальних розрізів. Показано, що при вирішенні складних проблем проектування мережі виникають задачі лінійного програмування із певними матрицями обмежень, а також сформульована характеристика цих матриць у термінах спеціальних підматриць.

We study some properties of the matrices with 0- or 1-valued rows in the form of characteristic vectors of fundamental cuts. It is shown that linear programming problems with such matrices of constraints arise in solving complex network design problems; moreover, a characteristic of these matrices is formulated in terms of special submatrices.