Аннотация:
Целью настоящей работы является обобщение на случай взвешенных плоских бинарных деревьев известного алгоритма Мелзака, а также понятия числа вращения. Последнее позволяет получить существенные ограничения на возможные топологии взвешенных минимальных бинарных деревьев.
Ключевые слова:
задача Штейнера, плоские взвешенные минимальные бинарные деревья, алгоритм Мелзака, число вращения.
Полный текст:
PDF файл (1736 kB)