Stężenie siatki

W matematyce sztywności strukturalnej usztywnienie siatki jest problemem polegającym na dodaniu stężeń krzyżowych do kwadratowej siatki , aby uzyskać sztywną konstrukcję. Można go optymalnie rozwiązać, tłumacząc go na problem w teorii grafów dotyczący łączności grafów dwudzielnych .

Oświadczenie o problemie

Nieusztywniona siatka kwadratowa z sześcioma rzędami i czterema kolumnami oraz siatka niekwadratowa uzyskana z jej ciągłego ruchu

$w$ postaci kwadratowej siatki $.$ wierszami i kolumnami kwadratów Siatka ma krawędzie, $r + 1 ) do {\ Displaystyle r (c + 1) + (r +$ których każda ma długość jednostkową i jest uważana za sztywny pręt, swobodnie poruszać się w płaszczyźnie euklidesowej ale nie można zmienić jego długości. $ze$ sobą za siatki Prawidłowy ciągły ruch tej ramy to sposób na ciągłe zmienianie położenia jej krawędzi i połączeń w płaszczyźnie w taki sposób, aby zachować te same długości i te same mocowania, ale bez konieczności tworzenia z nich kwadratów. Zamiast tego każdy kwadrat siatki można zdeformować, tworząc romb , a cała siatka może tworzyć nieregularną strukturę o innym kształcie dla każdej z jej ścian, jak pokazano na rysunku.

Kwadrat może się zginać, tworząc romb , ale trójkąt tworzy sztywną strukturę

W przeciwieństwie do kwadratów, trójkąty złożone ze sztywnych prętów i elastycznych połączeń nie mogą zmieniać swoich kształtów: dowolne dwa trójkąty o bokach tej samej długości muszą być przystające (jest to postulat SSS ) . Jeśli kwadrat jest wzmocniony krzyżowo przez dodanie jednej z jego przekątnych jako innego sztywnego pręta, przekątna dzieli go na dwa trójkąty, które podobnie nie mogą zmienić kształtu, więc kwadrat musi pozostać kwadratowy podczas każdego ciągłego ruchu ramy wzmocnionej poprzecznie. (Ten sam szkielet można również umieścić w płaszczyźnie w inny sposób, składając dwa trójkąty na siebie na wspólnej przekątnej, ale takiego złożonego położenia nie można uzyskać ciągłym ruchem.) Podobnie, jeśli wszystkie kwadraty danego siatka była krzyżowana w ten sam sposób, siatka nie mogła zmienić kształtu; jego jedynymi ciągłymi ruchami byłoby obracanie go lub tłumaczenie jako pojedyncze sztywny korpus . Jednak ta metoda usztywniania siatki, polegająca na dodaniu poprzeczek do wszystkich jej kwadratów, wymaga użycia znacznie większej liczby poprzeczek, niż jest to konieczne. Problem stężeń siatki wymaga opisu minimalnych zestawów stężeń poprzecznych, które mają ten sam efekt, czyli usztywnienie całej ramy.

Teoretyczne rozwiązanie grafów

Sztywna siatka z nawiasami krzyżowymi i odpowiadający jej dwudzielny wykres w wierzchołkach reprezentujących wiersze i kolumny siatki. Wykres jest drzewem, więc krzyżak wykorzystuje minimalną możliwą liczbę kwadratów w nawiasach klamrowych.

Jak pierwotnie zauważyli Ethan Bolker i Henry Crapo ( 1977 ), problem stężeń siatki można przełożyć na problem w teorii grafów , rozważając nieskierowany graf dwudzielny , który ma wierzchołek dla każdego wiersza i kolumny danej siatki oraz krawędź dla każdego krzyżowo usztywniony kwadrat siatki. Udowodnili, że siatka krzyżowo-stężona jest sztywna wtedy i tylko wtedy, gdy ten dwudzielny graf jest spójny. Wynika z tego, że minimalne krzyżulce siatki odpowiadają drzewom łączącym wszystkie wierzchołki grafu i że mają dokładnie ${\ displaystyle r + c-1}$ skrzyżowane kwadraty. Każde wzmocnione, ale sztywne krzyżowanie (z większą niż ta liczbą kwadratów nawiasów krzyżowych) można zredukować do minimalnego stężenia krzyżowego, znajdując drzewo rozpinające jego wykresu. Mówiąc bardziej ogólnie, liczba stopni swobody w kształcie siatki krzyżowo-stężonej jest równa liczbie połączonych elementów wykresu dwudzielnego minus jeden. Jeśli częściowo usztywniona siatka ma być usztywniona przez usztywnienie większej liczby kwadratów, minimalna liczba dodatkowych kwadratów, które należy wzmocnić, to taka liczba stopni swobody, a rozwiązanie z taką liczbą kwadratów można uzyskać przez dodanie tej liczby krawędzi do grafu dwudzielnego, połączenie par połączonych jego składowych tak, aby po dodaniu pozostała tylko jedna składowa.

Inna wersja problemu wymaga „podwójnego usztywnienia”, zestawu krzyżulców, który jest wystarczająco nadmiarowy, aby pozostał sztywny, nawet jeśli usunie się jedną z przekątnych. Ta wersja pozwala na użycie obu przekątnych jednego kwadratu, ale nie jest to wymagane. W tej wersji podwójne stężenie siatki odpowiada w ten sam sposób nieskierowanemu multigrafowi dwudzielnemu , który jest spójny i bezmostkowy (każda krawędź należy do co najmniej jednego cyklu ). Minimalna liczba przekątnych potrzebnych do podwójnego stężenia to ${\ Displaystyle \ min (2r, 2c)}$ . W szczególnym przypadku siatek z równą liczbą wierszy i kolumn jedynymi podwójnymi stężeniami o tym minimalnym rozmiarze są cykle Hamiltona , więc ustalenie, czy istnieje w większym stężeniu, jest NP-zupełne . Możliwe jest jednak aproksymowanie najmniejszego podwójnego podzbioru stężeń danego stężenia w ramach stałego współczynnika aproksymacji .

Analogiczną teorię, używającą grafów skierowanych , odkryli Jenny Baglivo i Jack Graver ( 1983 ) dla usztywnień rozciąganych , w których kwadraty są usztywnione drutami lub sznurkami (które nie mogą rozszerzyć się poza swoją początkową długość, ale mogą zginać się lub zapadać do krótszej długości) ) zamiast sztywnych prętów. Aby w ten sposób usztywnić pojedynczy kwadrat, konieczne jest usztywnienie obu jego przekątnych, a nie tylko jednej przekątnej. Takie usztywnienie można ponownie przedstawić za pomocą wykresu dwudzielnego, którego krawędź jest skierowana od wierzchołka wiersza do wierzchołka kolumny, jeśli wspólny kwadrat tego wiersza i kolumny jest usztywniony dodatnio nachyloną przekątną, a krawędź z wierzchołka kolumny do wierzchołka rzędu, jeśli wspólny kwadrat jest usztywniony przekątną o ujemnym nachyleniu. Stężona struktura jest sztywna wtedy i tylko wtedy, gdy wynikowy wykres jest sztywny silnie połączone . Jeśli nie, należy dodać dodatkowe usztywnienie, aby połączyć ze sobą mocno połączone ze sobą elementy . Problem znalezienia minimalnego zestawu dodatkowych nawiasów klamrowych do dodania jest przykładem silnego zwiększania łączności i można go rozwiązać w czasie liniowym . Zgodnie z twierdzeniem Robbinsa grafy nieskierowane, które można silnie połączyć, kierując ich krawędzie są dokładnie grafami bezmostkowymi; reinterpretując to twierdzenie w kategoriach stężeń siatkowych, usztywnienie sztywnymi prętami tworzy podwójne usztywnienie wtedy i tylko wtedy, gdy jego pręty można zastąpić drutami (prawdopodobnie na innych przekątnych ich kwadratów), tworząc sztywne usztywnienie rozciągane.

Linki zewnętrzne

• Whitty, Robin, „Twierdzenie o prostokątnych tensegracjach” (PDF) , Twierdzenie dnia