Граф кратчайшего пути
В математике и географической информатике граф кратчайшего пути — это неориентированный граф, определенный из набора точек на евклидовой плоскости . Граф кратчайшего пути предложен с идеей определения ребер между набором точек так, чтобы кратчайший путь, пройденный через выведенные ребра, примерно совпадал с кратчайшим путем, пройденным через неточную область, представленную набором точек. Набор ребер графа кратчайшего пути варьируется в зависимости от одного параметра t ≥ 1. Когда вес ребра определяется как его евклидова длина, возведенная в степень параметра t ≥ 1, ребро присутствует в кратчайшем пути. Граф путей тогда и только тогда, когда это путь с наименьшим весом между его конечными точками. [1]
Свойства графа кратчайшего пути
[ редактировать ]Когда параметр конфигурации t стремится к бесконечности, граф кратчайшего пути становится минимальным связующим деревом набора точек. Граф является подграфом графа Габриэля множества точек и, следовательно, также подграфом его триангуляции Делоне . [1]
Ссылки
[ редактировать ]- ^ Jump up to: а б де Берг, Марк ; Меулеманс, Воутер; Спекманн, Беттина (2011). «Очерчивание неточных областей с помощью графов кратчайших путей» . Материалы 19-й Международной конференции ACM SIGSPATIAL по достижениям в области географических информационных систем - ГИС '11 . Том. 19. С. 271–280. дои : 10.1145/2093973.2094010 . ISBN 9781450310314 . S2CID 2359926 . Проверено 2 сентября 2019 г.