Kreivi Lamanov

Laman-graafi on harvalukuisten graafien perheestä kuuluva graafi , joka kuvaa segmenttien ja saranoiden minimaalisia jäykkiä järjestelmiä Muodollisesti Laman-graafi, jossa on pisteet, on sellainen graafi , että ensinnäkin jokaiselle graafin jokaiselle alagraafille, joka sisältää pisteet, on korkeintaan reunat ja toiseksi itse graafilla on täsmälleen reunat. $n$ $G$ $k$ $n$ $k$ $2k-3$ $G$ $2n-3$

Ne on nimetty Amsterdamin yliopiston professorin Gerard Lamanin mukaan , joka käytti niitä vuonna 1970 kuvaamaan litteitä jäykkiä rakenteita [1] .

Jäykkyys

Laman-graafit syntyvät jäykkyysteoriassa seuraavasti: jos sijoitat Laman-graafin kärjet euklidiselle tasolle siten, että ne ovat yleisessä asemassa ja siirrät pisteitä siten, että kaikkien reunojen pituudet pysyvät muuttumattomina, niin tämä liike on välttämättä euklidinen isometria. Lisäksi mikä tahansa minimaalinen graafi, jolla on tämä ominaisuus, on välttämättä Laman-graafi. Intuitiivisesti katsottuna on selvää, että graafin jokainen reuna vähentää sitä vastaavan saranatankojärjestelmän vapausastetta yhdellä. Siksi 2 n − 3 reunaa Laman-graafissa vähentävät n pisteen järjestelmän 2 n vapausastetta kolmeen, mikä vastaa tason isometristä muunnosta. Graafi on tässä mielessä jäykkä silloin ja vain, jos se sisältää Laman-aligraafin, joka sisältää kaikki graafin kärjet. Siten Laman-graafit ovat minimaalisia jäykkiä graafeja ja muodostavat perustan kaksiulotteisille jäykkyysmatroideille .

Kun tasossa on annettu n pistettä, niiden järjestelyssä on 2n vapausastetta (jokaisella pisteellä on kaksi itsenäistä koordinaattia), mutta jäykällä graafilla on vain kolme vapausastetta (yhden pisteen paikantaminen ja sen ympäri kiertäminen). On intuitiivisesti selvää, että kiinteän pituisen reunan lisääminen graafiin vähentää vapausastetta yhdellä, joten Laman-graafin 2n − 3 reunaa pienentää alkuperäisen järjestelyn 2n vapausastetta kolmeen jäykän vapausasteeseen. kaavio. Jokainen graafi, jossa on 2n − 3 reunaa, ei kuitenkaan ole jäykkä. Laman-graafin määritelmän ehto, että mikään aligraafi ei sisällä liian monta reunaa, varmistaa, että jokainen reuna todella myötävaikuttaa vapausasteen yleiseen laskuun, eikä ole osa aligraafia, joka on jo jäykkä muiden reunojensa vuoksi.

Tasoisuus

Laman-graafit liittyvät myös pseudotriangulaation käsitteeseen . Tiedetään, että jokainen pseudokolmio on Laman-graafi ja päinvastoin, jokainen tasomainen Laman-graafi voidaan toteuttaa pseudo-triangulaationa. [2] On kuitenkin pidettävä mielessä, että on olemassa ei-tasoisia Laman-graafia, esimerkiksi täydellinen kaksiosainen graafi . $K_{{3,3}}$

Harvaus

Shteinu ja Teran [3] määrittelevät graafin -harvaksi, jos jollakin ei-tyhjällä aligraafilla, jolla on kärkipisteet, on enintään reunat, ja -tiheäksi, jos se on -harva ja siinä on tarkat reunat. Siten tässä merkinnässä Laman-graafit ovat täsmälleen (2,3)-tiheitä graafeja ja Laman-graafien aligraafit ovat täsmälleen (2,3)-harvoja graafeja. Samaa merkintää voidaan käyttää kuvaamaan muita tärkeitä harvalukuisten graafien perheitä , mukaan lukien puut , pseudometsät ja rajatut puukaaviot . [3] ${\näyttötyyli (k,l)}$ $n$ $kn-l$ ${\näyttötyyli (k,l)}$ ${\näyttötyyli (k,l)}$ $kn-l$

Hennenbergin rakennus

Kauan ennen Lamanin työtä Lebrecht Henneberg kuvasi kaksiulotteisia minimaalisia jäykkiä graafia (eli Laman-graafia) eri tavoin [4] . Hennenberg osoitti, että minimaaliset jäykät graafit, joissa on kaksi tai useampia huippuja, ovat täsmälleen niitä graafisia, jotka voidaan saada aloittamalla yhdestä reunasta kahdentyyppisillä operaatioilla:

Uusi kärkipiste lisätään yhdessä reunojen kanssa, jotka yhdistävät sen kahteen olemassa olevaan kärkeen.
Reuna jaetaan ja lisätään uusi reuna, joka yhdistää juuri ilmestyneen kärjen olemassa olevaan.

Tällaisten operaatioiden sarjaa, joka muodostaa tietyn graafin, kutsutaan Hennenberg-konstruktioksi . Esimerkiksi täydellinen kaksiosainen graafi voidaan rakentaa käyttämällä ensin ensimmäistä operaatiota kolme kertaa kolmioiden muodostamiseksi ja sitten käyttämällä kahta tyypin kaksi operaatiota kolmion kahden sivun jakamiseksi. $K_{{3,3}}$

Kirjallisuus

G. Laman. Graafista ja tasorakenteiden jäykkyydestä // 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. Tasomaiset minimaalisen jäykät kuvaajat ja pseudotriangulaatiot // Laskennallisen geometrian teoria ja sovellukset. - 2005. - T. 31 , no. 1-2 . - S. 31-61 . - doi : 10.1016/j.comgeo.2004.07.003 .
I. Streinu, L. Theran. Harvat hypergraafit ja kivipelialgoritmit // European Journal of Combinatorics . - 2009. - T. 30 , no. 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 s.