Граф кратчайшего пути - Shortest-path graph - Wikipedia

Граф кратчайшего пути при t = 2

В математика и географическая информатика, а граф кратчайшего пути является неориентированный граф определяется из набора точек в Евклидова плоскость. Граф кратчайшего пути предлагается с идеей вывода ребер между набором точек, так что кратчайший путь, пройденный по предполагаемым ребрам, будет примерно совпадать с кратчайшим путем, пройденным через неточную область, представленную набором точек. график кратчайшего пути зависит от одного параметра т ≥ 1. Когда вес ребра определяется как его евклидова длина, возведенная в степень параметра т ≥ 1, ребро присутствует в графе кратчайших путей тогда и только тогда, когда это путь наименьшего веса между его конечными точками.^[1]

Свойства графа кратчайшего пути

Когда параметр конфигурации т уходит в бесконечность, граф кратчайшего пути становится минимальное остовное дерево набора точек. График представляет собой подграф набора точек Габриэль граф и, следовательно, также подграф его Триангуляция Делоне^[1].

Рекомендации