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

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

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

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

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

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

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

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

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

Примечания

Литература

Категория:Геометрические графы Категория:Графы, имеющие собственные названия Категория:Семейства графов