Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Ламанов граф



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

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

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

Ламанова графи пов'язані також з поняттям псевдотріангуляціі : відомо, що кожна псевдотріангуляція є Ламанова графом, і навпаки, - кожен плоский Ламанов граф може бути реалізований як псевдотріангуляція. [2] Однак слід мати на увазі, що є непланарние Ламанова графи, наприклад, повний двочастковий граф K 3,3.


Примітки

  1. Laman, G. (1970), " On graphs and the rigidity of plane skeletal structures - dx.doi.org/10.1007/BF01534980 ", J. Engineering Mathematics Т. 4: 331-340, MR 0269535 - www.ams.org/mathscinet-getitem?mr=0269535 , DOI 10.1007/BF01534980 .
  2. Haas, Ruth; Orden, David; Rote, Gnter; 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 - dx.doi.org/10.1016/j.comgeo.2004.07.003. MR 2131802 - www.ams.org/mathscinet-getitem?mr=2131802.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Граф
Граф Петерсена
Граф, Девід
Граф, Штеффі
Граф Монтенегро
Граф алгоритму
Граф Ессекс
Граф Лестер
Граф Дербі
© Усі права захищені
написати до нас
Рейтинг@Mail.ru