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