Ламанов граф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Веретено Мозера, планарный Ламанов граф
Полный двудольный граф K3,3, непланарный Ламанов граф


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

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

Жёсткость[править | править исходный текст]

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

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

Планарность[править | править исходный текст]

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

Разреженность[править | править исходный текст]

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

Построение Хенненберга[править | править исходный текст]

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

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

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

Последовательность таких операций, которая формирует заданный граф, называется построением Хенненберга. Например, полный двудольный граф K3,3 может быть построен сначала применением трижды первой операции для построения треугольников, а затем применением двух операций типа два для разбиения двух сторон треугольника.

Примечания[править | править исходный текст]

  1. G. Laman On graphs and the rigidity of plane skeletal structures // J. Engineering Mathematics. — 1970. — Т. 4. — С. 331–340. — DOI:10.1007/BF01534980.
  2. Haas, Ruth; Orden, David; Rote, Günter & Santos, Francisco (2005), "«Planar minimally rigid graphs and pseudo-triangulations»", Computational Geometry Theory and Applications Т. 31 (1–2): 31–61, DOI 10.1016/j.comgeo.2004.07.003 .
  3. I. Streinu, L. Theran Sparse hypergraphs and pebble game algorithms // European Journal of Combinatorics. — 2009. — В. 8. — Т. 30. — С. 1944–1964. — DOI:10.1016/j.ejc.2008.12.018 — arΧiv:math/0703921.
  4. L. Henneberg Die graphische Statik der starren Systeme. — Leipzig, 1911.