Эту проблему можно решить с помощью линейного программирования .Проверка, может ли T быть минимальным остовным деревом, равносильна проверке выполнимости набора линейных ограничений на множестве | E |переменные, по одной для каждого края графика.Переменная x (u, v) соответствует весу ребра (u, v).То есть возможным решением для линейной программы является присвоение весов ребрам графа, так что T является минимальным остовным деревом.Итак, для начала, каждая переменная x (u, v) должна находиться в пределах указанного интервала.
Другие ограничения, которые я вскоре укажу, предназначены для удовлетворения тогда и только тогда, когда Tявляется минимальным остовным деревом в соответствии с назначением, которое решает программу.
Чтобы понять, почему при каждом присваивании, которое удовлетворяет следующим ограничениям, T должно быть минимальным остовным деревом, вы должны убедиться в следующем свойстве минимального связываниядеревья:
остовное дерево T является минимальным остовным деревом тогда и только тогда, когда для каждого ребра (u, v) не в T и каждого ребра e на пути от u к v в T, w(u,v)>=w(e).Это свойство следует из свойство cut .
Таким образом, чтобы проверить, может ли T быть минимальным остовным деревом, необходимо проверить выполнимость линейной программы, определенной следующим набором ограничений.
- Для каждого ребра на графике
i(u,v)<=x(u,v)<=j(u,v). - Для каждого ребра
(u,v) не в T, а для каждого ребра e на пути от u до v в т, x(u,v)>=x(e).