Жесткость матроида

В математике структурной жесткости матроид жесткости — это матроид , описывающий число степеней свободы неориентированного графа с жесткими ребрами фиксированной длины, вложенного в евклидово пространство . В матроиде жесткости для графа с n вершинами в d -мерном пространстве набор ребер, определяющий подграф с k степенями свободы, имеет ранг матроида dn  −  k . Набор ребер независим тогда и только тогда, когда для каждого ребра в наборе удаление ребра увеличит число степеней свободы оставшегося подграфа. ^{[1] [2] [3]}

Каркас — это неориентированный граф , встроенный в d -мерное евклидово пространство путем предоставления d -кортежа декартовых координат для каждой вершины графа. Из каркаса с n вершинами и m ребрами можно определить матрицу с m строками и nd столбцами, расширенную версию матрицы инцидентности графа, называемую матрицей жесткости . В этой матрице запись в строке e и столбце ( v , i ) равна нулю, если v не является конечной точкой ребра e . Если, с другой стороны, ребро e имеет вершины u и v в качестве конечных точек, то значение записи равно разнице между i -ми координатами v и u . ^{[1] [3]}

Матроид жесткости данного каркаса — это линейный матроид , элементами которого являются ребра графа. Набор ребер независим в матроиде, если он соответствует набору строк матрицы жесткости, которая линейно независима . Каркас называется общим , если координаты его вершин являются алгебраически независимыми действительными числами. Любые два общих каркаса на одном и том же графе G определяют один и тот же матроид жесткости, независимо от их конкретных координат. Это ( d -мерный) матроид жесткости G. ^{[1] [3]}

Нагрузка на каркас представляет собой систему сил на вершинах (представленных в виде векторов). Напряжение является частным случаем нагрузки, в которой равные и противоположные силы прикладываются к двум конечным точкам каждого ребра (которое можно представить как пружину), и силы, сформированные таким образом, складываются в каждой вершине. Каждое напряжение является равновесной нагрузкой , нагрузкой, которая не накладывает никакой поступательной силы на всю систему (сумма ее векторов силы равна нулю) или какой-либо вращательной силы. Линейная зависимость между строками матрицы жесткости может быть представлена ​​как самонапряжение , назначение равных и противоположных сил конечным точкам каждого ребра, которое не является тождественно нулем, но которое добавляется к нулю в каждой вершине. Таким образом, набор ребер образует независимое множество в матроиде жесткости тогда и только тогда, когда он не имеет самонапряжения. ^[3]

Вектор пространства всех возможных нагрузок на систему из n вершин имеет размерность dn , среди которых равновесные нагрузки образуют подпространство размерности . Независимое множество в матроиде жесткости имеет систему равновесных нагрузок, размерность которой равна мощности множества, поэтому максимальный ранг, который может иметь любое множество в матроиде, равен . Если множество имеет этот ранг, то из этого следует, что его набор напряжений совпадает с пространством равновесных нагрузок. Альтернативно и эквивалентно, в этом случае каждая равновесная нагрузка на каркас может быть разрешена напряжением, которое генерирует равный и противоположный набор сил, и каркас называется статически жестким. ^[3]${\displaystyle dn-{\binom {d+1}{2}}}$${\displaystyle dn-{\binom {d+1}{2}}}$

Если вершины каркаса находятся в движении, то это движение может быть описано на малых масштабах расстояния его градиентом , вектором для каждой вершины, определяющим ее скорость и направление. Градиент описывает линеаризованное приближение к фактическому движению точек, в котором каждая точка движется с постоянной скоростью по прямой линии. Градиент может быть описан как вектор-строка, который имеет одну вещественную числовую координату для каждой пары, где - вершина каркаса, а - индекс одной из декартовых координат -мерного пространства; то есть размерность градиента такая же, как ширина матрицы жесткости. ^{[1] [3]}${\displaystyle (v,i)}$${\displaystyle v}$${\displaystyle я}$${\displaystyle д}$

Если края каркаса предполагаются жесткими стержнями, которые не могут ни расширяться, ни сжиматься (но могут свободно вращаться), то любое движение, уважающее эту жесткость, должно сохранять длины ребер: производная длины, как функция времени, в течение которого происходит движение, должна оставаться нулевой. Это условие может быть выражено в линейной алгебре как ограничение, что вектор градиента движения вершин должен иметь нулевое внутреннее произведение со строкой матрицы жесткости, которая представляет данное ребро. Таким образом, семейство градиентов (бесконечно мало) жестких движений задается нулевым пространством матрицы жесткости. ^{[1] [3]} Для каркасов, которые не находятся в общем положении, возможно, что некоторые бесконечно мало жесткие движения (векторы в нулевом пространстве матрицы жесткости) не являются градиентами какого-либо непрерывного движения, но этого не может произойти для общих каркасов. ^[2]

Жесткое движение каркаса — это движение, при котором в каждый момент времени каркас конгруэнтен своей исходной конфигурации. Жесткие движения включают в себя переносы и вращения евклидова пространства; градиенты жестких движений образуют линейное пространство, имеющее переносы и вращения в качестве баз, размерности , которое всегда должно быть подпространством нулевого пространства матрицы жесткости. Поскольку нулевое пространство всегда имеет по крайней мере эту размерность, матроид жесткости может иметь ранг не более , и когда он имеет этот ранг, единственными движениями, которые сохраняют длины ребер каркаса, являются жесткие движения. В этом случае каркас называется жестким первого порядка (или бесконечно малым). ^{[1] [3]} В более общем смысле, ребро принадлежит операции замыкания матроида множества тогда и только тогда, когда не существует непрерывного движения каркаса, которое изменяет длину , но оставляет длины ребер неизменными. ^[1]${\displaystyle {\binom {d+1}{2}}}$${\displaystyle dn-{\binom {d+1}{2}}}$${\displaystyle е}$${\displaystyle S}$${\displaystyle е}$${\displaystyle S}$

Хотя они определяются в разных терминах (векторы-столбцы против векторов-строк или силы против движений), статическая жесткость и жесткость первого порядка сводятся к тем же свойствам базовой матрицы и, следовательно, совпадают друг с другом. В двух измерениях общий матроид жесткости также описывает число степеней свободы другого вида движения, в котором каждое ребро ограничено оставаться параллельным своему исходному положению, а не ограничено сохранением той же длины; однако эквивалентность между жесткостью и параллельным движением нарушается в более высоких измерениях. ^[3]

Каркас имеет уникальную реализацию в d -мерном пространстве, если каждое размещение одного и того же графа с одинаковыми длинами ребер ему конгруэнтно. Такой каркас обязательно должен быть жестким, потому что в противном случае существует непрерывное движение, приводящее его к неконгруэнтному размещению с одинаковыми длинами ребер, но уникальная реализуемость сильнее жесткости. Например, ромбовидный граф (два треугольника, разделяющие ребро) является жестким в двух измерениях, но он не является уникально реализуемым, потому что у него есть две разные реализации, одна из которых, в которой треугольники находятся на противоположных сторонах общего ребра, и другая, в которой они оба находятся на одной стороне. Уникально реализуемые графы важны в приложениях, которые включают реконструкцию форм с расстояния, таких как триангуляция в топографической съемке, ^[4] определение положений узлов в беспроводной сенсорной сети , ^[5] и реконструкция конформаций молекул с помощью ядерно-магнитной резонансной спектроскопии . ^[4]

Брюс Хендриксон определил граф как избыточно жесткий , если он остается жестким после удаления любого из его ребер. В терминах матроида это означает, что матроид жесткости имеет полный ранг и что матроид не имеет никаких колопов. Хендриксон доказал, что каждый уникально реализуемый каркас (с общими длинами ребер) является либо полным графом , либо - вершинно-связанным , избыточно жестким графом, и он предположил, что это точная характеристика уникально реализуемых каркасов. ^[6] Гипотеза верна для одного и двух измерений; в одномерном случае, например, граф уникально реализуем тогда и только тогда, когда он связен и не имеет мостов . ^[7] Однако гипотеза Хендриксона ложна для трех и более измерений. ^[8] Для каркасов, которые не являются общими, NP-трудно определить, является ли данный каркас уникально реализуемым. ^[9]${\displaystyle dn-{\binom {d+1}{2}}}$${\displaystyle (d+1)}$

Streinu & Theran (2009) определяют граф как -разреженный, если каждый непустой подграф с вершинами имеет не более ребер, и -плотный, если он -разреженный и имеет ровно ребер. ^[10] Из рассмотрения нагрузок и напряжений можно увидеть, что набор ребер, который независим в матроиде жесткости, образует -разреженный граф, поскольку в противном случае существовал бы подграф, количество ребер которого превышало бы размерность его пространства равновесных нагрузок, из чего следует, что он имел бы самонапряжение. По аналогичным рассуждениям набор ребер, который является как независимым, так и жестким, образует -плотный граф. Например, в одном измерении независимые множества образуют множества ребер лесов, (1,1)-разреженных графов, а независимые жесткие множества образуют множества ребер деревьев, (1,1)-плотных графов. В этом случае матроид жесткости каркаса совпадает с графическим матроидом соответствующего графа. ^[2]${\displaystyle (к,л)}$${\displaystyle n}$${\displaystyle кн-л}$${\displaystyle (к,л)}$${\displaystyle (к,л)}$${\displaystyle кн-л}$${\displaystyle (d,{\binom {d+1}{2}})}$${\displaystyle (d,{\binom {d+1}{2}})}$

В двух измерениях Ламан (1970) показал, что верна та же самая характеристика: независимые множества образуют множества ребер (2,3)-разреженных графов, а независимые жесткие множества образуют множества ребер (2,3)-плотных графов. ^[11] На основе этой работы (2,3)-плотные графы (графы минимально жестких общих каркасов в двух измерениях) стали известны как графы Ламана . Семейство графов Ламана на фиксированном множестве вершин образует множество баз матроида жесткости полного графа , и, в более общем смысле, для каждого графа , который образует жесткий каркас в двух измерениях, остовные подграфы Ламана являются базами матроида жесткости .${\displaystyle n}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

Однако в более высоких размерностях не каждый -плотный граф является минимально жестким, и характеристика минимально жестких графов (баз жесткостного матроида полного графа) является важной открытой проблемой. ^[12]${\displaystyle (d,{\binom {d+1}{2}})}$