Алгоритм построения родственных остовных ориентированных лесов минимального веса

В. А. Буслов

Санкт-Петербургскй государственный университет, ул. Ульяновская, д.3, Старый Петергоф, 198504 Санкт-Петербург, Россия

Аннотация: Предложен алгоритм построения ориентированных остовных лесов минимального веса, в котором сохраняется максимально возможная степень родства между минимальными лесами при изменении числа деревьев. Проверена корректность алгоритма и определена его сложность, которая не превышает $O(N^3)$ для плотных графов. Результатом работы алгоритма является набор родственных остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$. Библ. – 10 назв.

Ключевые слова: взвешенный орграф, минимальный лес, цепь Маркова.

УДК: 519.17

Поступило: 28.11.2025