Ламанов граф

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

Веретено Мозера, планарный Ламанов граф

Полный двудольный граф K_3,3, непланарный Ламанов граф

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

Жёсткость

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

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

Планарность

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

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

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

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

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

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

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

Последовательность таких операций, которая формирует заданный граф, называется построением Хенненберга. Построение Хенненберга веретена Мозера показано на картинке. Другой пример: полный двудольный граф $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 с.