Крепление сетки

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

Постановка задачи

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

В задаче рассматривается каркас в виде квадратной сетки с $r$ ряды и $c$ столбцы квадратов. Сетка имеет $r(c+1)+(r+1)c$ ребра, каждое из которых имеет единичную длину и считается жестким стержнем, свободно перемещающимся непрерывно внутри евклидовой плоскости , но не способным изменять свою длину. Эти стержни прикреплены друг к другу гибкими шарнирами. $(r+1)(c+1)$ вершины сетки. Действительныйнепрерывное движение этого каркаса — это способ непрерывного изменения расположения его краев и соединений в плоскости таким образом, чтобы они сохраняли одинаковую длину и одинаковые крепления, но без необходимости образовывать квадраты. Вместо этого каждый квадрат сетки может быть деформирован в ромб , а вся сетка может образовывать неправильную структуру с разной формой каждой из ее граней, как показано на рисунке.

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

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

Теоретико-графовое решение

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

Как первоначально заметили Итан Болкер и Генри Крапо ( 1977 ), проблему закрепления сетки можно перевести в задачу теории графов , рассматривая неориентированный двудольный граф , который имеет вершину для каждой строки и столбца данной сетки и ребро для каждого перекрестный квадрат сетки. Они доказали, что связная сетка является жесткой тогда и только тогда, когда этот двудольный граф связен. Отсюда следует, что минимальные перекрестные связи сетки соответствуют деревьям , соединяющим все вершины графа, и что они имеют ровно $r+c-1$ крестообразные квадраты. Любую перекосную, но жесткую поперечную связь (с количеством переплетенных квадратов, превышающим это количество) можно свести к минимальной поперечной связи, найдя остовное дерево ее графа.

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

Вариации

Двойное крепление

Другая версия проблемы требует «двойной распорки», набора поперечных распорок, который является достаточно избыточным, чтобы оставаться жестким, даже если одна из диагоналей будет удалена. Эта версия позволяет использовать обе диагонали одного квадрата, но это не обязательно.

В том же виде двудольного графа, который используется для решения проблемы связей, двойная связь сетки соответствует неориентированному двудольному мультиграфу , который является связным и не имеет мостов , что означает, что каждое ребро принадлежит хотя бы одному циклу . Минимальное количество диагоналей, необходимое для двойной связи, равно $\min(2r,2c)$.

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

Натяжная связь

Аналогичная теория с использованием ориентированных графов была открыта Дженни Багливо и Джеком Грейвером ( 1983 ) для натяжных связей , в которых квадраты скрепляются проволокой или веревками (которые не могут расширяться за пределы своей первоначальной длины, но могут сгибаться или сжиматься до более короткой длины). ) вместо жестких стержней. Чтобы сделать один квадрат жестким с помощью натяжных связей, необходимо связать обе его диагонали, а не только одну.

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

Если заданного набора фигурных скобок недостаточно, необходимо добавить дополнительные скобки, что в представлении графа соответствует добавлению ребер, которые соединяют вместе сильно связанные компоненты графа. Таким образом, проблему поиска минимального набора дополнительных фигурных скобок для добавления можно рассматривать как пример сильного увеличения связности и можно решить за линейное время . Согласно теореме Роббинса , неориентированные графы, которые можно сделать сильно связными, направляя их ребра, являются в точности графами без мостов; переинтерпретируя эту теорему с точки зрения связи сетки, связь жесткими стержнями образует двойную связь тогда и только тогда, когда каждый из ее стержней можно заменить одной проволокой (возможно, на другой диагонали своего квадрата), чтобы сформировать жесткую натяжную связь.

Внешние ссылки

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