Теорема Гейрингера – Ламана.

Теорема Гейрингера -Ламана дает комбинаторную характеристику генерически жестких графов в $2$-мерное евклидово пространство относительно стержневых каркасов . Эта теорема была впервые доказана Хильдой Поллачек-Гейрингер в 1927 году. а затем Джерардом Ламаном в 1970 году. эффективный алгоритм под названием Pebble Game . Для идентификации этого класса графов используется Эта теорема послужила источником вдохновения для многих результатов типа Гейрингера-Ламана для других типов структур с обобщенными играми Pebble.

Формулировка теоремы

Эта теорема основана на определениях универсальности, которые можно найти на странице структурной жесткости . Позволять $V(E)$ обозначают множество вершин набора ребер $E$.

Теорема Гейрингера-Ламана. График $G=(V,E)$ в целом является жестким в $2$-размеры относительно стержневых каркасов тогда и только тогда, когда $G$ имеет охватывающий подграф $G'=(V,E')$ такой, что

• $|E'|=2|V|-3$
• для всех подмножеств $F\subset E'$, $|F|\leq 2|V(F)|-3$.

Рис. 1. (а) и (в) — в общем случае жесткие графы в $2$-размеры. (b) является обобщенно гибким графом в $2$-размеры.

Охватывающий подграф $G'$ удовлетворяющий условиям теоремы, называется графом Гейрингера-Ламана, или минимально жестким, графом. Графы, удовлетворяющие второму условию, образуют независимые множества матроида разреженности и называются $(2,3)$-редкий. Граф, удовлетворяющий обоим условиям, также называется $(2,3)$-плотный график. Направление теоремы, утверждающей, что вообще-жесткий граф $(2,3)$-плотное называется направлением Максвелла, потому что Джеймс Клерк Максвелл дал аналогичное необходимое условие $\textstyle {\big (}d,{d+1 \choose 2}{\big )}$- разреженность для того, чтобы граф был независимым в $d$-мерный общий матроид жесткости . Другое направление теоремы доказать труднее. По размерам $d\geq 3$, график, который $\textstyle {\big (}d,{d+1 \choose 2}{\big )}$-плотно не обязательно в общем случае минимально жестко, т. е. обратное направление Максвелла неверно.

Пример. Рассмотрим графики на рисунке 1. Граф (c) в общем случае является минимально жестким, но не бесконечно жестким. Красные векторы скорости изображают нетривиальный бесконечно малый изгиб. Удаление красного ребра в (a) дает в общем минимально жестком остовном графе. Добавление пунктирного красного края в (b) делает граф в общем минимально жестким.

Теорема. Позволять $G$ быть графиком. Следующие утверждения эквивалентны:

• $G$ является в общем случае минимально жестким;
• $G$ является $(2,3)$-тугой; и
• $G$ содержит три непересекающихся по ребрам остовных дерева $T_{1},T_{2},$ и $T_{3}$ такой, что (i) каждая вершина $G$ содержится ровно в двух из этих остовных деревьев и (ii) разные поддеревья этих остовных деревьев не имеют одинакового набора вершин.

Эквивалентность первого и второго утверждений есть теорема Гейрингера-Ламана. Эквивалентность первого и третьего утверждений была впервые доказана Крапо с помощью теоремы Гейрингера-Ламана: а позже Тэй, используя более прямой подход.

Схема доказательства

Приведенное ниже доказательство теоремы Гейрингера-Ламана основано на доказательстве Ламана. Кроме того, детали приведенных ниже доказательств основаны на конспектах лекций, найденных здесь.

Рассмотрим систему стержневых соединений. $(G=(V,E),\delta )$ и рамки $(G,p)$ этой системы, где $p:V\rightarrow \mathbb {R} ^{2|V|}$ это карта, на которой расположены вершины $G$ в плоскости так, что ограничения на расстояние $\delta$ удовлетворены. Для удобства мы обратимся к $p$ как основа $G$. Доказательство теоремы Гейрингера-Ламана следует схеме, приведенной ниже.

1. График $G$ является генерически жесткой тогда и только тогда, когда оно генерически бесконечно мало жестко.
   1. Бесконечно малая жесткость — общее свойство графов .
   2. Жесткость — это общее свойство графов.
   3. Если структура $(G,p)$ бесконечно жестко, то оно жестко.
   4. Если структура $(G,p)$ является общим относительно бесконечно малой жесткости и жестким, то оно бесконечно жесткое.
2. Если график $G$ имеет общую бесконечно малую жесткую структуру, то $G$ является графом Гейрингера-Ламана.
3. График $G$ является графом Гейрингера-Ламана тогда и только тогда, когда $G$ имеет конструкцию Геннеберга.
4. Если график $G$ имеет конструкцию Геннеберга, то $G$ имеет общий бесконечно малый жесткий каркас.

Шаг 1 устанавливает общие настройки жесткости, чтобы мы могли сосредоточиться на общей бесконечно малой жесткости, а не на общей жесткости. Это более простой подход, поскольку бесконечно малая жесткость включает систему линейных уравнений, а не квадратных в случае регулярной жесткости. В частности, мы можем доказать структурные свойства матрицы жесткости типового каркаса. Эти результаты были впервые доказаны Азимовым и Ротом. см. Комбинаторные характеристики обобщенно жестких графов . Обратите внимание, что на этапе 1.4 каркас должен быть общим в отношении бесконечно малой жесткости. В частности, рамки $(G,p)$ то, что является жестким и универсальным по отношению к жесткости, не обязательно является бесконечно малым. Шаг 2 — это максвелловское направление доказательства, которое следует из простых рассуждений по подсчету матрицы жесткости. Шаг 3 показывает, что минимально жесткие графы в общем случае — это именно те графы, которые можно построить, начиная с одного ребра, с помощью двух простых операций, которые определены ниже. Шаг 4 показывает, что графы с такой конструкцией в общем случае бесконечно малы. Наконец, как только шаг 1 доказан, шаги 2–3 доказывают теорему Гейрингера-Ламана.

Эквивалентность общей жесткости и общей бесконечно малой жесткости

Позволять $G=(V,E)$ быть графиком. Во-первых, мы показываем, что общие каркасы относительно бесконечно малой жесткости образуют открытое и плотное множество в $\mathbb {R} ^{2|V|}$. Одно необходимое и достаточное условие фреймворка $p$ из $G$ быть бесконечно жестким для своей матрицы жесткости $R(p)$ иметь максимальный рейтинг среди всех фреймворков $G$.

Предложение 1. Для любого каркаса $p$ из $G$ и любой район $N(p)$, существует структура $q$ в $N(p)$ такая, что матрица жесткости $R(q)$ имеет максимальный ранг.

Доказательство. Если матрица жесткости $R(p)$ не имеет максимального ранга, то у него есть набор зависимых строк, соответствующих подмножеству ребер $E'\subset E$ такая, что для некоторой другой матрицы жесткости $R(q)$, строки, соответствующие $E'$ независимы. Позволять ${\mathcal {X}}_{E'}$ — набор каркасов таких, что строки, соответствующие $E'$ в них матрицы жесткости являются зависимыми. Другими словами, ${\mathcal {X}}_{E'}$ это набор фреймворков $p$ такая, что минорная из строк, соответствующих $E'$ в $R(p)$ является $0$. Следовательно, ${\mathcal {X}}_{E'}$ представляет собой кривую в $\mathbb {R} ^{2|V|}$, поскольку минор — это полином от элементов матрицы. Позволять ${\mathcal {X}}$ — объединение этих кривых по всем подмножествам ребер $E$. Если структура $R(p)$ не имеет максимального ранга для некоторых фреймворков $p$, затем $p$ содержится в ${\mathcal {X}}$. Наконец, поскольку ${\mathcal {X}}$ — конечное множество кривых, предложение доказано.

Предложение 2. Бесконечно малая жесткость — общее свойство графов.

Доказательство. Мы показываем, что если одна общая структура относительно бесконечно малой жесткости является бесконечно малой жесткостью, то все общие структуры являются бесконечно малыми. Если структура $p$ графика $G$ бесконечно жестко, то $R(p)$ имеет максимальный ранг. Заметим, что ядром матрицы жесткости является пространство бесконечно малых движений каркаса, имеющее размерность ${3 \choose 2}$ для бесконечно малых каркасов. Следовательно, согласно теореме ранга-нулевой , если одна общая структура является бесконечно малой жесткостью, то все общие структуры имеют бесконечно малую жесткость и обладают жесткостью.

Предложение 3. Если каркас $p$ графика $G$ бесконечно жестко, то оно жестко.

Доказательство. Предположим, что $p$ не является жестким, поэтому существует каркас $q$ в районе $N(p)$ такой, что $\rho (p)=\rho (q)$ и $q$ невозможно получить тривиальным движением $p$. С $q$ находится в $N(p)$, существует $\delta >0$ и $\|h\|<\delta$ такой, что $q=p+h$. Применение некоторой алгебры дает:

${\begin{aligned}\rho (p)_{ij}-\rho (q)_{ij}&=\|p_{i}-p_{j}\|^{2}-\|q_{i}-q_{j}\|^{2}\\&=\|h_{i}-h_{j}\|^{2}-2(p_{i}-p_{j})(h_{i}-h_{j})\\&=0.\end{aligned}}$

Следовательно,

${\frac {\|h_{i}-h_{j}\|^{2}}{\|h\|}}=2(p_{i}-p_{j}){\frac {(h_{i}-h_{j})}{\|h\|}}=0.$

Мы можем выбрать последовательность $\delta _{n}$ такой, что $\delta _{n+1}<\delta _{n}$ и $\lim _{n\rightarrow \infty }\delta _{n}=0$. Это вызывает $\lim _{n\rightarrow \infty }\|h_{n}\|=0$ и $\lim _{n\rightarrow \infty }{\frac {\|h_{n,i}-h_{n,j}\|^{2}}{\|h_{n}\|}}=(h_{i}^{\star }-h_{j}^{\star })$. Следовательно,

${\begin{aligned}2(p_{i}-p_{j})(h_{i}^{\star }-h_{j}^{\star })&=\lim _{n\rightarrow \infty }2(p_{i}-p_{j}){\frac {\|h_{n,i}-h_{n,j}\|^{2}}{\|h_{n}\|}}\\&=\lim _{n\rightarrow \infty }{\frac {\|h_{n,i}-h_{n,j}\|^{2}}{\|h_{n}\|}}\\&=0.\end{aligned}}$

Первое и последнее выражения в приведенных выше уравнениях гласят, что $h^{\star }$ это бесконечно малое движение каркаса $p$. Поскольку тривиального движения между $p$ и $q$, $h^{\star }$ не является тривиальным бесконечно малым движением. Таким образом, $p$ не является бесконечно жестким.

Предложение 4. Если каркас $p$ графика $G$ является жестким и общим относительно бесконечно малой жесткости, то $p$ является бесконечно жестким.

Доказательство. Это следует из теоремы о неявной функции . Сначала выделим все тривиальные движения $p$. С $R(p)$ имеет максимальный ранг, нет $3$ точки $p$ коллинеарны. Следовательно, мы можем закрепить $2$ точки $p$ выделить тривиальные движения: одну точку в начале координат, другую вдоль $x$-ось на расстоянии от начала координат, согласующемся со всеми ограничениями. Это дает закрепленную структуру $q$ который живет в $\mathbb {R} ^{2|V|-3}$. Это можно сделать для всех фреймворков в округе. $N(p)$ из $p$ чтобы получить соседство $N(q)$ из $q$ закрепленных рамок. Набор таких каркасов по-прежнему представляет собой гладкое многообразие , поэтому карту жесткости и матрицу жесткости можно переопределить в новой области. В частности, матрица жесткости $R(q)$ закрепленной структуры $q$ имеет $2|V|-3$ столбцы и ранг, равный $R(p)$, где $p$ это незакрепленная структура, соответствующая $q$. В этой закрепленной настройке каркас является жестким, если он является единственным ближайшим решением карты жесткости.

Теперь предположим, что незакрепленная структура $p$ не является бесконечно жестким, так что $rank(R(p))=k<2|V|-3$. Тогда $rank(R(q))=k$, где $q$ это закрепленная версия $p$. Теперь мы готовы применить теорему о неявной функции. Наша непрерывно дифференцируемая функция — это отображение жесткости $\rho :\mathbb {R} ^{2|V|-3}\rightarrow \mathbb {R} ^{|E|}$. Якобиан ​ ​ $\rho$ – матрица жесткости. Рассмотрим подмножество ребер $E'\subset E$ соответствующий $k$ независимые ряды $R(q)$, что дает подматрицу $R(q)_{E'}$. Мы можем найти $k$ независимые столбцы $R(q)_{E'}$. Обозначим записи в этих столбцах векторами $y=y_{1},\dots ,y_{k}$. Обозначим записи остальных столбцов векторами $x=x_{1},\dots ,x_{2|V|-3-k}$. $k\times k$ подматрица $R(q)_{E'}$ вызвал $y_{1},\dots ,y_{k}$ обратима, поэтому по теореме о неявной функции существует непрерывно дифференцируемая функция $g$ такой, что $y=g(x)$ и $\rho (x,y)_{E'}=\rho (q)_{E'}$. Следовательно, рамки $q_{E'})$ подграфа $G'=(V,E')$ не является жестким, и поскольку ряды $R(q)_{E'}$ охватывать пространство строк $R(q)$, $q$ также не является жестким. Это противоречит нашему предположению, поэтому $p$ является бесконечно жестким.

Предложение 5. Жесткость — общее свойство графов.

Доказательство. Позволять $p$ быть жестким каркасом $G$ это является общим с точки зрения жесткости. По определению существует окрестность жестких рамок $N(p)$ из $p$. По предложению 1 существует основа $q$ в $N(p)$ является общим относительно бесконечно малой жесткости, поэтому по предложению 4 $q$ является бесконечно жестким. Следовательно, по предложению 2 все каркасы общего положения относительно бесконечно малой жесткости являются бесконечно малыми, а по предложению 3 они также являются жесткими. Наконец, каждый район $N(p')$ каждой структуры $p'$ общий по жесткости, содержит каркас $q'$ которое является общим относительно бесконечно малой жесткости по предложению 1. Таким образом, если $p$ тогда он жесткий $p'$ является жестким.

Рисунок 2. Визуализация обоих направлений доказательства теоремы 1. (a) также изображает доказательство предложения 5.

Теорема 1. Граф $G$ является генерически жесткой тогда и только тогда, когда оно генерически бесконечно мало жестко.

Доказательство. Доказательство проводится аналогично доказательству предложения 5. Если $G$ является в общем жестком, то существует общая структура $p$ относительно жесткости, которая является жесткой по определению. По предложениям 1 и 4 в любой окрестности $p$ есть рамки $q$ это является общим относительно бесконечно малой жесткости и бесконечно малой жесткости. Следовательно, по предложению 2 $G$ в общем случае является бесконечно малым жестким.

Для другого направления предположим противное, что $G$ является в общем бесконечно малой жесткостью, но не в общем случае. Тогда существует общая структура $p$ относительно жесткости, которая не является жесткой по определению. По предложению 1 в любой окрестности $p$ есть рамки $q$ это является общим относительно бесконечно малой жесткости. По предположению $q$ бесконечно жестко, и по предложению 3 $q$ также является жестким. Таким образом, $p$ должна быть жесткой, и согласно предложению 5 все модели общего положения относительно жесткости являются жесткими. Это противоречит нашему предположению, что $G$ в целом не является жестким.

Максвелловское направление

Направление Максвелла в теореме Гейрингера-Ламана следует из простого аргумента подсчета матрицы жесткости.

Максвелловское направление. Если график $G$ имеет общую бесконечно малую жесткую структуру, то $G$ имеет подграф Гейрингера-Ламана.

Доказательство. Позволять $p$ быть общей бесконечно малой жесткой структурой $G$. По определению, $R(p)$ имеет максимальный ранг, т.е. $rank(R(p))=2|V|-3$. В частности, $R(p)$ имеет $2|V|-3$ независимые строки. Каждый ряд $R(p)$ соответствует краю $G$, поэтому подматрица $R(p)_{G'}$ только с независимыми строками соответствует подграфу $G'=(V,E')$ такой, что $|E'|=2|V|-3$. Более того, любой подграф $H=(V',F)$ из $G'$ соответствует подматрице $R(p)_{H}$ из $R(p)_{G'}$. Поскольку ряды $R(p)_{G'}$ независимы, как и строки $R(p)_{H}$. Следовательно, $rank(R(p)_{H})=|F|$, что явно удовлетворяет $|F|\leq 2|V(F)|-3$.

Эквивалентность типичной бесконечно малой жесткости и конструкций Геннеберга

Теперь мы начнем доказательство другого направления теоремы Гейрингера-Ламана с того, что сначала покажем, что минимально жесткий граф в общем случае имеет конструкцию Хеннеберга. Граф Хеннеберга $G$ имеет следующее рекурсивное определение:

1. $G$ представляет собой одно ребро или
2. $G$ можно получить из графа Хеннеберга $G'$ с помощью одной из следующих операций
   1. добавить вершину в $G'$ и подключите его к $2$ отдельные вершины $G'$
   2. Для преимущества $(u,v)$ и вершина $w$ из $G'$, добавьте вершину в $G'$, подключите его к $u,v,$ и $w$, а затем удалите $(u,v)$.

Две вышеописанные операции называются $0$-расширение и $1$-расширение соответственно.

Следующие предложения доказаны в:

Предложение 6. Минимально жесткий граф в общем случае не имеет вершины степени $1$ и хотя бы одна вершина со степенью меньше $4$

Предложение 7. Если $G$ является минимально жестким графом в общем случае с вершиной $v$ степени $3$, соединенный с вершинами $u_{1},u_{2},$ и $u_{3}$, то хотя бы для одной пары соседей $v$, без ограничения общности скажем $(u_{1},u_{2})$, нет подграфа $G'=(V',E')$ из $G$ который содержит $u_{1}$ и $u_{2}$ и удовлетворяет $|F|=2|U|-3$.

Теорема 2. Минимально жесткий граф в общем случае $G$ по крайней мере $2$ вершин имеет конструкцию Геннеберга.

Доказательство. Действуем индукцией по числу вершин $|V|$. Базовый случай $|V|=2$ — это граф Хеннеберга в базовом случае. Предполагать $G=(V,E)$ имеет конструкцию Геннеберга, когда $|V|=k$ и мы докажем это для $|V|=k+1$. Когда $|V|=k+1$, $G$ имеет вершину $v$ со степенью $2$ или $3$, по предложению 6.

Случай 1: $v$ имеет степень 2.

Позволять $G'=(V',E')$ быть подграфом $G$ полученный путем удаления $v$, так $|V'|=|V|-1$ и $|E'|=|E|-2$. С $G$ минимально жестко, имеем

$|E'|=|E|-2=2|V|-3-2=2|V'|-3.$

Более того, любой подграф $H=(V'',F)$ из $G'$ также является подграфом $G$, так $|F|\leq 2|V''|-4,$ по предположению. Следовательно, $G'$ является минимально жестким по направлению Максвелла и $G'$ имеет конструкцию Геннеберга по индуктивному предположению. Теперь просто заметьте, что $G$ можно получить из $G'$ далеко в $0$-расширение.

Случай 2: $v$ имеет степень 3.

Пусть ребра, инцидентные $v$ быть $(v,u_{1}),(v,u_{2}),$ и $(v,u_{3})$. По предложению 7 для одной пары соседей $v$, без ограничения общности скажем $(u_{1},u_{2})$, нет подграфа $H=(U,F)$ из $G$ который содержит $u_{1}$ и $u_{2}$ и удовлетворяет $|F|=2|U|-3$. Обратите внимание, что $(u_{1},u_{2})$ не может быть ребром, иначе подграф именно на этом ребре удовлетворяет предыдущему равенству. Рассмотрим график $G'=(V',E')$ полученный путем удаления $v$ от $G$ и добавляем край $(u_{1},u_{2})$. У нас есть

$|E'|=|E|-3+1=2|V|-3-2=2|V'|-3$.

Более того, как и в случае 1, любой подграф $G'$ который не содержит $(u_{1},u_{2})$ по предположению удовлетворяет второму условию минимальной жесткости. Для подграфа $G''=(V'',E'')$ который содержит $(u_{1},u_{2})$, удаление этого ребра дает подграф $G'''=(V''',E''')$ из $G$. По предложению 7 $|E'''|\leq 2|V'''|-2$, так $|E''|\leq 2|V''|-3$. Следовательно, $G'$ является минимально жестким и $G'$ имеет конструкцию Геннеберга по индуктивному предположению. Наконец, обратите внимание, что $G$ можно получить из $G'$ далеко в $1$-расширение.

Объединение случаев 1 и 2 доказывает теорему по индукции.

Обратить теорему 2 также легко по индукции.

Предложение 8. Граф конструкции Хеннеберга в общем случае является минимально жестким.

Конструируемые графы Хеннеберга в общем случае бесконечно малы.

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

Предложение 9. Если $p_{1},p_{2},p_{3}$ три неколлинеарных $2$-мерные точки и $u_{1},u_{2},u_{3}$ три $2$-мерные векторы, то следующие утверждения эквивалентны:

• $(p_{i}-p_{j})\cdot (u_{i}-u_{j})=0$ для всех $i,j\in \{1,2,3\}$
• Функция

$f(p)={\begin{vmatrix}p-p_{1}&(p-p_{1})\cdot u_{1}\\p-p_{2}&(p-p_{2})\cdot u_{2}\\p-p_{3}&(p-p_{3})\cdot u_{3}\end{vmatrix}}$

исчезает в каждой точке $p$.

Теорема 3. Если граф $G$ по крайней мере $3$ вершин имеет конструкцию Геннеберга, то $G$ в общем случае является бесконечно малым жестким.

Доказательство. Действуем индукцией по числу вершин $|V|$. График в базовом случае $|V|=3$ представляет собой треугольник, который в общем случае является бесконечно малым жестким. Предположим, что когда $|V|=k$ $G$ в общем случае является бесконечно малым жестким, и мы докажем это для $k+1$. Для $|V|=k+1$, рассмотрим график $G'=(V',E')$ что $G$ было получено через $0$- или $1$-расширение. По индуктивному предположению, $G'$ в общем случае является бесконечно малым жестким. Следовательно, $G'$ имеет общую бесконечно жесткую структуру $p'\in \mathbb {R} ^{2k}$ такое, что ядро $R(p')$ имеет размерность $3$. Позволять $v$ быть вершиной, добавленной к $G'$ чтобы получить $G$. Нам нужно выбрать место размещения $p_{v}$ в $2$-размеры такие, что $p=p'\cup p_{v}$ представляет собой общую бесконечно малую жесткую структуру $G$.

Случай 1: $G$ получается из $G'$ далеко в $0$-расширение.

Выбирая такое место для $p_{v}$ эквивалентно добавлению строк, соответствующих уравнениям

${\begin{aligned}&(p_{v}-p_{u})\cdot (q_{v}-q_{u})=0\\&(p_{v}-p_{w})\cdot (q_{v}-q_{w})=0\end{aligned}}$

к матрице жесткости $R(p')$, где $u$ и $w$ являются соседями $v$ после $0$-расширение и $q_{v}$ это скорость, присвоенная $p_{v}$ бесконечно малым движением. Наша цель – выбрать $p_{v}$ такова размерность пространства бесконечно малых движений $R(p)$ такое же, как и у $R(p')$. Мы можем выбрать $p_{v}$ так, что оно не коллинеарно $p_{u}$ и $p_{w}$, что гарантирует наличие только одного решения этих уравнений. Следовательно, ядро $R(p)$ имеет размерность $3$, так $p$ представляет собой общую бесконечно малую жесткую структуру $G$.

Случай 2: $G$ получается из $G'$ далеко в $1$-расширение.

Пусть соседи $v$ после $1$-расширение по краям $(v,u_{1}),(v,u_{2})$, и $(v,u_{3})$, и пусть $(u_{1},u_{2})$ быть ребром, который был удален. Удаление края $(u_{1},u_{2})$ от $G'$ дает подграф $G''$. Позволять $p''$ быть основой $G''$ это эквивалентно $p'$, кроме удаленного края. Матрица жесткости $R(p'')$ можно получить из $R(p')$ удалив строку, соответствующую удаленному ребру. По предложению 8 $G'$ в общем случае минимально жёсткий, поэтому строки $R(p')$ независимы. Следовательно, строки $R(p'')$ независимы и его ядро ​​имеет размерность $4$. Позволять $\lambda _{1},\lambda _{2},\lambda _{3},\lambda _{4}$ быть базисным вектором пространства бесконечно малых движений $p''$ такой, что $\lambda _{1},\lambda _{2},\lambda _{3}$ является основой пространства тривиальных бесконечно малых движений. Тогда любое бесконечно малое движение $p''$ можно записать как линейную комбинацию этих $4$ базисные векторы. Выбор места для $p_{v}$ что приводит к созданию общей бесконечно жесткой структуры $G$ эквивалентно добавлению строк, соответствующих уравнениям

${\begin{aligned}&(p_{v}-p_{u_{1}})\cdot (q_{v}-q_{u_{1}})=0\\&(p_{v}-p_{u_{2}})\cdot (q_{v}-q_{u_{2}})=0\\&(p_{v}-p_{u_{3}})\cdot (q_{v}-q_{u_{3}})=0\end{aligned}}$

к матрице жесткости $R(p'')$. Наша цель – выбрать $p_{v}$ такова размерность пространства бесконечно малых движений $R(p)$ является $1$ меньше, чем у $R(p'')$. После перестановки эти уравнения имеют решение тогда и только тогда, когда

${\begin{vmatrix}p_{v}-p_{u_{1}}&(p_{v}-p_{u_{1}})\cdot q_{u_{1}}\\p_{v}-p_{u_{2}}&(p_{v}-p_{u_{2}})\cdot q_{u_{2}}\\p_{v}-p_{u_{3}}&(p_{v}-p_{u_{3}})\cdot q_{u_{3}}\end{vmatrix}}=0.$

Обратите внимание, что $q_{u_{j}}$ можно записать как $\sum _{i}^{4}{c_{i}\lambda _{i,u_{j}}}$, для констант $c_{1},c_{2},c_{3},c_{4}$. Кроме того, мы можем переместить суммирование за пределы определителя, чтобы получить

$\sum _{i}^{4}c_{i}{\begin{vmatrix}p_{v}-p_{u_{1}}&(p_{v}-p_{u_{1}})\cdot \lambda _{i,u_{1}}\\p_{v}-p_{u_{2}}&(p_{v}-p_{u_{2}})\cdot \lambda _{i,u_{2}}\\p_{v}-p_{u_{3}}&(p_{v}-p_{u_{3}})\cdot \lambda _{i,u_{3}}\end{vmatrix}}=0.$

С $\lambda _{1},\lambda _{2},\lambda _{3}$ составляют основу тривиальных бесконечно малых движений, первые три члена суммирования равны $0$, оставив только

$c_{4}{\begin{vmatrix}p_{v}-p_{u_{1}}&(p_{v}-p_{u_{1}})\cdot \lambda _{4,u_{1}}\\p_{v}-p_{u_{2}}&(p_{v}-p_{u_{2}})\cdot \lambda _{4,u_{2}}\\p_{v}-p_{u_{3}}&(p_{v}-p_{u_{3}})\cdot \lambda _{4,u_{3}}\end{vmatrix}}=0.$

Решения этого уравнения образуют кривую $2$-размеры. Мы можем выбрать $p_{v}$ не вдоль этой кривой, так что $c_{4}=0$, что гарантирует наличие только одного решения этого уравнения. Следовательно, по предложению 9 ядро $R(p)$ имеет размерность $3$, так $p$ представляет собой общую бесконечно малую жесткую структуру $G$.

Объединение случаев 1 и 2 доказывает теорему по индукции.

См. также

• Граф Ламана