Graphs and Circulation in Rural Housing

Year: 2003 Authors: Mª Francisca Blanco; Miriam Pisonero

Core claim

Circulation diagrams modeled as graphs can objectively characterize room access, centrality, and privacy in rural housing.

Topics

graph theory, circulation diagrams, rural housing, architectural analysis

Domains

graph invariants, adjacency matrix, degree sequence, eccentricity, architecture, rural vernacular design, housing layout

Methods

floor plan to graph mapping, adjacency analysis, descriptive statistics, isomorphism comparison

Media

ground plan, circulation diagram, adjacency matrix, tables

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

ISAMA The International Society of the Arts, Mathematics, and Architecture BRIDGES Mathematical Connections in Art, Music, and Science

Graphs and Circulation in Rural Housing

Mª Francisca Blanco and Miriam Pisonero Departamento de Matemática Aplicada Fundamental E. T. S. de Arquitectura, Universidad de Valladolid Avenida de Salamanca s/n 47014 Valladolid, España E-mails: fblanco@maf.uva.es and mpisoner@maf.uva.es

Abstract

In our opinion, an objective tool for studying the quality of, and circulation, or movements thorough a dwelling house is the Theory of Graphs. We associate a graph to a ground plan, which is known as a circulation diagram by Architects; the vertices are the rooms and the edges are the direct connections between two rooms. In this paper we use these graphs, together with certain mathematical invariants associated with them, to analyze the movements of people through different rural houses.

1. Invariants of a graph

A graph $G$ can be described, at least, in three ways:

• A pictorial diagram of points, called vertices, and line segments joining the vertices, called edges. The actual way in which the graph is drawn is of no significance to the theory. The vertices may be placed anywhere in the plane, and the edges do not need to be straight, nor of any fixed length.
• A pair $(V(G),E(G))$ where $V(G)$ is a non-empty finite set of elements, called vertices, and $E(G)$ is a finite family of two elements sets of elements of $V(G)$, called edges.
• A square symmetric matrix $\mathrm{Adj}(G)=(a_{i,j})$ with non-negative integer entries, where its rows (or columns) represent the vertices of $G$ and its elements represent the edges of $G$ (i.e. $a_{i,j}$ is the number of edges between vertex $i$ and vertex $j$). This matrix is called the adjacency matrix of $G$.

The value of the graph lies in its capacity to show the essential structure of a set of relationships.

The graphs that we are going to use in this work are always circulation diagrams of ground plans: the vertices are the rooms, which will be labeled by positive integer numbers, and the edges are the direct connections between two rooms. Such diagrams are useful in representing the connections among the rooms, but they do not give us any information about the size or shape or localization of the rooms. Let us show this with a particular example, a house in Nava del Rey. Nava del Rey is a village of Valladolid, a central province of the autonomous region of Castile and León in Spain. Valladolid is a zone of bleak plateau and its highest height is $900\mathrm{m}$. Many of the houses in this region are formed from mud walls and adobe. The façade and the party wall were covered with mud, often mixed with straw, because it fastens better and improves the mortar. But when it is not easy to make a mud wall, because of the absence of clay in the earth, frequently brick is used. Brick architecture has Moorish origins, and can be found in villages such as Nava del Rey, where also all houses have their party walls lined with brick. Wooden floor framing, of Mudejar influence, vertical wooden frames and cover of roofing tile were used.

433

Figure 1: The ground plan of a house of Nava del Rey and its associated graph $G$ can be described in three ways.

If $u$ and $v$ are vertices of a graph $G$ , then an edge of the form $\{u,v\}$ is said to join $u$ and $v$ , and that $u$ and $v$ are adjacent. Two or more edges joining the same pair of vertices are called multiple edges. In the previous example there are no multiple edges, but these can appear in the graphs, when two rooms are connected by more than one door. An edge joining a vertex to itself is called a loop, but this is meaningless for graphs associated to a ground plan. A graph with no loops and no multiple edges is called a simple graph, and in this case $E(G)$ is a set and the adjacency matrix has zeros in the main diagonal and zeros or ones out of it. The graph in our example is a simple graph.

While it is possible to represent a graph by many diagrams, by providing names to vertices of the graph enables it to be stored in a computer. However, we are interested in studying properties that do not depend either on the diagrams or on the names of the vertices. Two graphs $G$ and $H$ are isomorphic if there exists a bijection $f$ between $V(G)$ and $V(H)$ that preserves the adjacency relation, then $G$ and $H$ have the same structural properties. Equivalently, two graphs $G$ and $H$ are isomorphic if there exists a permutation matrix $P$ such that $P^{\mathrm{J}}\mathrm{Adj}(H)P=\mathrm{Adj}(G)$ . A permutation matrix $P$ is one, in which there is a single element equal to 1 in every row and column, all other elements being zero. In other words, the rows of $P$ consist of a permutation of the rows of $I$ , where $I$ is the identity matrix of the same order as $P$ . If $G$ and $H$ are isomorphic we will write $G=H$ . When a mathematical entity assigned to a graph $G$ is

equal, up to a reordering, to that assigned to any other graph $H$ isomorphic to $G$, it is said that it is a graph invariant. So the number of vertices, the number of edges, the number of multiple edges and the number of loops are graph invariants. Let us show this with a particular example.

$(V(G),E(G))=(V(G^{\prime }),E(G^{\prime }))$

and $\mathrm{Adj}(G)=\mathrm{Adj}(G^{\prime })$

Figure 2: Two different representations of the previous graph $G$.

$f$ is a bijection that preserves the adjacency relation $\Rightarrow G\approx H$ $E(G)\ne E(H)\Rightarrow G\ne H$

$P^{\prime }\mathrm{Adj}(H)P=\mathrm{Adj}(G)\Rightarrow G\approx H$

$\mathrm{Adj}(G)\ne \mathrm{Adj}(H)\Rightarrow G\ne H$

Figure 3: The graph $H$ is isomorphic, and not equal, to the previous graph $G$.

435

Note that when trying to understand whether two graphs are equal or isomorphic it is better to use their definitions as a pair, or as a matrix, rather than the pictorial diagram.

One of the aspects concerned with the circulation in a house, is the number of rooms accessible from a particular room. The mathematical notion for this is the degree of a vertex. The degree, or valency, of a vertex $u$ in a graph $G$ (loopless), denoted by $gr(u)$, is the number of edges meeting at $u$. Using the adjacency matrix of $G$, $\mathrm{Adj}(G)$, the degree of $u$ is the sum of all the elements in its $u$-row (or $u$-column). In architecture, vertices with greatest degree correspond to circulation spaces (vertex 3, passage, in the example of graph $G$) or to the main spaces served by the others. Vertices whose degree is one are called terminal vertices. These correspond to areas infrequently used (vertex 6, garret stairs, in $G$); or to areas that require greater privacy (vertices 7, 8 and 9, all bedrooms, and 12, dining room, in $G$); or to areas, because of functional reasons, such as noises or smells, which must not be directly linked with other areas (vertex 6, garret stairs, in $G$). The maximum degree $g{r}_{\text{max}}$, the minimum degree $g{r}_{\text{min}}$ and the degree sequence are graph invariants. A graph is said to be regular when all its vertices have the same degree. Because regular graphs are infrequent in architecture, we are studying the sharing out of degrees with descriptive statistical measures. Remember that the sum of the vertex degrees is equal to twice the number of edges (handshaking lemma or first theorem of Graph Theory). This result provides an easy way of computing the average vertex degree, $gr=2m/n$, and bounds for it, $g{r}_{\text{min}}\le gr\le g{r}_{\text{max}}$, where $m$ is the number of edges and $n$ the number of vertices. Let us show the degree sequence with the graph $G$ associated to a house in Nava del Rey.

Figure 4: Graph $G$ and its degree sequence.

The degree of a vertex depends only upon the local structure of that vertex. Let us consider other notions that involve the global structure of the graph. A walk of length $k$ in a graph $G$ is a finite sequence ${\nu }_0,e_1,{\nu }_1,e_2,\dots ,e_k,{\nu }_k$ of vertices and edges of $G$ such that $e_i=\{{\nu }_{i-1},{\nu }_i\}$ for all $i$, and we say that this walk is a walk between ${\nu }_0$ and ${\nu }_k$. Note that if $G$ is simple, the walk is completely determined by the sequence of vertices. A cycle in $G$ is a walk with no repeated vertex and with the first vertex, ${\nu }_0$, and the last vertex, ${\nu }_k$, equal. The girth of a graph $G$ is the length of a shortest cycle, if $G$ has a cycle, and $\infty$ otherwise. The girth is also a graph invariant. A graph is connected if there is a walk between any given pair of vertices, and disconnected otherwise. Note that the graph associated to a ground plan, in the form already explained, is always connected: an isolated space is meaningless. The graph of figure 4 is connected and only has one cycle, “1, 2, 3, 13, 1”, which has length four so the girth of this graph is 4.

The connection of a graph $G$ allows us to define a distance between each two vertices $i$ and $j$ of $G$ , denoted by $d(i,j)$ , as the smallest length of the walks between $i$ and $j$ . Therefore two vertices are adjacent if and only if the distance between them is one. The distance matrix of a connected graph $G$ , denoted by $\mathrm{Dist}(G)$ , is a square symmetric matrix whose element $(i,j)$ is $d(i,j)$ . The eccentricity of a vertex $i$ in $G$ , denoted by $e(i)$ , is the maximum of its distances to other vertices. Vertices whose eccentricity is one are those adjacent to all the vertices of the graph. Obviously, this is infrequent in the design of houses. Again, this gives three graph invariants: the maximum eccentricity $e_{\max }$ , the minimum eccentricity $e_{\min }$ and the eccentricity sequence. The minimum eccentricity is called the radius of the graph and the maximum eccentricity the diameter of the graph. Note that $e_{\max }$ is the maximum value of the distance function. It can be proved that the diameter and radius of a graph always satisfy the inequality $e_{\min }\le e_{\max }\le 2e_{\min }$ . Let us show the eccentricity sequence with the graph $G$ associated to a house in Nava del Rey.

Figure 5: Graph $G$ , its distance matrix and its eccentricity sequence.

The concept of eccentricity allows us to define subsets of interest in the vertex set of a graph. The center and the perimeter are the sets of vertices of minimum and maximum eccentricities, respectively. Similarly, the perimeter ring corresponding to $k$ is the set of vertices of eccentricity $k$ . These vertex sets stratify or arrange all the rooms of a house in terms of distances. The center of the graph associated to a dwelling not necessarily means the geometric center of the ground plan, or in Mechanics “the center of mass” or the “gravity center”. The reason for this, is because of the direct connections between rooms, and not their sizes and localization. Because graphs with equal radius than diameter are infrequent in architecture, we are studying the sharing out of eccentricities with descriptive statistical measures.

Figure 6: Graph $G$ , its center, its perimeter and its perimeter rings.

2. Descriptive measures applied to the degree and eccentricity sequences

We have two sequences, the degree and eccentricity sequences, associated to each graph. As previously stated, it is infrequent in the design of houses that these sequences are constant. Hence, we study the sharing out of degrees and eccentricities with descriptive statistical measures. We represent the information, as it is custom, by frequency tables.

As it is well known, in order to sum up the statistical data, the mean measures the central tendency of the statistics and the standard deviation measures their variability. Another very usual dispersion measure, with the advantage of being adimensional, is the coefficient of variation. Note that when statistical data are constant, both, the standard deviation and the coefficient of variation are zero.

Let us go back to the graph $G$ associated to a house in Nava del Rey that was used in the previous section.

Figure 7: Descriptive statistical measures and frequency tables for the degree and eccentricity sequences of graph $G$ .

The graph considered has three levels of degrees with a big gap between degrees two and seven. The vertices with lowest degree correspond to spaces that require more privacy, bedrooms and dining room; or because of noises or smells, or are more isolated, the garret stairs. The vertices whose degree is two correspond to the main spaces (hall, rooms, drawing room, kitchen and courtyard) and to the street that has direct connection with the house through the hall and through the courtyard. Notice that the spaces with two direct connections are almost the $54\%$ of the vertex set. There is only one vertex with the maximum degree, which corresponds to the circulation space, the passage.

The central space, in terms of distances, is the passage. This fact is revealed by the lowest eccentricity of vertex 3. We also observe three levels of eccentricity without gaps. The lowest eccentricity, that is the radius of the graph, corresponds to the central space, which is a circulation space. The medium eccentricity corresponds to the main spaces and to the garret stairs, and they are almost the $54\%$ of the vertex set. The highest eccentricity, that is the diameter of the graph, corresponds to spaces that require more privacy, and to the street.

In this example, the center is formed by the vertex of highest degree of the graph; but not always is like this, see [1]. Note also that terminal vertices do not require necessarily being at the perimeter, and vice versa, that is vertices in the perimeter do not require necessarily to be terminal vertices.

Note that the degree sequence mean is two, but the graph is not regular because the standard deviation is $1.51\ne 0$. If we look at the coefficient of variation of the degree sequence we have that this sequence has a dispersion of $75.8\%$ with respect to its mean. The central tendency of the eccentricity sequence is 3.31 and its dispersion is $18.3\%$ with respect to its mean. Therefore, the eccentricity sequence is much more homogeneous than the degree sequence.

References

[1] M. F. Blanco and M. Pisonero, Spanish Popular Architecture and Graphs, Proceedings of Mathematics & Design 2001, pp. 24-38. 2001.

[2] M. F. Blanco and M. Pisonero, An application of graphs in architecture, Symmetry: Art and Science, Vol. 1, pp. 30-33. 2001.

[3] L. Feduchi, Itinerarios de Arquitectura popular española, Blume, España. Five volumes: vol. 1 1974, vol. 2 1975, vol. 3 1976, vol. 4 1978 and vol. 5 1984.

[4] J. Gross and J. Yellen, Graph Theory and its Applications, CRC Press, USA 1999.

[5] P. Pellegrino, D. Coray et al., arquitectura e informática, Gustavo Gili, GG Básicos, España 1999.

.