Фактор растяжения (т. е. константа Билипшица ) вложения измеряет фактор, с которым вложение искажает расстояния . Предположим, что одно метрическое пространство S вложено в другое метрическое пространство T с помощью метрического отображения , непрерывной функции f , которая сохраняет или уменьшает расстояние между каждой парой точек. Тогда вложение порождает два различных понятия расстояния между парами точек в S. Любая пара точек ( x , y ) в S имеет как внутреннее расстояние , расстояние от x до y в S , так и меньшее внешнее расстояние, расстояние от f ( x ) до f ( y ) в T. Фактор растяжения пары — это отношение этих двух расстояний, d ( f ( x ), f ( y) )/ d ( x , y ) . Фактор растяжения всего отображения — это супремум факторов растяжения всех пар точек. Фактор растяжения также называют искажением [ спорно – обсудим ] или расширением отображения.
Фактор растяжения важен в теории геометрических остовов , взвешенных графов , которые аппроксимируют евклидовы расстояния между набором точек в евклидовой плоскости . В этом случае вложенная метрика S является конечным метрическим пространством, расстояния которого являются кратчайшими длинами путей в графе, а метрика T , в которую вложен S, является евклидовой плоскостью. Когда граф и его вложение фиксированы, но веса ребер графа могут меняться, фактор растяжения минимизируется, когда веса в точности равны евклидовым расстояниям между конечными точками ребер. Исследования в этой области были сосредоточены на поиске разреженных графов для заданного набора точек, которые имеют низкий фактор растяжения. [1]
Лемма Джонсона –Линденштрауса утверждает, что любое конечное множество с n точками в евклидовом пространстве может быть вложено в евклидово пространство размерности O (log n ) с искажением 1 + ε , для любой константы ε > 0 , где постоянный множитель в O -обозначении зависит от выбора ε . [2] Этот результат и связанные с ним методы построения метрических вложений с низким искажением важны в теории алгоритмов приближения . Основной открытой проблемой в этой области является гипотеза GNRS , которая (если она верна) характеризует семейства графов, которые имеют вложения с ограниченным растяжением в пространства, как все семейства графов с замкнутым минором.
В теории узлов искажение узла является инвариантом узла , минимальным фактором растяжения любого вложения узла как пространственной кривой в евклидово пространство . Исследователь-бакалавр Джон Пардон выиграл премию Моргана 2012 года за свое исследование, показывающее, что не существует верхней границы искажения торических узлов , решив проблему, первоначально поставленную Михаилом Громовым . [3] [4]
При изучении потока укорачивания кривой , в котором каждая точка кривой в евклидовой плоскости движется перпендикулярно кривой со скоростью, пропорциональной локальной кривизне, Хейскен (1998) доказал, что фактор растяжения любой простой замкнутой гладкой кривой (с внутренними расстояниями, измеряемыми длиной дуги) изменяется монотонно. Более конкретно, в каждой паре ( x , y ) , которая образует локальный максимум фактора растяжения, фактор растяжения строго уменьшается, за исключением случая, когда кривая является окружностью. Это свойство позже было использовано для упрощения доказательства теоремы Гейджа–Гамильтона–Грейсона, согласно которой каждая простая замкнутая гладкая кривая остается простой и гладкой, пока не схлопнется в точку, сходясь по форме к окружности перед этим. [5] [6]
