Ля, есть кто теорию графов знает хорошо?
Задачка весёлая, готов даже сотку отгрузить.
Дан граф, в котором каждому узлу соответствует определённое случайное значение.
В этом графе необходимо построить остовное (направленное) дерево таким образом чтобы минимизировать количество участков, на которых узел с более высоким значением является дочерним по отношению к узлу имеющему меньшее значение.
Ну и вторая часть этой задачки:
При имеющемся остовном дереве необходим алгоритм, который перестроит дерево при изменении графа (добавлени/удаление узла, добавление/удаление связи). Создание дерева с нуля - не подходит.