Grid bracing

Last updated

In the mathematics of structural rigidity, grid bracing is a problem of adding cross bracing to a square grid to make it into a rigid structure. It can be solved optimally by translating it into a problem in graph theory on the connectivity of bipartite graphs. [1] [2] [3]

Contents

Problem statement

An unbraced square grid with six rows and four columns, and a non-square grid obtained from a continuous motion of it Grid-flex.svg
An unbraced square grid with six rows and four columns, and a non-square grid obtained from a continuous motion of it

The problem considers a framework in the form of a square grid, with rows and columns of squares. The grid has edges, each of which has unit length and is considered to be a rigid rod, free to move continuously within the Euclidean plane but unable to change its length. These rods are attached to each other by flexible joints at the vertices of the grid. A valid continuous motion of this framework is a way of continuously varying the placement of its edges and joints into the plane in such a way that they keep the same lengths and the same attachments, but without requiring them to form squares. Instead, each square of the grid may be deformed to form a rhombus, and the whole grid may form an irregular structure with a different shape for each of its faces, as shown in the figure. [1] [2] [3]

A square can flex to form a rhombus, but a triangle forms a rigid structure Structural rigidity basic examples.svg
A square can flex to form a rhombus, but a triangle forms a rigid structure

Unlike squares, triangles made of rigid rods and flexible joints cannot change their shapes: any two triangles with sides of the same lengths must be congruent (this is the SSS postulate). If a square is cross-braced by adding one of its diagonals as another rigid bar, the diagonal divides it into two triangles which similarly cannot change shape, so the square must remain square through any continuous motion of the cross-braced framework. (The same framework could also be placed in the plane in a different way, by folding its two triangles onto each other over their shared diagonal, but this folded placement cannot be obtained by a continuous motion.) Similarly, if all squares of the given grid were cross-braced in the same way, the grid could not change shape; its only continuous motions would be to rotate it or translate it as a single rigid body. However, this method of making the grid rigid, by adding cross-braces to all its squares, uses many more cross-braces than necessary. The grid bracing problem asks for a description of the minimal sets of cross-braces that have the same effect, of making the whole framework rigid. [1] [2] [3]

Graph theoretic solution

A rigid cross-braced grid, and the corresponding bipartite graph on vertices representing the rows and columns of the grid. The graph is a tree, so the cross-bracing uses the minimum possible number of braced squares. Grid-bracing.svg
A rigid cross-braced grid, and the corresponding bipartite graph on vertices representing the rows and columns of the grid. The graph is a tree, so the cross-bracing uses the minimum possible number of braced squares.

As EthanBolkerand Henry Crapo  ( 1977 ) originally observed, the grid bracing problem can be translated into a problem in graph theory by considering an undirected bipartite graph that has a vertex for each row and column of the given grid, and an edge for each cross-braced square of the grid. They proved that the cross-braced grid is rigid if and only if this bipartite graph is connected. It follows that the minimal cross-bracings of the grid correspond to the trees connecting all vertices in the graph, and that they have exactly cross-braced squares. Any overbraced but rigid cross-bracing (with more than this number of cross-braced squares) can be reduced to a minimal cross-bracing by finding a spanning tree of its graph. More generally, the number of degrees of freedom in the shape of a cross-braced grid is equal to the number of connected components of the bipartite graph, minus one. If a partially braced grid is to be made rigid by cross-bracing more squares, the minimum number of additional squares that need to be cross-braced is this number of degrees of freedom, and a solution with this number of squares can be obtained by adding this number of edges to the bipartite graph, connecting pairs of its connected components so that after the addition there is only one remaining component. [1] [2] [3] [4]

Another version of the problem asks for a "double bracing", a set of cross-braces that is sufficiently redundant that it will stay rigid even if one of the diagonals is removed. This version allows both diagonals of a single square to be used, but it is not required to do so. In this version, a double bracing of a grid corresponds in the same way to an undirected bipartite multigraph that is connected and bridgeless (every edge belongs to at least one cycle). The minimum number of diagonals needed for a double bracing is . [1] In the special case of grids with equal numbers of rows and columns, the only double bracings of this minimum size are Hamiltonian cycles, so determining whether one exists within a larger bracing is NP-complete. However, it is possible to approximate the smallest double bracing subset of a given bracing within a constant approximation ratio. [5]

An analogous theory, using directed graphs, was discovered by JennyBaglivoandJack Graver ( 1983 ) for tension bracing, in which squares are braced by wires or strings (which cannot expand past their initial length, but can bend or collapse to a shorter length) instead of by rigid rods. To make a single square rigid in this way, it is necessary to brace both of its diagonals, instead of just one diagonal. One can again represent such a bracing by a bipartite graph, which has an edge directed from a row vertex to a column vertex if the shared square of that row and column is braced by the positively-sloped diagonal, and an edge from a column vertex to a row vertex if the shared square is braced by the negatively-sloped diagonal. The braced structure is rigid if and only if the resulting graph is strongly connected. [1] [2] If not, additional bracing needs to be added to connect together its strongly connected components. The problem of finding a minimal set of additional braces to add is an instance of strong connectivity augmentation, and can be solved in linear time. [6] According to Robbins' theorem, the undirected graphs that can be made strongly connected by directing their edges are exactly the bridgeless graphs; reinterpreting this theorem in terms of grid bracing, a bracing by rigid rods forms a double bracing if and only if its rods can be replaced by wires (possibly on the other diagonals of their squares) to form a rigid tension bracing. [7]

Related Research Articles

Graph theory Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Hamiltonian path

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph (discrete mathematics) Mathematical structure consisting of vertices and edges connecting some pairs of vertices

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

Eulerian path

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related and 0 if they are not. There are variations; see below.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is called a planar matroid; these are exactly the graphic matroids formed from planar graphs.

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0.

The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices but has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.

Rooks graph

In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs or as the line graphs of complete bipartite graphs.

In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge that makes it into a strongly connected graph.

Structural rigidity Combinatorial theory of mechanics and discrete geometry

In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.

In graph theory, Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.

In discrete mathematics, the Bregman–Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix via its row or column sums. The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev M. Bregman. Further entropy-based proofs have been given by Alexander Schrijver and Jaikumar Radhakrishnan. The Bregman–Minc inequality is used, for example, in graph theory to obtain upper bounds for the number of perfect matchings in a bipartite graph.

Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures is an undergraduate-level book on the mathematics of structural rigidity. It was written by Jack E. Graver and published in 2001 by the Mathematical Association of America as volume 25 of the Dolciani Mathematical Expositions book series. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion by undergraduate mathematics libraries.

Incidence and Symmetry in Design and Architecture is a book on symmetry, graph theory, and their applications in architecture, aimed at architecture students. It was written by Jenny Baglivo and Jack E. Graver, and published in 1983 by Cambridge University Press in their Cambridge Urban and Architectural Studies book series. It won an Alpha Sigma Nu Book Award in 1983, and has been recommended for undergraduate mathematics libraries by the Basic Library List Committee of the Mathematical Association of America.

Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph.

References

  1. 1 2 3 4 5 6 Baglivo, Jenny A.; Graver, Jack E. (1983), "3.10 Bracing structures", Incidence and Symmetry in Design and Architecture, Cambridge Urban and Architectural Studies, Cambridge, UK: Cambridge University Press, pp. 76–87, ISBN   9780521297844
  2. 1 2 3 4 5 Graver, Jack E. (2001), Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures, The Dolciani Mathematical Expositions, 25, Washington, DC: Mathematical Association of America, ISBN   0-88385-331-0, MR   1843781 . See in particular sections 1.2 ("The grid bracing problem", pp. 4–12), 1.5 ("More about the grid problem", pp. 19–22), 2.6 ("The solution to the grid problem", pp. 50–55), and 4.4 ("Tensegrity: tension bracings", particularly pp. 158–161).
  3. 1 2 3 4 Kappraff, Jay (2001), "4.18 Bracing structures", Connections: The Geometric Bridge Between Art and Science, Series on Knots and Everything, 25 (2nd ed.), Singapore: World Scientific, pp. 154–159, ISBN   9789810245856, MR   1868159
  4. ↑ Bolker, E. D.; Crapo, H. (1977), "How to brace a one-story building", Environment and Planning B: Planning and Design, 4 (2): 125–152, doi:10.1068/b040125
  5. ↑ Cheriyan, J.; Sebő, A.; Szigeti, Z. (2001), "Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph", SIAM Journal on Discrete Mathematics, 14 (2): 170–180, doi:10.1137/S0895480199362071, MR   1856004
  6. ↑ Gabow, Harold N.; Jordán, Tibor (2000), "How to make a square grid framework with cables rigid", SIAM Journal on Computing , 30 (2): 649–680, doi:10.1137/S0097539798347189, MR   1769375
  7. ↑ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly , 46 (5): 281–283, doi:10.2307/2303897, JSTOR   2303897
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.