Прямолинейное дерево Штейнера: различия между версиями

При подключении точки к ребру самое длинное ребро получившейся схемы необходимо удалить. Для эффективного поиска соответствующего самого длиного ребра для каждой пары «точка-ребро» используется подход к вычислению остовного дерева при помощи алгоритма Крускала. Этот алгоритм сортирует ребра в порядке неубывания длины и рассматривает поочередно каждое ребро. Если конечные точки ребра были соединены, оно исключается из остовного дерева; в противном случае ребро включается в остовное дерево. Структура операций подключения может быть представлена бинарным деревом, листьями которого являются точки, а внутренними вершинами – ребра. После включения ребра в остовное дерево создается вершина, представляющая ребро, а также два ее потомка, представляющие два компонента, соединенные этим ребром. Пример остовного дерева и представляющего его бинарного дерева приведен на рис. 2. Легко увидеть, что самое длинное ребро между двумя точками является наименьшим общим предком этих двух точек в бинарном дереве. Например, самое длинное ребро между точками p и b на рис. 2 – ребро (b, c), наименьший общий предок p и b в бинарном дереве. Чтобы найти самое длинное ребро в схеме, образованной подключением точки к ребру, необходимо найти самое длинное ребро между этой точкой и той из конечных точек ребра, с которой она находилась в одном компоненте до подключения к ребру. Например, рассмотрим пары из точки p и ребра (a, b). Поскольку p и b принадлежали к одному компоненту до подключения (a, b), самым длинным ребром оказывается ребро между p и b; его и нужно удалить.