Матроид жесткости

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

Определение

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

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

Статика

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

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

Кинематика

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

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

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

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

Уникальная реализация

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

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

Отношение к разреженности

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Грейвер, Джек Э. (1991), «Матроиды жесткости», SIAM Journal on Discrete Mathematics , 4 (3): 355–368, doi : 10.1137/0404032 , MR 1105942 .
^ Jump up to: ^а ^б ^с Уайтли, Уолтер (1992), «Матроиды и жесткие конструкции», Приложения Матроидов , Энциклопедия математики и ее приложений, том. 40, Кембридж: Кембриджский университет. Press, стр. 1–53, doi : 10.1017/CBO9780511662041.002 , MR 1165538 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , MR 1411692 .
^ Jump up to: ^а ^б Хендриксон, Брюс (1995), «Проблема молекул: использование структуры в глобальной оптимизации», SIAM Journal on Optimization , 5 (4): 835–857, CiteSeerX 10.1.1.55.2335 , doi : 10.1137/0805040 , MR 1358807 .
^ Эрен, Т.; Гольденберг, ОК; Уайтли, В.; Ян, Ю.Р.; Морс, А.С.; Андерсон, БДО; Бельхумер, П.Н. (2004), «Жесткость, вычисления и рандомизация в сетевой локализации», Proc. Двадцать третья ежегодная совместная конференция обществ компьютеров и коммуникаций IEEE (INFOCOM 2004) , vol. 4, стр. 2673–2684, номер документа : 10.1109/INFCOM.2004.1354686 , S2CID 5674760 .
^ Хендриксон, Брюс (1992), «Условия уникальных реализаций графа», SIAM Journal on Computing , 21 (1): 65–84, doi : 10.1137/0221008 , MR 1148818 .
^ Джексон, Билл; Йордан, Тибор (2005), «Матроиды связной жесткости и уникальные реализации графов», Журнал комбинаторной теории , серия B, 94 (1): 1–29, doi : 10.1016/j.jctb.2004.11.002 , MR 2130278 .
^ Коннелли, Роберт (1991), «Об общей глобальной жесткости», Прикладная геометрия и дискретная математика , Серия DIMACS по дискретной математике и теоретической информатике, том. 4, Провиденс, Род-Айленд: Американское математическое общество, стр. 147–155, MR 1116345 .
^ Сакс, Дж. Б. (1979), Встраиваемость взвешенных графов в k -пространство сильно NP-трудна , Технический отчет, Питтсбург, Пенсильвания: Факультет компьютерных наук, Университет Карнеги-Меллона . Цитируется Джексоном и Джорданом (2005) .
^ Стрейну, И. ; Теран, Л. (2009), «Разреженные гиперграфы и алгоритмы игр с камушками», Европейский журнал комбинаторики , 30 (8): 1944–1964, arXiv : math/0703921 , doi : 10.1016/j.ejc.2008.12.018 , S2CID 5477763 .
^ Ламан, Г. (1970), «О графах и жесткости плоских скелетных структур», J. Engineering Mathematics , 4 (4): 331–340, Бибкод : 1970JEnMa...4..331L , doi : 10.1007/BF01534980 , МР 0269535 , S2CID 122631794 .
^ Джексон, Билл; Йордан, Тибор (2006), «О ранговой функции трехмерного матроида жесткости» (PDF) , International Journal of Computational Geometry & Applications , 16 (5–6): 415–429, doi : 10.1142/S0218195906002117 , MR 2269396 .

[graver-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Грейвер, Джек Э. (1991), «Матроиды жесткости», SIAM Journal on Discrete Mathematics , 4 (3): 355–368, doi : 10.1137/0404032 , MR 1105942 .

[w92-2] Jump up to: ^а ^б ^с Уайтли, Уолтер (1992), «Матроиды и жесткие конструкции», Приложения Матроидов , Энциклопедия математики и ее приложений, том. 40, Кембридж: Кембриджский университет. Press, стр. 1–53, doi : 10.1017/CBO9780511662041.002 , MR 1165538 .

[whiteley-3] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , MR 1411692 .

[molecule-4] Jump up to: ^а ^б Хендриксон, Брюс (1995), «Проблема молекул: использование структуры в глобальной оптимизации», SIAM Journal on Optimization , 5 (4): 835–857, CiteSeerX 10.1.1.55.2335 , doi : 10.1137/0805040 , MR 1358807 .

[5] Эрен, Т.; Гольденберг, ОК; Уайтли, В.; Ян, Ю.Р.; Морс, А.С.; Андерсон, БДО; Бельхумер, П.Н. (2004), «Жесткость, вычисления и рандомизация в сетевой локализации», Proc. Двадцать третья ежегодная совместная конференция обществ компьютеров и коммуникаций IEEE (INFOCOM 2004) , vol. 4, стр. 2673–2684, номер документа : 10.1109/INFCOM.2004.1354686 , S2CID 5674760 .

[6] Хендриксон, Брюс (1992), «Условия уникальных реализаций графа», SIAM Journal on Computing , 21 (1): 65–84, doi : 10.1137/0221008 , MR 1148818 .

[7] Джексон, Билл; Йордан, Тибор (2005), «Матроиды связной жесткости и уникальные реализации графов», Журнал комбинаторной теории , серия B, 94 (1): 1–29, doi : 10.1016/j.jctb.2004.11.002 , MR 2130278 .

[8] Коннелли, Роберт (1991), «Об общей глобальной жесткости», Прикладная геометрия и дискретная математика , Серия DIMACS по дискретной математике и теоретической информатике, том. 4, Провиденс, Род-Айленд: Американское математическое общество, стр. 147–155, MR 1116345 .

[9] Сакс, Дж. Б. (1979), Встраиваемость взвешенных графов в k -пространство сильно NP-трудна , Технический отчет, Питтсбург, Пенсильвания: Факультет компьютерных наук, Университет Карнеги-Меллона . Цитируется Джексоном и Джорданом (2005) .

[10] Стрейну, И. ; Теран, Л. (2009), «Разреженные гиперграфы и алгоритмы игр с камушками», Европейский журнал комбинаторики , 30 (8): 1944–1964, arXiv : math/0703921 , doi : 10.1016/j.ejc.2008.12.018 , S2CID 5477763 .

[11] Ламан, Г. (1970), «О графах и жесткости плоских скелетных структур», J. Engineering Mathematics , 4 (4): 331–340, Бибкод : 1970JEnMa...4..331L , doi : 10.1007/BF01534980 , МР 0269535 , S2CID 122631794 .

[12] Джексон, Билл; Йордан, Тибор (2006), «О ранговой функции трехмерного матроида жесткости» (PDF) , International Journal of Computational Geometry & Applications , 16 (5–6): 415–429, doi : 10.1142/S0218195906002117 , MR 2269396 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]