Матроид жесткости - Rigidity matroid

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

Определение

А рамки является неориентированный граф, встроенный в d-мерное евклидово пространство, предоставляя d-набор Декартовы координаты для каждой вершины графа. Из фреймворка с п вершины и м ребер, можно определить матрицу с м ряды и nd столбцы, расширенная версия матрица инцидентности графа, называемого матрица жесткости. В этой матрице запись в строке е и столбец (v,я) равно нулю, если v не конечная точка края е. Если, с другой стороны, край е имеет вершины ты и v как конечные точки, тогда значение записи - это разница между яth координаты v и ты.^[1][3]

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

Статика

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

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

Кинематика

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

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

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

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

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

В ромбовидный график, в общем жесткий, но не однозначно реализуемый

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

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

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

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

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

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

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

1. Грейвер, Джек Э. (1991), «Матроиды с жесткостью», Журнал SIAM по дискретной математике, 4 (3): 355–368, Дои:10.1137/0404032, МИСТЕР  1105942.
2. Уайтли, Уолтер (1992), «Матроиды и жесткие конструкции», Приложения Matroid, Энциклопедия математики и ее приложений, 40, Кембридж: Cambridge Univ. Press, стр. 1–53, Дои:10.1017 / CBO9780511662041.002, МИСТЕР  1165538.
3. Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995), Современная математика, 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, Дои:10.1090 / conm / 197/02540, МИСТЕР  1411692.
4. Хендриксон, Брюс (1995), "Проблема молекулы: использование структуры в глобальной оптимизации", SIAM Journal по оптимизации, 5 (4): 835–857, CiteSeerX  10.1.1.55.2335, Дои:10.1137/0805040, МИСТЕР  1358807.
5. Eren, T .; Goldenberg, O.K .; Whiteley, W .; Ян, Ю.Р .; Морс, A.S .; Anderson, B.D.O .; Belhumeur, P.N. (2004), «Жесткость, вычисление и рандомизация в локализации сети», Proc. Двадцать третья ежегодная совместная конференция компьютерных и коммуникационных обществ IEEE (ИНФОКОМ 2004), 4, стр. 2673–2684, Дои:10.1109 / INFCOM.2004.1354686.
6. Хендриксон, Брюс (1992), "Условия уникальной реализации графов", SIAM Журнал по вычислениям, 21 (1): 65–84, Дои:10.1137/0221008, МИСТЕР  1148818.
7. Джексон, Билл; Йордан, Тибор (2005), «Матроиды связанной жесткости и уникальные реализации графов», Журнал комбинаторной теории, Серия B, 94 (1): 1–29, Дои:10.1016 / j.jctb.2004.11.002, МИСТЕР  2130278.
8. Коннелли, Роберт (1991), "Об общей глобальной жесткости", Прикладная геометрия и дискретная математика, Серия DIMACS по дискретной математике и теоретической информатике, 4, Провиденс, Род-Айленд: Американское математическое общество, стр. 147–155, МИСТЕР  1116345.
9. Сакс, Дж. Б. (1979), Встраиваемость взвешенных графов в k-пространство сильно NP-сложно, Технический отчет, Питтсбург, Пенсильвания: Департамент компьютерных наук, Университет Карнеги-Меллон. Как цитирует Джексон и Джордан (2005).
10. Стрейну, И.; Теран, Л. (2009), "Разреженные гиперграфы и алгоритмы игры в гальку", Европейский журнал комбинаторики, 30 (8): 1944–1964, arXiv:математика / 0703921, Дои:10.1016 / j.ejc.2008.12.018.
11. Ламан, Г. (1970), «О графах и жесткости плоских скелетных структур», J. Инженерная математика, 4 (4): 331–340, Bibcode:1970JEnMa ... 4..331L, Дои:10.1007 / BF01534980, МИСТЕР  0269535.
12. Джексон, Билл; Йордан, Тибор (2006), «О ранговой функции трехмерного матроида жесткости» (PDF), Международный журнал вычислительной геометрии и приложений, 16 (5–6): 415–429, Дои:10.1142 / S0218195906002117, МИСТЕР  2269396.