Хананская сетка
В геометрии сетка Ханана H ( S ) конечного набора S точек плоскости получается путем построения вертикальных и горизонтальных линий, проходящих через каждую S. точку
Основная мотивация изучения сетки Ханана связана с тем фактом, что она, как известно, содержит прямолинейное дерево Штейнера минимальной длины для S . [1] Он назван в честь Мориса Ханана, который был первым [2] исследовать прямолинейное дерево минимума Штейнера и ввел этот граф. [3]
Ссылки
[ редактировать ]- ^ Мартин Захариасен, Каталог сетей с проблемами сетки Ханана , том. 38, 2000, стр. 200-221.
- ^ Кристин Р. Леверенц, Мирослав Трушинский, Задача прямолинейного дерева Штейнера: алгоритмы и примеры, использующие перестановки терминального набора , 1999 г., Юго-восточная региональная конференция ACM , 1999 г., дои : 10.1145/306363.306402
- ^ М. Ханан, О проблеме Штайнера с прямолинейным расстоянием. Архивировано 4 марта 2016 г. в Wayback Machine , J. SIAM Appl. Математика. 14 (1966), 255 – 265.