A Tutt-beágyazás ( baricentrikus beágyazás ) egy egyszerű, 3 csúcsú síkgráfban egy olyan beágyazás, amely nem metszik a vonalszakaszokat, azzal a további tulajdonsággal, hogy a külső lap határa egy konvex sokszög , és minden belső csúcs a geometriai középpontja. szomszédai . Ha a külső sokszög rögzített, akkor ez a feltétel a belső csúcsokon egyedileg határozza meg azok helyzetét egy lineáris egyenletrendszer megoldásaként . Az egyenletek megoldása síkbeli beágyazást ad . Tutt „gumitömítés” tétele kimondja, hogy egyetlen megoldásban soha nincsenek élmetszéspontok, és még szigorúbban, a kapott síkbeli beágyazás bármely lapja konvex [1] . A beágyazást "gumi" beágyazásnak nevezzük, mivel az ilyen beágyazás megtalálható a gráf éleit reprezentáló rugók vagy gumiszalagok rendszerének egyensúlyi helyzeteként.
Legyen G kockagráf. Rögzítsük (a négyszöglapok egyikét külső lapnak választva) a külső lap négy csúcsát az egységnégyzet sarkaiban, amelyek x és y koordinátái nullák és egyesek kombinációi. A maradék négy csúcs négy pontban található, amelyek x és y koordinátái 1/3 és 2/3 kombinációi, amint az az ábrán látható. Az eredmény Tutt beágyazása. Ennek a beágyazásnak minden belső v csúcsához a szomszédos három csúcsnak három koordinátaértéke van ( x és y ), az egyik egyenlő a v koordinátával , a másik kisebb, a másik 1/3-al nagyobb. Átlagosan megkapjuk magának a v pontnak a koordinátájának értékét .
Az a feltétel, hogy egy v csúcsnak a szomszédjai koordinátáinak átlaga van, két lineáris egyenlettel fejezhető ki , az egyik v x koordinátájára , a másik az y koordinátára . Egy n csúcsú gráfhoz, amelynek h a külső lapjának csúcsaiban van rögzítve, minden belső csúcshoz két egyenlet és két ismeretlen (koordináta) tartozik. Így kapunk egy lineáris egyenletrendszert 2( n − h ) egyenletekkel 2( n − h ) ismeretlenben, melynek megoldása a Tutt-beágyazás. Amint Tatt [2] megmutatta , a 3 csúcshoz kapcsolódó síkgráfok esetében ez a rendszer nem degenerált. Ezért a rendszernek egyedi megoldása lesz, és (fix külső éllel) a gráf lesz Tutt egyetlen beágyazása. Ezt a beágyazást polinomidőben találhatjuk meg egy egyenletrendszer megoldásával, például változók szekvenciális eliminálásával [3] .
Steinitz tétele szerint a 3 összekapcsolt síkgráfok, amelyekre Tutt "gumifektetési" tétele vonatkozik, megegyeznek a poliéder gráfokkal , a konvex poliéder csúcsaiból és éleiből alkotott gráfokkal . A Maxwell-Cremont módszer szerint egy síkgráf kétdimenziós beágyazása akkor és csak akkor képez egy háromdimenziós konvex poliéder vetületét, ha a beágyazásnak van egyensúlyi feszültsége , az erőeloszlás minden élre (mindkét végén). az élekkel párhuzamosan ellentétes irányú élek), így az egyes csúcsokban kiegyenlített erők . A Tutt-beágyazásnál az egyes élek erőeloszlása arányos az él hosszával (hasonlóan a gumiszalaghoz), kiegyenlítve az erőket minden belső pontban, de nem a külső sokszög csúcsaiban. Ha a külső sokszög egy háromszög, akkor a három külső élhez taszítóerőket rendelhet, hogy kiegyenlítse a külső háromszög csúcsaiban lévő erőket. Így a Tutt-féle beágyazás felhasználható bármely konvex poliéder Schlegel-diagramjainak megtalálására . Bármely 3-kapcsolatú G síkgráf esetén vagy magának a G gráfnak vagy annak duálisának van háromszöge, így a G gráf vagy duális poliéderes ábrázolását kapjuk . Abban az esetben, ha a duális gráfnak háromszöglapja van, a poláris konjugáció magának a G gráfnak poliéderes ábrázolását adja [3] .
Gortler, Gottsman és Thurston [4] Tutt "gumitömítés" tételéhez hasonló eredményeket mutatott be a gráfok tóruszba történő beágyazására [5] .
Chilacamarri, Dean és Litman [6] négydimenziós politópok gráfjainak háromdimenziós beágyazását tanulmányozták , amelyeket ugyanazzal a módszerrel alakítottak ki, mint a Tutt-féle beágyazási módszernél – a politóp egyik külső oldalát választottuk a háromdimenziós politóp külső felületének. dimenziós beágyazás és a csúcsok helyzetének rögzítése a háromdimenziós térben. A poliéder többi csúcsa mozgatható, élei rugóval (vagy gumizsinórral) helyettesíthetők. Most keressük meg a minimális energiájú rugórendszer konfigurációját. Amint azt kimutatták, az így kapott egyenletrendszer ismét nem lesz degenerált, de továbbra sem világos, hogy ez a módszer milyen feltételek mellett talál olyan beágyazást, amelyben a poliéder minden lapja konvex [7] .
Azt a tényt, hogy bármely egyszerű síkgráf megrajzolható egyenes élekkel, Farey-tételnek nevezzük [8] . Tutt „gumitömítés” tétele ezt bizonyítja 3 összekapcsolt síkgráfokra, de Farey tétele igaz minden síkgráfra, függetlenül a konnektivitástól. A Tutt-tétel alkalmazása olyan gráfokra, amelyek nem 3-kapcsolatosak, degenerációhoz vezethet, amelyben egy adott gráf részgráfjai ponttá vagy szegmenssé egyesülnek. Azonban bármilyen síkgráf megrajzolható Tutt-féle beágyazással, ha extra éleket adunk hozzá, hogy 3-kapcsolt legyen, majd megrajzoljuk a 3-as gráfot, és eltávolítjuk belőle a felesleges éleket.
Egy gráf akkor és csak akkor csúcs - k -összefüggõ (de nem feltétlenül síkbeli), ha van egy olyan ( k -1) dimenziós térbe való beágyazása, amelyben bármely k csúcshalmaz a szimplex csúcsaiban található , és a v konvex hajótest szomszédjainak fennmaradó csúcsa teljes dimenzióval rendelkezik, és v ezen a héjon belül helyezkedik el. Ha létezik ilyen beágyazás, akkor azt k csúcs helyzetének rögzítésével és az egyenletrendszer megoldásával találhatjuk meg. A megoldás minden csúcsot olyan helyre helyez, amely a szomszédok átlagos pozíciója, akárcsak Tutt síkbeli beágyazása [9] .
A végeselemes hálózásban a Laplace - simítás egy elterjedt módszer a kapott háló utófeldolgozására a minőség javítása érdekében [10] , és különösen népszerű a négyszöghálóknál, amelyekhez más módszerek, például a Lloyd-algoritmus a háromszög simítására. hálók, kevésbé alkalmazhatók. Ennél a módszernél minden csúcs a szomszédok pozícióinak átlagos pozíciója irányába van, de ezt a mozgást kis számú iterációban hajtjuk végre, hogy elkerüljük az elemméretek nagy torzulását, ill. konvex hálórégió) összegabalyodó nem síkbeli hálók szerzése.
A gráfhalmozási erő módszerek továbbra is népszerűek a gráfvizualizációban, de ezek a rendszerek jellemzően összetettebb erőrendszereket használnak, amelyek a gráf éleiből származó vonzó erőket (mint a Tutt-féle beágyazásban) a két tetszőleges csúcspár közötti taszító erőkkel kombinálják. Ezek a járulékos erők sok lokális stabil konfigurációt adhatnak a rendszernek, nem pedig egy globálisat, mint a Tutta beágyazásában [11] .