Hrabě Lamanov

Lamanův graf  je graf z rodiny řídkých grafů , který popisuje minimální rigidní systémy a pantů v rovině. Formálně je Lamanův graf s vrcholy takový graf , který za prvé pro každý podgraf grafu obsahující vrcholy má nejvíce hran a za druhé má graf samotný přesně hrany.

Jsou pojmenovány po Gerardu Lamanovi , profesorovi na univerzitě v Amsterdamu , který je použil v roce 1970 k popisu plochých tuhých struktur [1] .

Tuhost

Lamanovy grafy vznikají v teorii tuhosti následovně: pokud umístíte vrcholy Lamanova grafu do euklidovské roviny tak, aby byly v obecné poloze , a posunete vrcholy tak, aby délky všech hran zůstaly nezměněny, pak toto pohyb bude nutně euklidovská izometrie. Navíc každý minimální graf s touto vlastností je nutně Lamanův graf. Z intuitivního hlediska je zřejmé, že každá hrana grafu snižuje stupeň volnosti jemu odpovídající soustavy závěs-tyč o jednu. Proto 2 n  − 3 hran v Lamanově grafu redukují 2 n stupňů volnosti systému n vrcholů na tři, což odpovídá izometrické transformaci roviny. Graf je v tomto smyslu rigidní právě tehdy, když obsahuje Lamanův podgraf obsahující všechny vrcholy grafu. Lamanovy grafy jsou tedy minimální rigidní grafy a tvoří základ dvourozměrných matroidů rigidity .

Je-li dáno n bodů v rovině, je v jejich uspořádání 2n stupňů volnosti (každý bod má dvě nezávislé souřadnice), ale rigidní graf má pouze tři stupně volnosti (umístění jednoho bodu a rotace kolem tohoto bodu). Je intuitivně jasné, že přidání hrany pevné délky do grafu snižuje stupeň volnosti o jednu, takže 2n  − 3 okraje Lamanova grafu snižují 2n stupňů volnosti původního uspořádání na tři stupně volnosti tuhého grafu. graf. Ne každý graf s 2n  − 3 hranami je však rigidní. Podmínka v definici Lamanova grafu, že žádný podgraf neobsahuje příliš mnoho hran, zajišťuje, že každá hrana skutečně přispívá k celkovému snížení stupně volnosti a není součástí podgrafu, který je již tak rigidní díky svým ostatním hranám.

Rovinnost

S konceptem pseudotriangulace souvisí i Lamanovy grafy . Je známo, že každá pseudotriangulace je Lamanův graf a naopak každý rovinný Lamanův graf může být realizován jako pseudotriangulace. [2] Je však třeba mít na paměti, že existují nerovinné Lamanovy grafy, například úplný bipartitní graf .

Řídkost

Shteinu a Teran [3] definují graf jako -řídký, pokud má jakýkoli neprázdný podgraf s vrcholy maximum hran, a jako -hustý, pokud je -řídký a má přesně hrany. V tomto zápisu jsou tedy Lamanovy grafy přesně (2,3)-husté grafy a podgrafy Lamanových grafů jsou přesně (2,3)-řídké grafy. Stejný zápis lze použít k popisu dalších důležitých rodin řídkých grafů , včetně stromů , pseudolesů a grafů s ohraničeným stromem . [3]

Hennenbergova stavba

Dlouho před Lamanovou prací popsal Lebrecht Henneberg různými způsoby dvourozměrné minimální rigidní grafy (tedy Lamanovy grafy) [4] . Hennenberg ukázal, že minimální rigidní grafy se dvěma nebo více vrcholy jsou přesně ty grafy, které lze získat zahájením na jedné hraně pomocí dvou druhů operací:

  1. Je přidán nový vrchol spolu s hranami, které jej spojují se dvěma existujícími vrcholy.
  2. Hrana je rozdělena a je přidána nová hrana, která spojuje nově objevený vrchol se stávajícím.

Posloupnost takových operací, které tvoří daný graf, se nazývá Hennenbergova konstrukce . Například úplný bipartitní graf lze sestavit tak, že nejprve třikrát použijete první operaci ke konstrukci trojúhelníků a poté použijete dvě operace typu dva k rozdělení dvou stran trojúhelníku.

Poznámky

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

Literatura