PROFILPELAJAR.COM

Граф Ламана — граф з сімейства розріджених графів, що описує мінімальні жорсткі системи відрізків та шарнірів на площині. Формально — граф Ламана з $n$ вершинами — це такий граф $G$ , що, по-перше, для кожного $k$ будь-який підграф графа $n$ , який містить $k$ вершин, має не більше, ніж $2k-3$ ребер і, по-друге, сам граф $G$ має рівно $2n-3$ ребер.

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

Жорсткість

Не плутати з однойменною мірою зв'язності графа.

Графи Ламана виникають в теорії жорсткості наступним чином: якщо розмістити вершини графа Ламана на евклідовій площині так, щоб вони перебували у загальному положенні, і рухати вершини так, щоб довжини всіх ребер залишалися незмінними, то цей рух з необхідністю буде евклідовою ізометрією. Більш того, будь-який мінімальний граф, що має таку властивість, з необхідністю є графом Ламана. З інтуїтивної точки зору зрозуміло, що кожне ребро графа зменшує ступінь вільності відповідної йому шарнірно-стрижневої системи на одиницю. Тому 2n-3 ребер в графі Ламана зменшують 2n ступенів вільності системи з n вершин до трьох, що відповідає ізометричному перетворенню площини. Граф є жорстким в цьому сенсі тоді і лише тоді, коли він містить підграф Ламана, що містить всі вершини графа. Таким чином, графи Ламана є мінімальними жорсткими графами, і вони формують базис двомірних матроїдів жорсткості^[en].

Якщо задані n точок площини, існує 2n ступенів вільності в їх розташуванні (кожна точка має дві незалежні координати), але жорсткий граф має лише три ступені вільності (розміщення однієї точки та поворот навколо цієї точки). Інтуїтивно зрозуміло, що додавання ребра фіксованої довжини в граф скорочує ступінь вільності на одиницю, так що 2n-3 ребер графа Ламана зменшує 2n ступенів вільності початкового розташування до трьох ступенів вільності жорсткого графа. Проте не кожен граф з 2n-3 ребрами є жорстким. Умова у визначенні графа Ламана, що жоден підграф не містить забагато ребер гарантує, що кожне ребро реально вносить свій внесок у загальне зменшення ступеня вільності, а не є частиною підграфа, який вже є жорстким завдяки іншим своїм ребрам.

Планарність

Графи Ламана пов'язані також з поняттям псевдотріангуляції. Відомо, що кожна псевдотріангуляція є графом Ламана, і навпаки, кожен плаский граф Ламана може бути реалізований як псевдотріангуляція.^[2] Проте слід мати на увазі, що існують непланарні графи Ламана, наприклад, повний двочастковий граф $K_{3,3}$ .

Розрідженість

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

Побудова Хенненберга

Задовго до роботи Ламана Лебрехт Хеннеберг^[de] описав двомірні мінімальні жорсткі графи (тобто, графи Ламана) різними способами.^[5] Хенненберг показав, що мінімальні жорсткі графи з двома та більше вершинами — це в точності графи, які можна отримати, почавши з одиничного ребра, використовуючи операції двох видів:

Додається нова вершина разом з ребрами, що з'єднують її з двома вже наявними вершинами.
Ребро розбивається і додається нове ребро, що з'єднує знову з'явилася вершину з наявною.

Послідовність таких операцій, яка формує заданий граф, називається побудовою Хенненберга. Наприклад, повний двочастковий граф $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. — MR 0269535.
↑ 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, MR 2131802 .
↑ Streinu, Theran, 2008.
↑ I. Streinu, L. Theran. Sparse hypergraphs and pebble game algorithms // European Journal of Combinatorics^[en]. — 2009. — Т. 30, вип. 8. — С. 1944–1964. — arXiv:math/0703921. — DOI:10.1016/j.ejc.2008.12.018.
↑ L. Henneberg. Die graphische Statik der starren Systeme. — Leipzig, 1911.