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

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

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

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

Примечания