В математике структурной жесткости , А жесткость матроид является матроидом , который описывает число степеней свободы в качестве неориентированного графа с жесткими краями фиксированной длиной, встроенный в евклидово пространства . В матроиде жесткости для графа с n вершинами в d -мерном пространстве набор ребер, определяющий подграф с k степенями свободы, имеет ранг матроида dn - k . Набор ребер независим тогда и только тогда, когда для каждого ребра в наборе удаление ребра увеличит количество степеней свободы оставшегося подграфа.[1] [2] [3]
Определение
Структура представляет собой неориентированный граф , встроенная в г - мерное евклидово пространства, обеспечивая d -кратного в декартовой системе координат для каждой вершины графа. Из структуры с n вершинами и m ребрами можно определить матрицу с m строками и nd столбцами, расширенную версию матрицы инцидентности графа, называемую матрицей жесткости . В этой матрице запись в строке e и столбце ( v , i ) равна нулю, если v не является конечной точкой ребра e . Если, с другой стороны, у ребра e есть вершины u и v в качестве конечных точек, то значение записи - это разница между i- м координатами v и u . [1] [3]
Матроид жесткости данного каркаса является линейным матроидом , элементами которого являются ребра графа. Набор ребер является независимым в матроиде, если он соответствует линейно независимому набору строк матрицы жесткости . Каркас называется универсальным, если координаты его вершин являются алгебраически независимыми действительными числами. Любые две общие структуры на одном и том же графе G определяют один и тот же матроид жесткости, независимо от их конкретных координат. Это ( д - мерное) жесткость матроидом из G . [1] [3]
Статика
Нагрузка на структуры является система сил на вершинах (представлены в виде векторов). Стресс является частным случаем нагрузки, в которой равной и противоположных силы , приложенная к двум концам каждого ребра (которые могут быть воображаемыми как пружина) и сила , сформированная таким образом , добавляются в каждой вершине. Каждое напряжение представляет собой равновесную нагрузку , нагрузку, которая не оказывает ни поступательной силы на всю систему (сумма ее векторов сил равна нулю), ни какой-либо вращательной силы. Линейная зависимость между строками матрицы жесткости может быть представлена как самонапряжение , назначение равных и противоположных сил конечным точкам каждого ребра, которое не равно тождественно нулю, но прибавляет к нулю в каждой вершине. Таким образом, набор ребер образует независимый набор в матроиде жесткости тогда и только тогда, когда он не имеет собственного напряжения. [3]
Векторное пространство всех возможных нагрузок на систему из n вершин имеет размерность dn , среди которых равновесные нагрузки образуют подпространство размерности. Независимый набор в матроиде жесткости имеет систему равновесных нагрузок, размерность которой равна мощности набора, поэтому максимальный ранг, который может иметь любой набор в матроиде, равен. Если набор имеет этот ранг, это означает, что его набор напряжений совпадает с пространством равновесных нагрузок. В качестве альтернативы и эквивалентно, в этом случае каждая равновесная нагрузка на каркас может быть разрешена напряжением, которое создает равный и противоположный набор сил, и каркас считается статически жестким. [3]
Кинематика
Если вершины каркаса находятся в движении, то это движение может быть описано на небольших расстояниях с помощью его градиента , вектора для каждой вершины, определяющего ее скорость и направление. Градиент описывает линеаризованное приближение к фактическому движению точек, в котором каждая точка движется с постоянной скоростью по прямой. Градиент можно описать как вектор-строку, который имеет одну координату действительного числа для каждой пары. где является вершиной каркаса и - индекс одной из декартовых координат -габаритное пространство; то есть размер градиента такой же, как ширина матрицы жесткости. [1] [3]
Если предполагается, что края каркаса представляют собой жесткие стержни, которые не могут ни расширяться, ни сжиматься (но могут свободно вращаться), то любое движение с учетом этой жесткости должно сохранять длину краев: производную длины как функцию времени в течение при котором происходит движение, должно оставаться равным нулю. Это условие может быть выражено в линейной алгебре как ограничение, согласно которому вектор градиента движения вершин должен иметь нулевое внутреннее произведение со строкой матрицы жесткости, которая представляет данное ребро. Таким образом, семейство градиентов (бесконечно малых) жестких движений задается нулевым пространством матрицы жесткости. [1] [3] Для каркасов, которые не находятся в общем положении, возможно, что некоторые бесконечно жесткие движения (векторы в нулевом пространстве матрицы жесткости) не являются градиентами какого-либо непрерывного движения, но этого не может произойти для общих каркасов. [2]
Жесткое движение каркаса - это движение, при котором в каждый момент времени каркас соответствует своей исходной конфигурации. Жесткие движения включают переводы и вращения евклидова пространства; градиенты жестких движений образуют линейное пространство, имеющее в качестве оснований перемещения и вращения, размерности, которое всегда должно быть подпространством нулевого пространства матрицы жесткости. Поскольку нулевое пространство всегда имеет по крайней мере это измерение, матроид жесткости может иметь ранг не более, и когда он имеет этот ранг, единственными движениями, которые сохраняют длину ребер каркаса, являются жесткие движения. В этом случае каркас называется жестким первого порядка (или бесконечно малым). [1] [3] В более общем смысле, край принадлежит к операции замыкания матроида набора тогда и только тогда, когда не существует непрерывного движения каркаса, изменяющего длину но оставляет длину краев в без изменений. [1]
Хотя они определены в разных терминах (векторы столбцов и векторы-строки, или силы против движений), статическая жесткость и жесткость первого порядка сводятся к одним и тем же свойствам базовой матрицы и, следовательно, совпадают друг с другом. В двух измерениях общий матроид жесткости также описывает количество степеней свободы другого вида движения, в котором каждое ребро вынуждено оставаться параллельным своему исходному положению, а не ограничиваться сохранением той же длины; однако эквивалентность между жесткостью и параллельным движением нарушается в более высоких измерениях. [3]
Уникальная реализация
Каркас имеет уникальную реализацию в d -мерном пространстве, если каждое размещение одного и того же графа с одинаковыми длинами ребер конгруэнтно ему. Такой каркас обязательно должен быть жестким, потому что в противном случае существует непрерывное движение, приводящее его к несовпадающему положению с теми же длинами краев, но уникальная реализуемость сильнее жесткости. Например, ромбовидный граф (два треугольника с общим ребром) является жестким в двух измерениях, но его нельзя однозначно реализовать, потому что он имеет две разные реализации: в одной треугольники находятся на противоположных сторонах общего края, а в другой - они оба на одной стороне. Уникально реализуемые графики играют важную роль в приложениях , которые включают восстановление формы из расстояний, таких как триангуляции в землеустроительных, [4] определение позиций узлов в беспроводной сенсорной сети , [5] и восстановление конформации молекулы с помощью спектроскопия ядерного магнитного резонанса . [4]
Брюс Хендриксон определил, что граф является избыточно жестким, если он остается жестким после удаления любого из его ребер. В терминах матроидов это означает, что матроид жесткости имеет полный ранги что у матроида нет колупов. Хендриксон доказал, что каждый однозначно реализуемый каркас (с общей длиной ребер) является либо полным графом, либо- вершинно-связанный , избыточно жесткий граф, и он предположил, что это точная характеристика однозначно реализуемых каркасов. [6] Гипотеза верна для одного и двух измерений; в одномерном случае, например, граф однозначно реализуем тогда и только тогда, когда он связан и не имеет мостов . [7] Однако гипотеза Хенриксона неверна для трех или более измерений. [8] Для фреймворков, которые не являются общими, NP-сложно определить, является ли данный фреймворк однозначно реализуемым. [9]
Отношение к разреженности
Streinu & Theran (2009) определяют граф как-разрежьте, если каждый непустой подграф с вершин не более края и - герметично, если это - разреженный и ровно края. [10] Из рассмотрения нагрузок и напряжений можно увидеть, что набор ребер, который является независимым в матроиде жесткости, образует- разреженный граф, поскольку в противном случае существовал бы подграф, количество ребер которого превышало бы размерность его пространства равновесных нагрузок, из чего следует, что он имел бы самонапряжение. По аналогичным соображениям, набор ребер, который является как независимым, так и жестким, образуетплотный граф. Например, в одном измерении независимые множества образуют множества ребер лесов, (1,1) -резкие графы, а независимые жесткие множества образуют множества ребер деревьев, (1,1) -жатые графы. В этом случае матроид жесткости каркаса совпадает с графическим матроидом соответствующего графа. [2]
В двух измерениях Ламан (1970) показал, что верна та же характеристика: независимые множества образуют множества ребер (2,3) -разреженных графов, а независимые жесткие множества образуют множества ребер (2,3) -жильных графов. . [11] На основании этой работы (2,3) -грудные графы (графы минимально жестких общих каркасов в двух измерениях) стали известны как графы Ламана . Семейство графов Ламана на фиксированном множествевершины образуют набор баз матроида жесткости полного графа и, в более общем смысле, для каждого графа который образует жесткую основу в двух измерениях, остовные подграфы Ламана являются основаниями матроида жесткости .
Однако в более высоких измерениях не каждый -плотный граф является минимально жестким, и характеризация минимально жестких графов (основ матроида жесткости полного графа) является важной открытой проблемой. [12]
Рекомендации
- ^ Б с д е е г Гравер, Джек Е. (1991), "Жесткость матроиды", SIAM журнал по дискретной математике , 4 (3): 355-368, DOI : 10,1137 / 0404032 , МР 1105942.
- ^ а б в Уайтли, Уолтер (1992), "Матроиды и жесткие структуры", Приложения Matroid , Энциклопедия математики и ее приложений, 40 , Кембридж: Cambridge Univ. . Пресс, стр 1-53, DOI : 10,1017 / CBO9780511662041.002 , MR 1165538.
- ^ Б с д е е г ч I Whiteley, Вальтер (1996), "Некоторые матроиды из дискретной прикладной геометрии", матроидных теории (Сиэтл, Вашингтон, 1995) , Современная математика, 197 , Providence, RI: Американское математическое общество, стр 171-311,. Дои : 10,1090 / conm / 197/02540 , Руководство по ремонту 1411692.
- ^ а б Хендриксон, Брюс (1995), "Молекула проблема: использование структуры в глобальной оптимизации", SIAM журнал по оптимизации , 5 (4): 835-857, CiteSeerX 10.1.1.55.2335 , DOI : 10,1137 / 0805040 , MR 1358807.
- ^ Eren, T .; Гольденберг, ОК; Whiteley, W .; Ян, YR; Морс, А.С.; Андерсон, BDO; Belhumeur, PN (2004), "Жесткость, вычисление и рандомизация в сетевой локализации", Proc. Двадцать третья ежегодная Совместная конференция IEEE Computer и коммуникационных обществ (INFOCOM 2004) , 4 ., С 2673-2684, DOI : 10,1109 / INFCOM.2004.1354686.
- ^ Хендриксона, Брюс (1992), "Условие уникальных графиков реализаций", SIAM журнал по вычислениям , 21 (1): 65-84, DOI : 10,1137 / 0221008 , МР 1148818.
- ^ Джексон, Билл; Йордан, Тибор (2005), "Connected жесткость матроиды и уникальные реализации графов", Журнал комбинаторной теории , серии 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.
- ^ Ламан, Г. (1970), «О графах и жесткости плоских скелетных структур», J. Engineering Mathematics , 4 (4): 331–340, Bibcode : 1970JEnMa ... 4..331L , doi : 10.1007 / BF01534980 , Руководство по ремонту 0269535.
- ^ Джексон, Билл; Йордан, Тибор (2006), "О функции ранга в 3-мерной жесткости матроид" (PDF) , Международный журнал вычислительной геометрии и приложений , 16 (5-6): 415-429, DOI : 10,1142 / S0218195906002117 , MR 2269396.