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

• Published in: Компьютерная математика
• Date: 2017
• Main Authors: Шарифов, Ф.А., Скукис, А.Е.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2017
• Subjects: Системный анализ
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/168454
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Проектирование сети, фундаментальные разрезы, матроиды / Ф.А. Шарифов, А.Е. Скукис // Компьютерная математика. — 2017. — № 2. — С. 46-53. — Бібліогр.: 11 назв. — рос.

Изучаются свойства матриц, строками которых являются значения 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.