4430
правок
Деревья Гомори-Ху: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Формально дерево Гомори-Ху T = (V, F) для неориентированного графа G = (V, E) представляет собой взвешенное неориентированное дерево, определенное на вершинах графа, для которого выполняются следующие свойства: | Формально дерево Гомори-Ху T = (V, F) для неориентированного графа G = (V, E) представляет собой взвешенное неориентированное дерево, определенное на вершинах графа, для которого выполняются следующие свойства: | ||
• Для любой пары вершин <math>s, t \in V \;</math> , <math>\lambda (s, t) \;</math> равно минимальному весу ребра уникального пути, соединяющего s и t в T. | • Для любой пары вершин <math>s, t \in V \;</math> , <math>\lambda (s, t) \;</math> равно минимальному весу ребра уникального пути, соединяющего s и t в T. Обозначим это ребро как e(s, t). Если на пути из s к t в T имеется несколько ребер с минимальным весом, любое из этих ребер обозначается как e(s, t). | ||
• Для любой пары вершин s и t биразбиение вершин на компоненты, получаемые в результате удаления e(s, t) (при наличии нескольких кандидатов на e(s, t) это свойство выполняется для каждого из этих ребер) из T соответствует минимальному s-t-разрезу исходного графа G. | • Для любой пары вершин s и t биразбиение вершин на компоненты, получаемые в результате удаления e(s, t) (при наличии нескольких кандидатов на e(s, t) это свойство выполняется для каждого из этих ребер) из T соответствует минимальному s-t-разрезу исходного графа G. | ||