Ламанов граф

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

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

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

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

Примечания

1. ↑ Laman, G. (1970), "«On graphs and the rigidity of plane skeletal structures»", J. Engineering Mathematics Т. 4: 331–340, MR0269535, DOI 10.1007/BF01534980 .
2. ↑ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (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. MR2131802.