Интернет конференция по проблемам теории и практики управленияНазвание: МЕТОД ПОИСКА МИНИМАЛЬНЫХ РАЗРЕЗОВ ГРАФА ДЛЯ ЗАДАЧИ УПРАВЛЕНИЯ ИНЖЕНЕРНОЙ ИНФРАСТРУКТУРОЙ
Автор: Ольга Васильевна Лукинова
Соавторы:
Вандиловская П.А. , Крыгин А.А.
Аннотация:
В данной работе предлагается метод нахождения всех минимальных разрезов ориентированного графа, вообще говоря, произвольной размерности, что нивелирует ограничения известных методов.
Концепция метода основана на конструировании разрезов таким образом, что на каждом шаге генерируется новый набор ребер, который всегда является разрезом и этот разрез минимален либо содержит таковой. Описан алгоритм мето-да, сформулированы правила, положенные в его основу, представлена теорема, обосновывающая положения метода, а также следствие, доказывающее тот факт, что найденное множество минимальных разрезов полное.
Ключевые слова:
граф, минимальный разрез графа, инженерная сеть, свободный путь графа.
Автор: Ольга Васильевна Лукинова
Соавторы:
Вандиловская П.А. , Крыгин А.А.
Аннотация:
В данной работе предлагается метод нахождения всех минимальных разрезов ориентированного графа, вообще говоря, произвольной размерности, что нивелирует ограничения известных методов.
Концепция метода основана на конструировании разрезов таким образом, что на каждом шаге генерируется новый набор ребер, который всегда является разрезом и этот разрез минимален либо содержит таковой. Описан алгоритм мето-да, сформулированы правила, положенные в его основу, представлена теорема, обосновывающая положения метода, а также следствие, доказывающее тот факт, что найденное множество минимальных разрезов полное.
Ключевые слова:
граф, минимальный разрез графа, инженерная сеть, свободный путь графа.