В математике структурной жесткости , решетчатое крепление — это проблема добавления поперечных связей к квадратной сетке для превращения ее в жесткую структуру. Ее можно решить оптимально, переведя ее в задачу теории графов о связности двудольных графов . [1] [2] [3]
Задача рассматривает каркас в виде квадратной сетки с рядами и столбцами квадратов. Сетка имеет ребра, каждое из которых имеет единичную длину и считается жестким стержнем, свободно перемещающимся непрерывно в пределах евклидовой плоскости , но неспособным изменять свою длину. Эти стержни прикреплены друг к другу гибкими соединениями в вершинах сетки. Допустимое непрерывное движение этого каркаса — это способ непрерывного изменения расположения его ребер и соединений в плоскости таким образом, чтобы они сохраняли ту же длину и те же крепления, но не требовали от них образования квадратов. Вместо этого каждый квадрат сетки может быть деформирован, чтобы образовать ромб , и вся сетка может образовать нерегулярную структуру с разной формой для каждой из ее граней, как показано на рисунке. [1] [2] [3]
В отличие от квадратов, треугольники, сделанные из жестких стержней и гибких соединений, не могут менять свою форму: любые два треугольника со сторонами одинаковой длины должны быть конгруэнтны (это постулат SSS ). Если квадрат скреплен крестообразно путем добавления одной из его диагоналей в качестве еще одного жесткого стержня, диагональ разделит его на два треугольника, которые также не могут изменить форму, поэтому квадрат должен оставаться квадратным при любом непрерывном движении каркаса с крестообразными связями. (Тот же каркас можно также разместить на плоскости другим способом, сложив два его треугольника друг на друга по их общей диагонали, но это сложенное размещение не может быть получено непрерывным движением.) Таким образом, если все квадраты данной сетки скреплены крестообразными связями, сетка не может менять форму; ее единственными непрерывными движениями были бы ее вращение или перевод как единого жесткого тела . Однако этот метод придания жесткости сетке путем добавления крестообразных связей ко всем ее квадратам использует гораздо больше крестообразных связей, чем необходимо. Задача о распорках сетки требует описания минимальных наборов поперечных распорок, которые имеют тот же эффект, что и вся структура, делает ее жесткой. [1] [2] [3]
Как первоначально заметили Этан Болкер и Генри Крапо (1977), проблема растяжки сетки может быть переведена в задачу теории графов, если рассмотреть неориентированный двудольный граф , имеющий вершину для каждой строки и столбца данной сетки и ребро для каждого квадрата сетки с перекрещивающимися скобами. Они доказали, что сетка с перекрещивающимися скобами является жесткой тогда и только тогда, когда этот двудольный граф связен. Из этого следует, что минимальные перекрещивающиеся скобы сетки соответствуют деревьям, соединяющим все вершины в графе, и что они имеют ровно квадраты с перекрещивающимися скобами. Любая перекрещивающаяся, но жесткая перекрещивающаяся скоба (с большим, чем это число квадратов с перекрещивающимися скобами) может быть сведена к минимальной перекрещивающейся скобе, если найти остовное дерево ее графа. [1] [2] [3] [4]
В более общем случае предположим, что сетка с поперечными связями не является жесткой. Тогда число степеней свободы в ее семействе форм равно числу связанных компонентов двудольного графа минус один. Если частично связанную сетку нужно сделать жесткой, связав больше квадратов, минимальное число дополнительных квадратов, которые необходимо связать, равно этому числу степеней свободы. Решение с таким числом квадратов можно получить, добавив это число ребер к двудольному графу, соединив пары его связанных компонентов так, чтобы после добавления остался только один компонент. [1] [2] [3] [4]
Другая версия задачи требует «двойного укрепления», набора поперечных распорок, которые достаточно избыточны, чтобы оставаться жесткими, даже если одна из диагоналей будет удалена. Эта версия позволяет использовать обе диагонали одного квадрата, но это не обязательно. [1]
В том же представлении двудольного графа, которое используется для решения проблемы распорок, двойная распорка сетки соответствует неориентированному двудольному мультиграфу , который является связным и не имеет мостов , что означает, что каждое ребро принадлежит по крайней мере одному циклу . Минимальное количество диагоналей, необходимое для двойной распорки, равно . [1]
В частном случае сеток с равным числом строк и столбцов единственными двойными скобками такого минимального размера являются гамильтоновы циклы . Гамильтоновы циклы легко найти в полных двудольных графах, представляющих задачу о скобках, но их поиск в других двудольных графах является NP-полной задачей . Из-за этого нахождение наименьшего подмножества с двойными скобками большего раскоса является NP-трудной задачей . Однако возможно аппроксимировать это наименьшее подмножество с двойными скобками с точностью до постоянного отношения аппроксимации . [5]
Аналогичная теория, использующая направленные графы , была открыта Дженни Багливо и Джеком Грейвером (1983) для растяжки , в которой квадраты скреплены проволокой или струнами (которые не могут расширяться за пределы своей первоначальной длины, но могут сгибаться или сжиматься до более короткой длины) вместо жестких стержней. Чтобы сделать один квадрат жестким с помощью растяжки, необходимо скрепить обе его диагонали, а не только одну. [1] [2]
Можно представить растяжку двудольным графом, который имеет ребро, направленное от вершины строки к вершине столбца, если общий квадрат этой строки и столбца растянут диагональю с положительным наклоном, и ребро от вершины столбца к вершине строки, если общий квадрат растянут диагональю с отрицательным наклоном. Растянутая структура является жесткой тогда и только тогда, когда полученный граф сильно связан . [1] [2]
Если заданного набора распорок недостаточно, необходимо добавить дополнительные распорки, что в графовом представлении соответствует добавлению ребер, которые соединяют вместе сильно связанные компоненты графа. Таким образом, задача нахождения минимального набора дополнительных распорок для добавления может рассматриваться как пример увеличения сильной связности и может быть решена за линейное время . [6] Согласно теореме Роббинса , неориентированные графы, которые можно сделать сильно связанными, направляя их ребра, являются в точности графами без мостов; переосмысливая эту теорему в терминах решетчатых распорок, распорка жесткими стержнями образует двойную распорку тогда и только тогда, когда каждый из ее стержней можно заменить одним проводом (возможно, на другой диагонали ее квадрата) для образования жесткой распорки натяжения. [7]
