One-Story Buildings as Tensegrity Frameworks

One-Story Buildings as Tensegrity Frameworks by N. Chakravarty, G. Holman, S. McGuinness and A. Recski Rbum6 Topologie structurale #12, 1986 Des klifices d’un 6tage comme charpentes de tensegrit6 Bolker et Crapo [l] ont fourni une solution matro‘idale au probkme du contreventement d’un edifice d’un ttage. Un des objectifs de la prtsente note est de rtsumer leurs resultats en utilisant seulement la thtorie des graphes. his, la 2e partie prtsente des rtsultats analogues pour des charpentes de tenstgritt sptciales (oh les aretes de la grille carrte sont encore des tiges, mais les diagonales sont des cables). Comme il fallait s’y attendre, il suffira d’utiliser des graphes orientts, bien que I’ttude des charpentes de tenstgritt, en gtntral, puisse ntcessiter le recours aux matroides orienttes. Adresses des auteurs: N. Chakravarty, G. Holman et S. McGuinness: Department of Combinatorics & Optimization, University of Waterloo Waterloo, Ontario, Canada N21. 3G1 A. Recski: School of Operations Research & Industrial Engineering, Cornell University Ithaca, New York 14853, U.S.A. Math. Institute, 1.. Eotvos University, H1088 Budapest, Hongrie en congt de: Une partie de cette recherche a ttt faite alors que I’auteur ttait professeur invite A I’University of Waterloo. Abstract Structural Topology #12, 1986 Bolker & Crapo [l] gave a matroidal solution to decide how to brace a one-story building. One of the aims of the present note is to summarize their results using graph theory only. Then, in Part 2, we present analogous results for special tensegrity frameworks (where the edges of the square grid are still rods but the diagonals are cables). As one can expect, directed graphs will be required only, although the study of tensegrity frameworks, in general, might need oriented matroids. Addresses of the authors: N. Chakravarty, G. Holman and S. McGuinness: Department of Combinatorics & Optimization, university of Waterloo Waterloo, Ontario, Canada N2L 3G1 A, Recski: School of Operations Research & Industrial Engineering, Cornell University Ithaca, New York 14853, U.S.A. Math. Institute, I.. Eotvos University, H-1088 Budapest, Hungary on leave from: Part of this research was done while the author was a visitingprofessor at the University of Waterloo. 12 Topologie stnrcturale #12, 1986 abc a 1 2 Figure 1 lre partie Figure 2 Figure 3 Part 1 Soit une grille carrte telle qu'8 la Figure 1. La charpente constitute de barres et de joints correspondante est un mecanisme et peut le demeurer meme aprts I'addition de quelques entretoises diagonales, comme c'est le cas lorsque des entretoises sont ajoutkes aux positions a2, bl et c2, tel que montrC B la Figure 2. Thhr8me 1 [ 11 Soit G, un graphe biparti ayant la bipartition V(G) =A u B, ou les sommets A et B correspondent respectivement aux lignes et aux colonnes de la grille carrke, et ori les arBtes correspondent aux entretoises diagonales. Par exemple, la Figure 3 montre G pour le cas du systtme de la Figure 2. La charpente constituke de barres et de joints est rigide si et seulement si re graphe G correspondant est connexe. Aperqu de la dbmonstration. N'importe quelle dtformation peut ttre complttement dtcrite par les translations horizontales xlr x2, ... des lignes et par les translations verticales y,, yb, ... des colonnes, tel qu'illustrt B la Figure 4. Un carrkcorrespondant B la ie ligne et B la je colonne de la grille conservera sa forme si et seulement si xi = yj, comme y, = x2 B la Figure 4. 1.e systtme entier est rigide si et seulement si x, = x2 = ... = y, = yb = ... L.es entretoises diagonales garantissent ceci si et seulement si le graphe G est connexe. Corollaire 2 IIfaut au moins k + I - 1 entretoises diagonalespour rigidijier unegrille carrke de k x I. Un ensemble dexactement k +I - 1 entretoises suffit si et seulement si G est un arbre partiel. Corollaire 3 Soit un groupe dentretoises qui produit WI syst2me rigide. Une entretoise donnPe est critique (c'est-cf-dire que sa suppression crke un mkcanisme) si et seulement si la suppression de I'arBte correspondante dans le graphe le disjoint. Ces dnoncCs sont de simples constquences des observations prtcCdentes. Par exemple, les deux systtmes de la Figure 5 sont rigides et renferment six entretoises diagonales, mais seulement le premier rtsiste B la perte d'une seule des membrures. I,e principal rksultat de [I] a trait aux &ifices d'un Ctage. I1 est facile de constater qu'une entretoise diagonale dans un mur vertical empeche les dtformations lites B un mouvement Flgure 5 Firstly, let us consider a square grid, as in Figure 1. The corresponding bar and joint framework is a mechanism and may remain so even after the addition of some diagonal braces, as is the case when braces are added at positions a2, bl and c2, as shown in Figure 2. Theorem 1 [I] Let G be a bipartitegraph with bipartition V(G) =A u B, where the vertices of A and B correspond to the rows and to the columns of the square grid, respectively, and edges correspond to diagonal braces. For example, Figure 3 shows Gin case of the system of Figure 2. The bar and joint framework is rigid if and only if the corresponding graph G is connected. Sketch of Roof. Any deformation can fully be described by the horizontal translations x,, x2, ... of the rows and by the vertical translations y,, yb, ... of the columns, as illustrated in Figure 4. Asquare, corresponding to the ith row andjth column of the grid, will maintain its shape if and only if xi = y. like y, = x2 in Figure 4. The full system is rigid if and only if x, = x2 = ,.. = y, = yb = ... &e diagonal braces insure this if and only if the graph G is connected. Corollary 2 At least k + I - 1 diagonal braces are required to make a k x I square grid rigid. A set of exactly k + 1 - 1 braces is appropriate if and only if G is a spanning tree. Corollary 3 Suppose a given collection of braces yielak a rigid system. A given brace is critical (i.e. its removal leads to a mechanism) if and only if the corresponding edge in the graph is a separating edge. These statements are simple consequences of the above observations. For example, both systems of Figure 5 are rigid and contain six diagonal braces, but only the first one is resistant to the failure of single members. The main results of [l] refer to one-story buildings. One can easily see that a diagonal brace in a vertical wall prevents those deformations for which the wall moves along itself. Structural Topology #12, 1986 13 Figure 1 Figure 6 Figure 10 Figure 8 w Figure 9 14 Topoiogie structuraie #12, 1986 du mur dans son plan. Donc deux de ces entretoises x, y dans des murs verticaux qui se croisent immobilisent la droite d’intersection en entier (Figure 6). Donc, si chacun des murs verticaux externes renferme une entretoise (Figure 7), alors le problhe de determiner lequel de deux edifices d’un etage est rigide se rCduit au suivant: laquelle des deux grilles carrtes de la Figure 8 est rigide si leurs coins sont fixis au plan? De toute evidence, si une telle grille est non rigide, elle n’a que des mouvements infinitesimaux comme A la Figure 10. Un ensemble de k + I - 1 entretoises ou plus, qui dttermine un graphe connexe, serait certainement suffisant selon le theorhe 1, mais il n’est pas necessaire. Des ensembles bien choisis de k + I - 2 entretoises suffiront aussi. Thbr&me 4 [2] Soit uneforPt de deux composantes diterminkepar un ensemble de k +I - 2 entretoises, Ies classes de bipartition des deux composantes GI et G2 itant respectivement de cardinalitik, et I,. et k, et I,. (Donc k = k, + k2 et I = I, + I,.) L’ensemble dentretoisesproduit un systime rigide si et seulement si k/I, z k2/12 z k/l. Par exemple, pour lepremier systhede la Figure 8, oh k = 4, I= 6, k, = k2 = 2, I, = I, = 3, les trois rapports sont identiques. Pour le second systkme oh k = 4, I= 6, kl = k2 = 2, I, = 2, I, = 4, les trois rapports sont diffkrents (Figure 9). Aperqu de la demonstration. [ 13 Lorsque les quatre coins de la grille carrte sont fixts, il s’ensuit que: (1) x, +x2+ ... +xk =O et y, +y2+ ,.. +y,=O Donc, en plus des k + I - 2 equations de la forme xi = xi, auxquelles correspondent les entretoises, les equations de (I) sont disponibles. Suppposons que k,/Il = k2/12, et considkrons stpartment GI et G,. Si un x ou un y appartient GI, notons c, la valeur correspondante; sinon notons-la c,. Les Cquations de forme xi = yjsont automatiquement satisfaites. De plus, si k,c, + k2c2 = I,cl + 12c2 = 0 et cI z 0 ou c2 z 0, alors la solution de (1) est non triviale, c’est-&-dire qu’une deformation est obtenue. D’autre part, considirons le systhe d’iquations S, constitut des Cquations de (1) et des k + 1 - 2 equations de forme xi = yj d’un sous-systbe (2). Si S a une solution non triviale, alors les vecteurs des lignes de la matrice de coefficients M de S sont IinCairement dtpendants. Considirons une telle combinaison lineaire non triviale des vecteurs des lignes. Soient A et p, les coefficients des lignes correspondant a (1). Quels que soient les autres coefficients, il s’ensuit que Ak = -PI, puisque chaque ligne de (2) a exactement deux entrCes non nulles, une pourx et une poury. Lorsque la meme discussion est rCpCtCe pour les blocs de M, qui correspondent aux deux composantes GI et G,, il s’ensuit que kl/Il = k2A2 = k/I. Hence two such braces x, y in intersecting vertical walls fix the whole line of intersection (Figure 6). Thus, if each external vertical wall contains a brace (Figure 7) then the problem of determining, which of the two one-story buildings is rigid, reduces to the following: Which of the two square grids of Figure 8 is rigid if their corners are fixed to the plane? Obviously, if such a grid is non-rigid, it has infinitesimal motions only, as in Figure 10. A set of k + I - 1 or more braces, determining a connected graph, would certainly be sufficient by Theorem 1, but is not necessary. Appropriate sets of k + I - 2 braces will also do: Theorem 4 [2] Let's set of k + I - 2 braces determine a 2-component forest. Let the bipartition-classes of the two components GI and C2 be of cardinality k, andl,, andk, and 1,. respectively. (Hence k = k, + k2 and I = I, + 12) The set of braces leads to a rigidsystem ifand onIy ifk,/Il z k2/12 z k/I. For example, in the first system of Figure 8, where k = 4, I = 6, k, = k2 = 2, I, = 1, = 3, the three ratios are the same. For the second system where k = 4, I = 6, k, = k2 = 2, I, = 2, I, = 4, the three ratios are all different (Figure 9). Sketch of Proof. Observe [ 13 that fixing the four corners of the square grid means that (1) x,+x,+ ...+ xk=O and y,+y,+ ...+y, =O Thus, in addition to the k + I - 2 equations of the form xi =xi, reflected by the braces, we have the equations of (1). Suppose kl/Il = k2/12. Consider G, and G, separately. If an x or y belongs to GI, let its corresponding value be c,, otherwise let it be c2. The equations of form xi = yj are automaticallysatisfied. Furthermore,ifk,c, + k2c2 =l,c, + 12c2 =Oandc, zOorc, zOthen we have a nontrivial solution of (I), i.e. a deformation is obtained. On the other hand, consider the system S of equations, consisting of the equations of (1) and the k + I - 2 equations of form xi = yj of a subsystem (2). If S has a nontrivial solution then the row vectors of the coefficient matrix Mof S are linearly dependent. Consider such a nontrivial linear combination of the row vectors and let A and p be the coefficients of the rows, corresponding to (1). No matter what the other coefficients are, we obtain Ak = -PI, since each row of (2) has exactly two nonzero entries, one for an x and one for a y. Repeating the same argument for the blocks of M, corresponding to the two components GI and G2, yields kl/ll = k2A2 = k/I. 2e partie Structural Topology U12, 1986 15 Part 2 La suite de cette note formule les analogues des thiortrnes 1 et 4 pour les grilles carr6es avec clbles diagonaux. D’abord, il est ii noter que dans le cas des clbles, leur direction est importante. I1 sera dCmontr6 que la premikre charpente de tensCgrit6 de la Figure 11 est rigide (les tiges et les clbles sont reprksentts respectivement par des lignes pleines et pointilltes) alors que la seconde charpente ne l’est Cvidemment pas (Figure 12). Par conskquent le modtle fera appel a des graphes orientis. I1 faut se rappeler que les lignes et les colonnes de la grille correspondent respectivement aux ensembles de points du bas et du haut du graphe biparti (Figure 3). Pour les deux charpentes de la Figure 11, une arete sera orientke vers le haut si le clble correspondant est en position sud-ouest/nord-est, et vers le bas s’il est en position nord-ouest/sud-est (Figure 13). I1 faut aussi se rappeler qu’un graphe orient6 est dit fortement connexe si pour toute paire de sommets u, v il existe un chemin orient6 de u vers v et un autre de v vers u. Thhrhe 5 [3] Une charpente de tensigriti est rigide si et seulement si le graphe orient& correspondant est fortemenr connexe. Dkmonstration. Assignons xi un signe positif si les arttes horizontales du haut des carrks de la ligne i se d6placent vers la gauche (par rapport aux arCtes du bas), et un signe negatif autrement. De la mCme facon, assignons un signe positif a yj si les aretes du cat6 droit des cads de la colonnej se dkplacent vers le haut (par rapport aux arttes du cat6 gauche), et negatif autrement. Alors un clble entraine une inkquation xi z yj s’il y a une arete orient& de i vers j, et xi I y, si l’arete est orient6e de j vers i. S’il y a dans le graphe un chemin orient6 P,,allant du sommet u au sommet v, alors toutes les inCgalitCs, qui correspondent aux aretes de Puv, ont la meme direction. S’il est possible de trouver un autre chemin P,, allant de v a u, alors toutes les intgalitks se transforment en CgalitCs. Par exemple, il decouledes chemins orientis (1, b, 2)et (2, a, 1)du premier graphe de la Figure 13 que x, 2 yb 5 x2 2 yo 2 x,. Donc la forte connexit6 du graphe orient6 implique la rigidit6 de la charpente. ab ab In the rest of this note we formulate the analogues of Theorems 1 and 4 for square grids with diagonal cables. First of all observe that in case of cables, their direction is of importance. We shall see that. the first tensegrity framework of Figure 11 is rigid (rods and cables are denoted by continuous and dotted lines, respectively) while the second framework is obviously not (Figure 12). Hence we shall use directed graphs in our model. Recall that rows and columns of the grid corresponded to the lower and upper point sets of the bipartite graph, respectively (Figure 3). Let us orient and edge up if the corresponding cable has a Southwest-Northeast position and down if it is in a Northwest-Southeast position (Figure 13) for the two frameworks of Figure 11. Recall that a directed graph is called strongly connected if for any two vertices u, v there exists a directed path from u to v and another from v to u. Theorem 5 [3] The tensegrity framework is rigid ifand only if the corresponding directed graph is strongly connected. Proof. Let us assign a positive sign to xi if the upper horizontal edges of the squares of row i move to the left (relative to the lower edges), and a negative sign otherwise. Similarly, let yj be positive if the right hand side edges of the squares of column j move upwards (relative to the left hand side edges) and negative otherwise. Then a cable means an inequality xizyjif there is an edge directed from i tojand xi 5 yjif the edge is directed from j to i. Ifthere is a directed path P,,, in our graph from vertex u to vertex v then all the inequalities, corresponding to the edges ofP,,,, have the same direction. If another path P,, from v to u can also be found then all the inequalities are met by equality. For example, the directed paths(l,b,2)and(2,a, 1)in thefirstgraphofFigure13meansx,zybzx,zy,zx,. Hence the strong connectedness of the directed graph implies rigidity of the framework. MI4 12 12 Figure 11 Figure 12 Flgure 13 16 Topologie siructurale #12, 1986 Si le graphe orient6 n’est pas fortement connexe, alors I’ensemble des sommets du graphe peut Stre decompose en deux parties telles que toutes les aretes soient orienttes de la seconde partie vers la premite. Assignons une petite (mais Cgale) valeur aux variables xet y correspondant aux sommets de la premiire partie, et une plus grande valeur commune aureste. Cecidttermineunedtformationde lacharpente. Parexemple,~, = yo<o<x2 =yb, oh xI = -x2 et yo = -yb dtcrit la deformation montree a la Figure 12. Ceci correspond ?i la decomposition { 1, a} u {2, b}. If the directed graph is not strongly connected then the vertex set of the graph can be decomposed into two parts so that every edge is oriented from the second part towards the first part. Assign smaller (but equal) values to the x and y variables, corresponding to vertices of the first part and a greater common value to the rest. This determines a deformation of the framework. For example, xI = yo < 0 < x2 = yb, where xI = -x2 and yo = -yb describes the deformation shown on Figure 12. This corresponds to the decomposition (1, a) u {2, b). Corollaire 6 [3] I1 faut au moins 2 max(k, r) cables diagonaux pour rigidifer une grille Carrie de k x 1. Dhonstration. Supposons que I’ensemble de points du bas compte a = max(k, I) sommets et que celui du haut compte b = min(k, I) sommets. Par suite de la forte connexite, chaque point du bas doit compter une arete orientte qui vient vers lui et au moins une arete orientee qui s’tloigne de hi. Puisque le graphe est biparti, il ne peut exister deuxpoints du bas adjacents. Par constquent ces 2a arktes sont toutes diffkrentes. La Figure 14 montre que cette limite est nette, c’est-&dire que ce nombre de cables est toujours suffisant. Remarque. L,es entretoises diagonales, sans &re des cables, peuvent aussi etre plus fiables en traction qu’en compression. Par consequent, si deux entretoises diagonales perpendiculaires sont utilistes au lieu d’une seule dans certains carrts, alors il faut 2(k + I1) entretoises selon le corollaire 2, soit presque deux fois I’optimum donnt par le corollaire 6. Finalement, considtrons un edifice d’un &age de taille k x I. Supposons que les quatre murs verticaux externes soient rigides (grace a une tige ou deux clbles chacun). I1 suffit alors de prendre en considtration une grille rectangulaire de k x I dont les quatre coins sont fixes au plan. Combien faut-il de cables diagonauxpour en eliminer les mouvements infinittsimaux? Thbrhe 7 [4] Soit k, I? 2 et k + 12 5. Alors il faut au moins k + I - 1 cribles diagonaux pour rigidper le systime. Dhonstration. Si un ensemble de cables rigidifie un systhe, la substitution de tiges A ces cables ne peut pas dttruire la rigidite. Par consequent, d’apris le thtorime 4, moins de k +I2clbles ne peuvent suffire. De la meme faqon, s’il existait un systime ayant k +I2 cables, le graphe G correspondant devrait &re une for& a deux composantes oh kl/ll # k2/12 (cf. thkorime 4 pour la notation). L.es deux composantes GI et G2 de G ont chacune au moins une source et au moins un puits. Si une des classes de bipartition de G renferme a la fois une source s et un puits t, alors assignons une valeur de +I As, de -1 A t et de 0 A tous les autres sommets. Ceci dttermine une deformation de la charpente. Corollary 6 [3] At least 2 max(k, r) diagonal cables are required to make a k x I square grid rigid, Proof. Suppose that the lower point set has a = max(k, I) vertices and the upper one has b = min(k, I) vertices. Every lower point must have an edge oriented towards it and at least one edge oriented away from it, by the strong connectivity. Since the graph is bipartite, no two lower points can be adjacent. Hence these 2a edges are all different. Figure 14 shows that this bound is sharp, i.e. that this number of cables is always enough. Remark. Diagonal braces (not cables) may also be more reliable under tension than under compression. Therefore if one applies two perpendicular diagonal braces, rather than just one of them, in some squares then 2(k + I - 1) braces would be needed by Corollary 2; nearly twice as many as the optimum, given by Corollary 6. Finally, let us consider a k x I-sized one-story building. Suppose that the four external vertical walls are rigid (by using one rod or two cables in each). We need only consider a k x I rectangular grid with all the four corners fixed to the plane. How many diagonal cables can prevent its infinitesimal motions? Theorem I [4] Let k, I? 2 and k + 12 5. Then at least k +I - 1 diagonal cables are required to make the system rigid. Proof. Ifa set of cables makes a system rigid, changing the cables to rods cannot destroy rigidity. Hence less than k + I - 2 cables cannot be enough, by Theorem 4. Similarly, if there were a system with k + I - 2 cables, the corresponding graph G should be a 2-component forest with k,/ll # k2/12 (see the notation in Theorem 4). Both components GI and G2 of G have at least one source and at least one sink each. If one of the bipartition classes of G contains both a sources and a sink t then assign the values + 1 to s, - 1 to I and 0 to all the other vertices. This determines a deformation of the framework. Structural Topology #I2, I986 17 Si toutes les sources sont dans la classe de bipartition A et tous les puits dans B, alors soit s unesourcede GI et soit funpuitsde G2. Assignonsunevaleurdex-~~PsetdexAtousles autressommetsde Gl;puisdey-yoPretdeyP touslesautressommetsde G2. Cesystkme satisfait aux inkgalitb si xo > 0 et yo < 0, et satisfait aussi P (1) si se vbrifie. hisque la matrice est non singulihre, il est possible de trouver des valeurs convenables pour x et y si xo et yo sont fixks. Par conskquent une dkformation de la charpente est obtenue. Finalement, il faut dkmontrer que k + I - 1 cables peuvent rigidifier un systbme. Soit k I I. Considkrons le graphe de la Figure 15, c'est-Pdire le systkme montrC P la Figure 16. Supposons que les quantitks xl, x2, ..., xk; yI, y,, ..,, yl satisfont P k I i= 1 j= 1 X xi=O et P yj=O et xisyl pour 1 cisk- ~;y, 5xk;etxk~y,pour2Ij~f. Amoinsqu'elIesnesoient toutesnulles,le seul cas possible est que xi 5 yI < 0 < xk 5 yj (pour tout 1 5 i 5 k - 1 et 2 5 j 5 I). Par conskquent k kI i= I i= I 0 = x xi = xk + P xi 5 xk + (k - 1)yl = xk f yI + (k - 2)yl Donc, si k 2 3, alors de k k I xk+yl+(k-2)yl<xk+yl + y.c z yjs X y'=o j=3 J-pl j=I J il dkoule une contradiction. Si k = 2 et I > 2, alors de I j= I Xk + + (k - 2)yl = X2 + I + y2 < yj = 0 il dkcoule encore une contradiction. Ifall the sources are in the bipartition classA and all the sinks in B then let s be a source of GI and t be a sink of G1. Assign the values x -xo tos and x to every other vertex of GI; then y -yo to r and y to every other vertex of G2. This system satisfies the ineqlralities if xo > 0 and yo < 0, and also satisfies (1) if holds. Since the matrix is nonsingular, we can find suitable values for x and y if xo and yo are fixed. Hence we obtain a deformation of the framework. Finally we have to prove that k + I - 1 cables can lead to a rigid system. Let k 5 I and consider the graph of Figure 15, i.e. the system shown on Figure 16. Suppose that the quantities xI, x2, ..-, xk; yI, y2, ..., yl satisfy k I i= 1 j= I P xi=O and X yj=O and xiiyl for Isilkl;y, ~xk;andxk~y~for 21jsf. Unlessallofthemarezero, theonlypossible case is xi 5 yI < 0 < xk syj (for every 1 I i I k - 1 and 2 S~I I). Hence k kI 0 = z xi = xk f xi I xk (k - 1)yl = xk + yI + (k - 2)yI i=l i= 1 Thus, if k 2 3 then k kI x& YI + (k - 2)yl < xk + YI +j53 yj sj51 uj ';.fi yj = leads to a contradiction. If k = 2 and I > 2 then I j= 1 Xk + (k - 2)yl 5 X2 Iyl +y, C )'j = 0 again a contradiction. Y, Y2 Y3 Y4 Yl x1 x2 x3 xk-l xk Figure 14 Figure IS 18 Topologie structurale #12, 1986 Remarque. Cette derniere ktape dkmontre que cette construction n’est pas valide pour k = I = 2 (Figure 17). Remark. This last step shows that the construction fails for k = I = 2 (Figure 17). Figure 17 Rbfbrences - References [l] E.D. Bolker & H. Crapo, “How to Brace a One-Story Building?”, Environment and Planning B, 4 (1977) 125-152. [2] H. Crapo, “More on the Bracing of One-Story Buildings”, Environment and Planning B, 4 (1977) 153-156. [3] A. Recski, Matroid Theory and its Applications, Springer Verlag, Berlin and AkadCmiai Kiadb, Budapest, to appear. [4] N. Chakravarty, G. Holman & S. McGuinness, projects reportshapports de projets, University of Waterloo, 1984.