Метод ефективного перебору мiнiмальних розрiзiв й остовiв телекомунікаційних мереж

Abstract

Розроблено метод перебору мінімальних розрізів графа і його остовів. Цей метод реалізує перебір мінімальних розрізів мережі шляхом додавання по модулю два комбінацій базових розрізів, які знаходяться для довільного остова. В результаті отримуємо монотонну бульову функцію мінімальних розрізів у вигляді кон'юнктивної нормальної форми, яку перетворюємо у диз'юнктивну нормальну форму остовів.