miniatyr|Rutenettlignende strukturer med utilstrekkelig tverravstivning kan være sårbare for kollaps. Fra Vargas-tragedien i Venezuela i 1999.

I matematikk knyttet til strukturell rigiditet er fagverksavstivning (engelsk: grid bracing, «rutenettavstivning», «gitteravstivning») et problem som går ut på å legge til skråstivere eller krysstivere i et rektangulært rutenett for å gjøre det til en rigid konstruksjon. Hvis en todimensjonal rutenettkonstruksjon består av stive staver som er koblet sammen i endene med fleksible ledd vil den fritt kunne endre form (deformeres) til posisjoner der stavene ikke lenger danner rette vinkler. Ved å bruke stivere langs diagonalene i de rektangulære eller kvadratiske rutene kan konstruksjonen gjøres rigid.

Problemet kan oversettes til grafteori ved å konstruere en graf der grafens hjørner representerer rader og kolonner i rutenettet, og hver kant (forbindelsen mellom hjørnene) representerer en avstivet celle i en gitt rad og kolonne. Rutenettet er stivt hvis og bare hvis den resulterende grafen er en sammenhengende graf. Hvert minimale system av avstivere som gjør rutenettet stivt tilsvarer et spenntre i en komplett todelt graf.

Den grafteoretiske løsningen på problemet med rutenettavstivning har blitt generalisert til «dobbel avstivning» (double bracing) som vil si at rutenettet skal forbli rigid selv om en tverravstivning svikter, og til «strekkavstivning» (tension bracing) som vil si at diagonalene i et rutenett er avstivet av tau eller strenger som kan krølle seg sammen til en kortere lengde, men ikke kan strekkes til å bli lengre. For dobbel avstivning tilsvarer de stive løsningene biforbundne grafer, og for strekkavstivning tilsvarer de sterkt forbundne grafer. I begge tilfeller tilsvarer minimalløsningene hamiltonsykluser.

Problemformulering miniatyr|Et uavstivet rutenett av regulære firkanter (venstre) bestående av fire kolonner og seks rader, og samme ikke-regulære rutenett forstyrret av bevegelse uten avstvining

Problemet tar utgangspunkt et rammeverk i form av et rektangulært rutenett (av rektangler) eller regulært rutenett (av kvadrater), med rader og kolonner. Rutenettet har kanter, som hver har enhetslengde og regnes som en stiv stang, med frihet til å bevege seg kontinuerlig innenfor det euklidske planet, men ikke i stand til å endre lengden. Disse stengene er festet til hverandre med fleksible ledd ved hjørner av rutenettet. En gyldig kontinuerlig bevegelse av dette rammeverket er en måte å kontinuerlig variere plasseringen av kantene og skjøtene i planet på en slik måte at de beholder samme lengde og samme feste, men uten at de må forbli i rette vinkler. I stedet kan hver celle i rutenettet deformeres for å danne et parallellogram eller en rombe, og hele rutenettet kan danne en uregelmessig struktur med en ulik form for hver av sine flater, som vist på figuren. miniatyr|Et kvadrat kan bøye seg for å danne en rombe (fleksibel graf), men en trekant danner en rigid struktur (rigid graf).

I motsetning til kvadrater kan ikke trekanter laget av stive stenger og fleksible ledd endre form: To trekanter med sider av samme lengde er kongruente (dette er side-side-side-postulatet). Et rektangel eller kvadrat kan avstives ved å legge til en stiv stang i en av diagonalene (slik at diagonalen deler firkanten inn i to trekanter som dermed ikke kan endre form), og deretter vil kvadratet måtte forbli kvadratisk gjennom enhver kontinuerlig bevegelse på grunn av det avstivede rammeverket. (Det samme rammeverket kan også plasseres i planet på en annen måte ved å brette de to trekantene oppå hverandre over deres delte diagonal, men denne brettengen kan ikke oppnås ved en kontinuerlig bevegelse i planet.) Hvis alle cellene i det gitte rutenettet er avstivet er det rigid og kan ikke endre form, altså vil dets eneste kontinuerlige bevegelse være å rotere eller translatere nettet som ett enkelt stivt legeme. Selv om metoden med å legge til avstivere i alle cellene vil gjøre rutenettet rigid resulterer det i mange flere avstivere enn nødvendig. Derimot ber rutenettavstivningproblemet om en beskrivelse av den minimale mengden av avstivere som oppnår samme effekt, altså det minste tilstrekkelige antallet (og variasjonene) for å gjøre hele rammeverket rigid.

Grafteoretisk løsning miniatyr|Et avstivet og rigid rutenett (venstre), og den tilhørende todelte grafen hvor hjørnene representerer radene (p-u) og kolonnene (A-D) i rutenettet. Grafen er et tre, så diagonalavstivningen bruker minste mulige antall avstivede firkanter.

I 1977 observerte Ethan Bolker og Henry Crapo at gitteravstivningproblemet kan oversettes til et problem i grafteori ved å betrakte en urettet todelt graf som har et hjørne for hver rad og kolonne i det gitte gitteret, og en kant for hvert diagonalavstivet rektangel eller kvadrat i gitteret. De beviste at det diagonalavstivede gitteret er stivt hvis og bare hvis denne todelte grafen er sammenhengende. Det følger at de minimale kombinasjonene av avstivninger i gitteret tilsvarer trærne som forbinder alle hjørner i grafen, og at de har nøyaktig avstivede firkanter. Enhver overavstivet, men stiv avstivning (med mer enn dette antallet avstivede celler) kan reduseres til minimal avstivning ved å finne et spenntre av grafen.

Det finnes generelle metoder for å konvertere et ikke-rigid rutenett til rigid. Anta at et avstivet rutenett bare er delvis avstivet, altså ikke rigid. Da er antallet frihetsgrader i dens familie av former (formene den kan bevege seg til) lik antallet sammenhengende komponenter i den todelte grafen minus én. Hvis et delvis avstivet rutenett skal gjøres rigid ved å avstive flere celler er minimumsantallet ekstra celler som må avstives lik dette antallet frihetsgrader. En løsning med dette antallet celler kan oppnås ved å legge til dette antallet kanter til den todelte grafen, og koble sammen par av dens sammenhengende komponenter slik at det etter addisjonen bare er én gjenværende komponent.

Variasjoner

Dobbel avstivning En annen versjon av problemet ber om en «dobbel avstivning», en mengde avstivere som er tilstrekkelig redundante til at strukturen forblir rigid selv om en av diagonalene fjernes. Denne versjonen av problemet tillater bruk av begge diagonalene i det enkelte kvadrat (såkalt kryssavstivning), men det er ikke et krav.

I den samme todelte grafvisningen som brukes til å løse avstivningproblemet tilsvarer en dobbel avstivning av et rutenett en urettet todelt multigraf som er sammenkoblet og broløs, hvilket betyr at hver kant tilhører minst én syklus. Minimum antall diagonaler som trengs for en dobbel avstivning er .

I det spesielle tilfellet med rutenett med likt antall rader og kolonner er de eneste dobbeltavstivningene med denne minimumsstørrelsen hamiltonsykluser. Hamiltonsykluser er enkle å finne i de komplette todelte grafene som representerer avstivningproblemet, men å finne dem i andre todelte grafer er NP-komplett. På grunn av dette er det NP-hardt å finne den minste dobbeltavstivede delmengden av en større avstivning. Det er imidlertid mulig å tilnærme denne minste dobbeltavstivede delmengden innenfor et konstant tilnærmingsforhold.

Spenningsavstivning En analog teori som bruker rettede grafer ble oppdaget av Jenny Baglivo og Jack Graver (1983) for strekkavstivning, der kvadrater avstives av tråder eller snorer (som ikke kan utvide seg utover sin opprinnelige lengde, men kan bøyes eller kollapse til en kortere lengde) i stedet for avstiving med stive stenger. For å gjøre et enkelt kvadrat stivt ved strekkavstivning er det nødvendig å avstive begge diagonalene i stedet for bare én diagonal (kryssavstivning).

Man kan representere en spenningsavstivning med en todelt graf som har en kant rettet fra et radknutepunkt til et kolonneknutepunkt hvis det delte kvadratet av den raden og kolonnen er avstivet av den positivt hellende diagonalen, og en kant fra et kolonneknutepunkt til et radknutepunkt hvis det delte kvadratet er avstivet av den negativt hellende diagonalen. Den avstivede strukturen er stiv hvis og bare hvis den resulterende grafen er sterkt forbundet. Når det gjelder dobbel avstivning er de minste spenningsavstivningene (tilsvarende de sterkt forbundet grafene med så få kanter som mulig) i rutenett med like mange rader og kolonner hamiltonsykluser. For rutenett der nøyaktig ett av de to avstivningsalternativene er tilgjengelige for hver celle kan en minste avstivning finnes i polynomisk tid.

Hvis en gitt mengde med avstivning er utilstrekkelig må ytterligere avstivning legges til, noe som i grafvisningen tilsvarer å legge til kanter som forbinder de sterkt forbundne komponentene i en graf. På denne måten kan problemet med å finne en minimal mengde med ytterligere avstivning som skal legges til sees på som et eksempel på sterk konnektivitetsforsterkning, og kan løses i lineær tid. Ifølge Robbins teorem er de ikke-rettede grafene som kan gjøres sterkt forbundne ved å rette kantene sine nettopp de broløse grafene. Ved å tolke dette teoremet på nytt i form av rutenettavstivning danner en avstivning med stive stenger en dobbel avstivning hvis og bare hvis hver av stengene kan erstattes av en enkelt tråd (muligens på den andre diagonalen i kvadratet) for å danne en stiv strekkavstivning.

Se også Kryssavstivning, forsterking av konstruksjoner ved hjelp av to diagonaler som krysser hverandre Fagverk, 2-dimensjonalt bæresystem av staver som kun tar strekk eller trykk Romfagverk, 3-dimensjonalt bæresystem av sammenkoblede fagverk Hanebjelke, horisontal bjelke som spenner mellom to sperrer i et sperrebind for avstivning av takkonstruksjoner Hylleknekt, innfestning med avstivning for å henge en hylle på en vegg Sammenføyningsteknikk, metoder for montering av konstruksjoner ved mekanisk sammenføyning med to eller flere elementer

Referanser

Kategori:Matematikk Kategori:Mekanikk Kategori:Grafteori Kategori:Sider uten gjennomgåtte oversettelser