Contele Lamanov

Un graf Laman este un grafic din familia grafurilor rare care descrie sisteme rigide minime de segmente și balamale pe un plan. Formal, un graf Laman cu vârfuri este un astfel de graf încât, în primul rând, pentru fiecare subgraf al graficului care conține vârfuri are cel mult muchii și, în al doilea rând, graficul în sine are exact muchii. $n$ $G$ $k$ $n$ $k$ $2k-3$ $G$ $2n-3$

Ele poartă numele lui Gerard Laman , profesor la Universitatea din Amsterdam , care le-a folosit în 1970 pentru a descrie structuri rigide plate [1] .

Rigiditate

Graficele Laman apar în teoria rigidității după cum urmează: dacă plasați vârfurile unui grafic Laman pe planul euclidian astfel încât acestea să fie în poziție generală și mutați vârfurile astfel încât lungimile tuturor muchiilor să rămână neschimbate, atunci aceasta mișcarea va fi neapărat o izometrie euclidiană. Mai mult, orice graf minim cu această proprietate este în mod necesar un graf Laman. Din punct de vedere intuitiv, este clar că fiecare margine a graficului reduce gradul de libertate al sistemului de balamale-tijă corespunzător acestuia. Prin urmare, 2 n − 3 muchii dintr-un grafic Laman reduc cele 2 n grade de libertate ale unui sistem de n vârfuri la trei, ceea ce corespunde unei transformări izometrice a planului. Un graf este rigid în acest sens dacă și numai dacă conține un subgraf Laman care conține toate vârfurile grafului. Astfel, graficele Laman sunt grafice minime rigide și formează baza matroidelor de rigiditate bidimensionale .

Având în vedere n puncte în plan, există 2n grade de libertate în aranjarea lor (fiecare punct are două coordonate independente), dar un grafic rigid are doar trei grade de libertate (localizând un punct și rotindu-se în jurul acelui punct). Este intuitiv clar că adăugarea unei muchii cu lungime fixă la un grafic reduce gradul de libertate cu unul, astfel încât 2n - 3 muchii ale graficului Laman reduc cele 2n grade de libertate ale aranjamentului inițial la trei grade de libertate ale unui rigid. grafic. Totuși, nu orice grafic cu 2n - 3 muchii este rigid. Condiția din definiția unui graf Laman că niciun subgraf nu conține prea multe muchii asigură că fiecare muchie contribuie de fapt la scăderea generală a gradului de libertate și nu face parte dintr-un subgraf care este deja rigid datorită celorlalte muchii ale sale.

Planaritate

Graficele Laman sunt, de asemenea, legate de conceptul de pseudotriangulație . Se știe că fiecare pseudo-triangulație este un graf Laman și invers, fiecare graf Laman plan poate fi realizat ca o pseudo-triangulație. [2] Cu toate acestea, trebuie reținut că există grafuri Laman neplanare, de exemplu, un graf bipartit complet . $K_{{3,3}}$

Sparsitate

Shteinu și Teran [3] definesc un graf ca -sparse dacă orice subgraf nevid cu vârfuri are maximum de muchii, și -dens dacă este -sparse și are exact muchii. Astfel, în această notație, graficele Laman sunt grafice exact (2,3)-dense, iar subgrafele graficelor Laman sunt grafice exact (2,3)-sparse. Aceeași notație poate fi folosită pentru a descrie alte familii importante de grafice rare , inclusiv copaci , pseudopăduri și grafice cu arbori mărginiți . [3] $(k,l)$ $n$ $kn-l$ $(k,l)$ $(k,l)$ $kn-l$

Construcția lui Hennenberg

Cu mult înainte de lucrarea lui Laman, Lebrecht Henneberg a descris graficele rigide minime bidimensionale (adică graficele Laman) în diferite moduri [4] . Hennenberg a arătat că graficele minime rigide cu două sau mai multe vârfuri sunt exact graficele care pot fi obținute pornind de la o singură muchie folosind două tipuri de operații:

Se adaugă un nou vârf împreună cu muchiile care îl conectează la două vârfuri existente.
Muchia este împărțită și se adaugă o nouă muchie, conectând vârful nou apărut cu cel existent.

O secvență de astfel de operații care formează un grafic dat se numește construcție Hennenberg . De exemplu, un graf bipartit complet poate fi construit aplicând mai întâi prima operație de trei ori pentru a construi triunghiuri și apoi aplicând două operații de tipul doi pentru a subdiviza cele două laturi ale triunghiului. $K_{{3,3}}$

Literatură

G. Laman. Despre grafice și rigiditatea structurilor scheletice plane // J. Engineering Mathematics. - 1970. - T. 4 . - S. 331-340 . - doi : 10.1007/BF01534980 .
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley. Grafice planare minim rigide și pseudo-triangulații // Teoria și aplicațiile geometriei computaționale. - 2005. - T. 31 , nr. 1-2 . - S. 31-61 . - doi : 10.1016/j.comgeo.2004.07.003 .
I. Streinu, L. Theran. Hipergrafe rare și algoritmi de joc cu pietricele // European Journal of Combinatorics . - 2009. - T. 30 , nr. 8 . - S. 1944-1964 . - doi : 10.1016/j.ejc.2008.12.018 . — arXiv : math/0703921 .
L. Henneberg. Die graphische Statik der starren Systeme . - Leipzig: BG Teubner, 1911. - 755 p.