Ламанов граф (Lgbgukf ijgs)

Лама́нов граф — граф из семейства разреженных графов, описывающий минимальные жёсткие системы^[англ.] отрезков и шарниров на плоскости. Формально — ламанов граф с $n$ вершинами — это такой граф $G$ , что, во-первых, для каждого $k$ любой подграф графа $n$ , содержащий $k$ вершин, имеет не более, чем $2k-3$ ребра и, во-вторых, сам граф $G$ имеет ровно $2n-3$ ребра.

Названы в честь профессора Амстердамского университета Герарда Ламана, который использовал их в 1970 году для описания плоских жёстких структур^[1].

Жёсткость

Ламановы графы возникают в теории жёсткости^[англ.] следующим образом: если разместить вершины Ламанова графа на евклидовой плоскости так, чтобы они находились в общем положении и двигать вершины так, чтобы длины всех рёбер оставались неизменными, то это движение с необходимостью будет евклидовой изометрией. Более того, любой минимальный граф, обладающий таким свойством, с необходимостью является Ламановым. С интуитивной точки зрения понятно, что каждое ребро графа уменьшает степень свободы соответствующей ему шарнирно-стержневой системы на единицу. Поэтому 2n −3 рёбер в Ламановом графе уменьшают 2n степеней свободы системы из n вершин до трёх, что соответствует изометрическому преобразованию плоскости. Граф является жёстким в этом смысле тогда и только тогда, когда он содержит Ламанов подграф, содержащий все вершины графа. Таким образом, Ламановы графы являются минимальными жёсткими графами и формируют базис двухмерных матроидов жёсткости^[англ.].

Если заданы n точек плоскости, существует 2n степени свободы в их расположении (каждая точка имеет две независимые координаты), но жёсткий граф имеет только три степени свободы (расположение одной точки и поворот вокруг этой точки). Интуитивно ясно, что добавление ребра фиксированной длины в граф сокращает степень свободы на единицу так, что 2n − 3 рёбер Ламанова графа уменьшает 2n степеней свободы начального расположения до трёх степеней свободы жёсткого графа. Однако не всякий граф с 2n − 3 рёбрами является жёстким. Условие в определении Ламанова графа, что никакой подграф не содержит слишком много рёбер, гарантирует, что каждое ребро реально вносит свой вклад в общее уменьшение степени свободы, а не является частью подграфа, который уже является жёстким благодаря другим своим рёбрам.

Планарность

Ламановы графы связаны также с понятием псевдотриангуляции^[англ.]. Известно, что каждая псевдотриангуляция является Ламановым графом и наоборот, каждый плоский Ламанов граф может быть реализован как псевдотриангуляция.^[2] Однако следует иметь в виду, что имеются непланарные Ламановы графы, например, полный двудольный граф $K_{3,3}$ .

Разреженность

Штрейну и Теран^[3] определяют граф как $(k,l)$ -разреженный, если любой непустой подграф с $n$ вершинами имеет максимум $kn-l$ рёбер, и $(k,l)$ -плотный, если он $(k,l)$ -разреженный и имеет в точности $kn-l$ рёбер. Таким образом, в этой нотации, Ламановы графы — это в точности (2,3)-плотные графы, и подграфы Ламановых графов — это в точности (2,3)-разреженные графы. Ту же самую нотацию можно использовать для описания других важных семейств разреженных графов, включая деревья, псевдолеса и графы с ограниченной древесностью.^[3]

Построение Хенненберга

Задолго до работы Ламана, Лебрехт Хеннеберг (Lebrecht Henneberg) описал двухмерные минимальные жёсткие графы (то есть, графы Ламана) различными способами^[4]. Хенненберг показал, что минимальные жёсткие графы с двумя и более вершинами — это в точности графы, которые можно получить, начав с единичного ребра, используя операции двух видов:

Добавляется новая вершина вместе с рёбрами, соединяющими её с двумя уже существующими вершинами.
Ребро разбивается и добавляется новое ребро, соединяющее вновь появившуюся вершину с существующей.

Последовательность таких операций, которая формирует заданный граф, называется построением Хенненберга. Построение Хенненберга веретена Мозера показано на картинке. Другой пример: полный двудольный граф $K_{3,3}$ может быть построен сначала применением первой операции для построения треугольника, и затем применением трёх операций второго типа для разбиения каждой стороны треугольника.

Литература

G. Laman. On graphs and the rigidity of plane skeletal structures // J. Engineering Mathematics. — 1970. — Т. 4. — С. 331—340. — doi:10.1007/BF01534980.
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley. Planar minimally rigid graphs and pseudo-triangulations // Computational Geometry Theory and Applications. — 2005. — Т. 31, вып. 1—2. — С. 31—61. — doi:10.1016/j.comgeo.2004.07.003.
I. Streinu, L. Theran. Sparse hypergraphs and pebble game algorithms // European Journal of Combinatorics. — 2009. — Т. 30, вып. 8. — С. 1944—1964. — doi:10.1016/j.ejc.2008.12.018. — arXiv:math/0703921.
L. Henneberg. Die graphische Statik der starren Systeme. — Leipzig: B. G. Teubner, 1911. — 755 с.

[_7ad16dad57fcda59-1] Laman, 1970.

[_a58e7f95dd5153e9-2] Haas, 2005.

[_21fd48420eb0b1c8-3] ¹ ² Streinu, Theran, 2009.

[_9ad828fe4537ea9f-4] Henneberg, 1911.

[1]

[2]

[3]

[4]