Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

В математике структурной жесткости , сетки распорка проблема добавления кросс распорки к квадратной сетке , чтобы превратить его в жесткую структуру. Она может быть решена оптимальным образом , переводя его в проблему , в теории графов на связи с двудольными графами . [1] [2] [3]

Формулировка проблемы [ править ]

Неограниченная квадратная сетка с шестью строками и четырьмя столбцами и неквадратная сетка, полученная в результате непрерывного ее движения.

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

Квадрат может изгибаться, образуя ромб , но треугольник образует жесткую структуру.

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

Теоретико-графическое решение [ править ]

Жесткая сетка с перекрестными скобками и соответствующий двудольный граф на вершинах, представляющий строки и столбцы сетки. Граф представляет собой дерево, поэтому в перекрестных связях используется минимально возможное количество квадратных скобок.

Как первоначально заметили Итан Болкер и Генри Крапо  ( 1977 ), проблема привязки сетки может быть преобразована в проблему теории графов, если рассмотреть неориентированный двудольный граф , имеющий вершину для каждой строки и столбца данной сетки и ребро для каждого квадратная скобка сетки. Они доказали, что сетка с перекрестными скобками является жесткой тогда и только тогда, когда этот двудольный граф связен. Отсюда следует, что минимальные перекрестные связи сетки соответствуют деревьям, соединяющим все вершины в графе, и что они имеют ровноквадратные скобки. Любые сверхкрепкие, но жесткие перекрестные связи (с числом квадратов в перекрестных скобках больше указанного) можно свести к минимальным перекрестным связям, найдя остовное дерево его графа. В более общем смысле, количество степеней свободы в форме сетки с поперечными связями равно количеству соединенных компонентов.двудольного графа, минус один. Если частично связанная сетка должна быть жесткой путем соединения большего количества квадратов, минимальное количество дополнительных квадратов, которые необходимо связать крестообразными связями, равно этому количеству степеней свободы, и решение с таким количеством квадратов может быть получено следующим образом: добавляя это количество ребер к двудольному графу, соединяя пары его компонент связности так, чтобы после сложения оставалась только одна компонента. [1] [2] [3] [4]

Другая версия проблемы требует «двойных распорок», набора поперечных распорок, которые достаточно избыточны, чтобы оставаться жесткими даже при удалении одной из диагоналей. Эта версия позволяет использовать обе диагонали одного квадрата, но это не обязательно. В этой версии двойное закрепление сетки точно так же соответствует неориентированному двудольному мультиграфу, который связан и не имеет мостов (каждое ребро принадлежит хотя бы одному циклу ). Минимальное количество диагоналей, необходимое для двойной распорки, составляет . [1] В частном случае сеток с равным количеством строк и столбцов единственными двойными связями такого минимального размера являются гамильтоновы циклы., поэтому определение того, существует ли он в более крупной распорке, является NP-полным . Однако можно приблизить наименьшее подмножество двойных распорок данной связи с постоянным коэффициентом приближения . [5]

Аналогичная теория, использующая ориентированные графы , была открыта Дженни Багливо и Джеком Грейвером ( 1983 ) для растяжек., в котором квадраты скреплены проволокой или веревкой (которые не могут расширяться сверх своей начальной длины, но могут изгибаться или сжиматься до меньшей длины) вместо жестких стержней. Чтобы сделать один квадрат жестким таким образом, необходимо связать обе его диагонали, а не только одну диагональ. Такое крепление можно снова представить в виде двудольного графа, у которого есть ребро, направленное от вершины строки к вершине столбца, если общий квадрат этой строки и столбца ограничен диагональю с положительным наклоном, а ребро - из вершины столбца. в вершину строки, если общий квадрат ограничен диагональю с отрицательным наклоном. Связанная структура является жесткой тогда и только тогда, когда полученный граф сильно связен . [1] [2]В противном случае необходимо добавить дополнительные распорки, чтобы соединить вместе прочно связанные компоненты . Проблема поиска минимального набора дополнительных фигурных скобок для добавления является примером сильного увеличения связности и может быть решена за линейное время . [6] Согласно теореме Роббинса , неориентированные графы, которые можно сделать сильно связными, направляя их ребра , в точности являются графами без мостов; переосмысливая эту теорему в терминах решетчатой ​​связи, связь жесткими стержнями образует двойную связь тогда и только тогда, когда ее стержни могут быть заменены проволокой (возможно, на других диагоналях их квадратов), чтобы сформировать жесткую связь растяжения. [7]

Ссылки [ править ]

  1. ^ a b c d e f Багливо, Дженни А .; Гравер, Джек Э. (1983), «3.10 Укрепляющие конструкции», Частота и симметрия в дизайне и архитектуре , Кембриджские городские и архитектурные исследования, Кембридж, Великобритания: Cambridge University Press, стр. 76–87, ISBN 9780521297844
  2. ^ a b c d e Гравер, Джек Э. (2001), Расчет на каркасы : математика для помощи при проектировании жестких структур , The Dolciani Mathematical Expositions, 25 , Вашингтон, округ Колумбия: Математическая ассоциация Америки, ISBN 0-88385-331-0, MR  1843781. См., В частности, разделы 1.2 («Проблема крепления сетки», стр. 4–12), 1.5 («Подробнее о задаче сетки», стр. 19–22), 2.6 («Решение проблемы сетки», стр. 50–55) и 4.4 («Тенсегрити: скобы натяжения», в частности стр. 158–161).
  3. ^ a b c d Каппрафф, Джей (2001), «4.18 Укрепляющие конструкции» , Соединения: геометрический мост между искусством и наукой , серия о узлах и всем остальном, 25 (2-е изд.), Сингапур: World Scientific, стр. 154– 159, ISBN 9789810245856, Руководство по ремонту  1868159
  4. ^ Bolker, ED; Крапо, Х. (1977), «Как укрепить одноэтажное здание», Environment and Planning B: Planning and Design , 4 (2): 125–152, doi : 10.1068 / b040125
  5. ^ Cheriyan, J .; Seb, A .; Сигети, Z. (2001), "Повышение на 1,5-аппроксимации наименьшего 2-края связного остовного подграфа", SIAM журнал по дискретной математике , 14 (2): 170-180, DOI : 10,1137 / S0895480199362071 , МР 1856004 
  6. ^ Габоу, Гарольд Н .; Йордан, Тибор (2000), "Как сделать квадратные рамки сетки с кабелями жестких", SIAM журнал по вычислениям , 30 (2): 649-680, DOI : 10,1137 / S0097539798347189 , MR 1769375 
  7. ^ Роббинс, HE (1939), "Теорема о графах, с приложением к проблеме управления движением", American Mathematical Monthly , 46 (5): 281–283, DOI : 10.2307 / 2303897 , JSTOR 2303897 

Внешние ссылки [ править ]

  • Уитти, Робин, "Теорема о прямоугольных тенсегритах" (PDF) , Теорема дня