Greve Lamanov

En Laman-graf  är en graf från familjen glesa grafer som beskriver minimala stela system av segment och gångjärn på ett plan. Formellt är en Laman-graf med hörn en sådan graf att för det första har varje undergraf av grafen som innehåller hörn högst kanter och för det andra har själva grafen exakta kanter.

De är uppkallade efter Gerard Laman , professor vid universitetet i Amsterdam , som använde dem 1970 för att beskriva platta stela strukturer [1] .

Stelhet

Lamangrafer uppstår i teorin om stelhet enligt följande: om du placerar hörnen på en Laman-graf på det euklidiska planet så att de är i allmän position och flyttar hörnen så att längden på alla kanter förblir oförändrade, då rörelse kommer nödvändigtvis att vara en euklidisk isometri. Dessutom är varje minimal graf med den här egenskapen nödvändigtvis en Laman-graf. Ur en intuitiv synvinkel är det tydligt att varje kant av grafen minskar frihetsgraden för gångjärnsstångssystemet som motsvarar den med en. Därför reducerar 2 n  − 3 kanter i en Laman-graf de 2 n frihetsgraderna för ett system med n hörn till tre, vilket motsvarar en isometrisk transformation av planet. En graf är stel i denna mening om och bara om den innehåller en Laman-subgraf som innehåller alla hörn i grafen. Således är Laman-grafer minimala stela grafer och utgör grunden för tvådimensionella styvhetsmatroider .

Givet n punkter i planet finns det 2n frihetsgrader i deras arrangemang (varje punkt har två oberoende koordinater), men en stel graf har bara tre frihetsgrader (placerar en punkt och roterar runt den punkten). Det är intuitivt tydligt att lägga till en kant med fast längd till en graf minskar frihetsgraden med en, så att 2n  − 3 kanter på Lamangrafen reducerar de 2n frihetsgraderna för det initiala arrangemanget till tre frihetsgrader för en stel Graf. Men inte varje graf med 2n  − 3 kanter är stel. Villkoret i definitionen av en Laman-graf att ingen subgraf innehåller för många kanter säkerställer att varje kant faktiskt bidrar till den totala minskningen av frihetsgraden och inte är en del av en subgraf som redan är stel på grund av sina andra kanter.

Planaritet

Lamangrafer är också relaterade till begreppet pseudotriangulering . Det är känt att varje pseudo-triangulering är en Laman-graf och vice versa, varje plan Laman-graf kan realiseras som en pseudo-triangulering. [2] Man bör dock komma ihåg att det finns icke-planära Laman-grafer, till exempel en komplett tvådelad graf .

Sparsitet

Shteinu och Teran [3] definierar en graf som -gles om någon icke-tom subgraf med hörn har maximalt med kanter, och -tät om den är -gles och har exakt kanter. I denna notation är alltså Laman-grafer exakt (2,3)-täta grafer, och undergrafer av Laman-grafer är exakt (2,3)-glesa grafer. Samma notation kan användas för att beskriva andra viktiga familjer av glesa grafer , inklusive träd , pseudoskogar och grafer med avgränsade träd . [3]

Hennenbergs konstruktion

Långt före Lamans arbete beskrev Lebrecht Henneberg tvådimensionella minimala stela grafer (det vill säga Lamangrafer) på olika sätt [4] . Hennenberg visade att minimala stela grafer med två eller flera hörn är exakt de grafer som kan erhållas genom att börja vid en enda kant med två typer av operationer:

  1. En ny vertex läggs till tillsammans med kanter som förbinder den med två befintliga hörn.
  2. Kanten delas och en ny kant läggs till, vilket förbinder den nyligen visade vertexen med den befintliga.

En sekvens av sådana operationer som bildar en given graf kallas en Hennenbergkonstruktion . Till exempel kan en komplett tvådelad graf byggas genom att först tillämpa den första operationen tre gånger för att konstruera trianglar, och sedan tillämpa två operationer av typ två för att dela upp triangelns två sidor.

Anteckningar

  1. ↑ Laman, 1970 .
  2. ↑ Haas, 2005 .
  3. ↑ 12 Streinu, Theran, 2009 .
  4. ↑ Henneberg, 1911 .

Litteratur