Кратко о сути проблемы. Под жёсткостью плоской каркасной сети $bar-and-jointframework$ обычно понимают свойство конструкции из жёстких стержней $ребёр$ и шарнирных узлов $вершин$ не иметь непрерывной деформации, сохраняющей длины стержней, кроме тривиальных жёстких движений плоскости $двухпараллельныхпереносовиповорот$. Для «общих» $generic$ положений вершин это свойство определяется только связностью графа, а не конкретными координатами — и для таких графов существует чисто комбинаторная критерий минимальной жёсткости $isostaticity$: теорема Ламана.

Формулировка условий Ламана $Laman’stheorem$

Граф G с n вершинами является минимально жёстким $минимальноизостатическим,Laman-графом$ для «общего» размещения вершин в плоскости тогда и только тогда, когда
1) число ребёр m = 2n − 3;
2) для всякого подмножества вершин X размера k ≥ 1 подсчитанное число ребёр в индуцированном подграфе G$$X$$ не превосходит 2k − 3 $обычноусловиесчитаетсядляk\ge 2;дляk=1онотривиально$.

Короткое объяснение смысла условий

Счёт степеней свободы: каждая вершина даёт 2 координаты → 2n степеней свободы; три тривиальные жёсткие движения $дветранспляции+поворот$ не ограничиваются ребрами, поэтому для изостатичности требуется m = 2n − 3 независимых ограничений. Это даёт необходимое условие.Условие на все подмножества исключает «локально перенасыщенные» части графа, где число ребер больше, чем нужно: такие части содержали бы зависимости $избыточныесвязи$, и граф не был бы минимальным.Достаточность $при«общих»размещениях$ доказывается конструктивно: любой Laman-граф может быть получен из треугольника Henneberg-операциями $типI:добавлениевершины,соединённойсдвумястарыми;типII:вставкавершины,разрезающейреброисоединяющейсястретьейвершиной$. Это обеспечивает индуктивную конструкцию всех Laman-графов и показывает, что при общих координатах они дают независимые ограничения → минимальная жёсткость.

Понятие «generic» $общего$ положения

Теорема Ламана и связанные с ней утверждения относятся к «generic» конфигурациям: координаты вершин не должны удовлетворять каким-то алгебраическим зависимостям $например,тривершинынележатстрогонаоднойпрямой,еслиэтосоздаётособыезависимости$. Формально — координаты берутся из множества, вне некоторого алгебраического многочлена нулей. При негeneric $вырожденных$ размещениях граф, удовлетворяющий ламановским числам, может оказаться гибким $появятсяособыедвижения$, а граф, не удовлетворяющий условиям, при специальных координатах может неожиданно оказаться жёстким.

Инфинитезимальная жёсткость и матрица жёсткости

Для анализа используется rigidity matrix $матрицаограниченияотносительныхскоростейвершинпорёбрам$. Для графа с m рёбрами и n вершинами матрица размера m × 2n. Ранг этой матрицы при generic-размещении равен 2n − 3 ↔ инфинитезимальная жёсткость $нетнетривиальныхбесконечномалыхперемещений$. Для generic-положений инфинитезимальная жёсткость эквивалентна локальной жёсткости (Asimow & Roth).

Примеры

Примеры, удовлетворяющие условию Ламана $минимальножёсткие$:
Треугольник K3: n = 3, m = 3 = 2·3 − 3. Жёсток и минимален.Четырёхвершинный граф «квадрат + одна диагональ» $илидватреугольника,пересекающиесяпоребру$: n = 4, m = 5 = 2·4 − 3; для любых k подграфы имеют ≤ 2k − 3 ребра. Это Laman-граф, даёт изостатическую структуру.Любой граф, полученный последовательностью Henneberg-операций от треугольника, будет Laman-графом.Примеры, не удовлетворяющие условию:
Дерево на n вершинах: m = n − 1 ≪ 2n − 3 — гибкая.Простий цикл C4 $квадратбездиагоналей$: n = 4, m = 4 < 5 — гибкий $может«скакать»какромб$.Граф K4 $полныйна4вершинах$: n = 4, m = 6 > 5. K4 при generic-положении жёсток, но не минимален — у него есть избыточные связи $онсверхжёсток$. Laman даёт критерий минимальной жёсткости; K4 не минимален, но он redundantly rigid $имеютсялишниеребра$.Важное замечание о вырожденных конфигурациях: граф, который по числам является Laman, может при неудачном $негенерическом$ расположении точек всё-таки оказаться гибким. Например, если несколько вершин лежат на одной прямой или расстояния устроены особым образом, матрица жёсткости может потерять ранг.

Различие между локальной/инфинитезимой и глобальной жёсткостью

Laman-графы гарантируют $приgeneric-$ локальную/инфинитезимальную жёсткость — нельзя «небольшими» движениями менять расстояния, кроме тривиальных. Но это не гарантирует единственности всей геометрической конфигурации при сохранении всех парных заданных расстояний $глобальнаяжёсткость$. Для того, чтобы граф задавал уникальную глобально $додвиженийплоскости$ конфигурацию, нужны более сильные условия: в плоскости существующая теорема (Jackson & Jordan) утверждает: для generic-framework граф глобально жёсток тогда и только тогда, когда он избыточно жёсток $redundantlyrigid$ и 3‑связен. Это важно для задач локализации по расстояниям и управления формацией роботов.

Применимость к инженерии и робототехнике

Проектирование ферм и фермовых конструкций $trussdesign$: Laman-графы соответствуют изостатическим $статическиопределимым$ плоским рамам — число ребёр минимально, чтобы обеспечить жёсткость. В инженерной практике это важно для анализа несущей способности, определения внутренних усилий: в изостатической конструкции внутренние усилия можно однозначно определить из уравнений равновесия. Однако на практике часто предпочитают иметь избыточность $избыточножёсткиеконструкции$ для надёжности и запасов прочности.Структурная оптимизация и экономичность: при желании минимизировать число стержней при сохранении жёсткости Laman-условие даёт критерий «минимально достаточной» сети; алгоритмически это проверяется pebble-game алгоритмами и конструкциями Henneberg для генерации допустимых топологий.Робототехника и распределённая формация $formationcontrol$ и сенсорные сети $sensornetworklocalization$: для восстановления положения агентов по измеренным взаимным расстояниям $distance-basedformation$ требуется, как минимум, локальная жёсткость графа $иначеформаможет«шевелиться»$. Для уникальной $глобальной$ локализации нужны условия глобальной жёсткости $redundantrigidity+3‑connectivityвплоскости$. На практике добавляют некоторые «якоря» $узлысизвестнымикоординатами$ или искусственно дублируют связи для обеспечения глобальной корректности.Ограничения практики: реальные стержни не идеальные шарниры; элементы имеют гибкость, допуски и нелинейные свойства; поэтому чисто комбинаторные критерии — хорошая модель первого приближения, но при детальном проектировании нужно учитывать упругость, устойчивость $buckling$, геометрию соединений, нагрузки и динамику. Кроме того, Laman-чисто комбинаторный критерий применим только для плоских рам и generic-случаев; в трёхмерном пространстве аналогичного простого полного критерия нет $задачагораздосложнее$.Алгоритмы и программные инструменты: для больших сетей используются алгоритмы pebble-game для проверки $2,3$-sparsity и выделения Laman-подграфов; решаются системы уравнений $непрерывнаяоптимизация,SNL—sensornetworklocalization$ и численная проверка ранга rigidity matrix. Для проектирования надёжных конструкций обычно комбинируют комбинаторные тесты с численным моделированием конечных элементов.

Короткое резюме практических рекомендаций

Если нужно минимально жёсткую $экономичную$ плоскую сеть — проектируйте Laman-граф $m=2n-3и(2,3)-sparsity$ и проверяйте Henneberg-построениями/pebble-game.Если важна надёжность/резерв — делайте избыточную жёсткость $redundantlyrigid$, чтобы избежать потери жёсткости при поломках.Если требуется однозначная локализация по расстояниям $вробототехнике,сенсорныхсетях$ — стремитесь к глобальной жёсткости $вплоскости:redundantrigidity+3‑connectivity$.Всегда проверяйте численно и учитывайте механические нюансы $упругость,шарниры,устойчивость$ — комбинаторный критерий даёт лишь идеализированную модель.

Полезные ключевые термины и ссылки для дальнейшего чтения $наанглийском$

Laman, G. $1970$. On graphs and rigidity of plane skeletal structures.Asimow, L. & Roth, B. — результаты об эквивалентности инфинитезимальной и локальной жёсткости для generic-положений.Henneberg constructions; pebble game algorithms (Lee & Streinu и др.).Jackson & Jordan — критерий глобальной жёсткости в плоскости.

Если хотите, могу:

показать несколько конкретных примеров $счисленнымикоординатами$ и продемонстрировать ранги rigidity-matrix;привести алгоритм pebble-game и показать, как им проверить Laman-условия на конкретном графе;обсудить отличия для 3D $почемунетаналогаЛамана$.