Pages

Saturday, October 19, 2013

102. Graphs and Networks


In physics one can, in principle, work out the properties of a noncomplex system in terms of the structure of the system and the distance-dependent interactions among its constituents. For instance, one can understand the emergence of macroscopic magnetism in a crystal in terms of the distance-dependent interactions among the spins. But there are a large number of complex systems in which the physical distances among the constituents are largely irrelevant, and in which there is ambiguity about whether or not there is interaction between a chosen pair of constituents. Social systems are one such example, as are ecological systems, neurons in a brain, investors in a stock market, and participants in the Internet. Network theory and statistical mechanics provide powerful tools for dealing with such systems.

I introduced networks briefly in Part 48. The experts make a distinction between networks and graphs although, sometimes, the two terms do tend be used synonymously in a loose sort of way.

A graph is a collection of points (called nodes or vertices) together with a collection of lines (called edges or links) that connect certain pairs of these points. A directed graph is a graph in which the edges are ordered pairs of vertices; that is, every edge in a directed graph has a direction.

A network is a directed graph in which every edge is given a label. The term 'network' is used in several different contexts, and can have different, context-dependent meanings. Electrical networks, social networks, communication networks, and neural networks are some examples.

Networks with a large number of nodes and edges generally exhibit complex behaviour, and are called complex networks (Albert and Barabási 2002). Complex systems embody organizing principles encoded in the topology of the underlying network.



A graph G is a nonempty finite set N(G) together with a finite set E(G) of distinct unordered pairs of elements of N(G). Each element in N(G) is called a node or a vertex, and each element in E(G) is called an edge.

The order |N| of G is the number of elements in N, and the size |E| of G is the number of elements in E.

In practical applications of graph theory, it is often necessary to assign a weight to each edge. For example, if the vertices in a graph represent cities, and the edges the roads between the cities, then a weight proportional to the length of a road can be assigned to the edge representing that road.

Consider two vertices u and v of G which are joined by an edge e. The edge e = {u, v} is often represented as just uv (or u-v). We say that u is adjacent with v. And e is said to be incident to u and v. Two edges incident to a common vertex are said to be adjacent with each other.

The neighbourhood n(u) of a vertex u is the set of vertices in the graph that are adjacent with u. The number of vertices in the set n(u) is called the degree of u. It is denoted by d(u), and is the number of edges of the graph incident to u.

The figure below illustrates these definitions. For the graph G shown in it, N = {u, v, w, x, y}; E = {ux, uy, vy, xy}; order |N| = 5; and size |E| = 4. The degrees of the vertices are: d(u) = d(x) = 2, d(v) = 1, d(y) = 3, d(w) = 0. The vertex w is said to be an isolated vertex.

(a) Graph G. (b) Subgraph G - y. (c) Spanning graph G - ux . (d) Spanning supergraph G + vw. (e) Graph H isomorphic to the graph G. (f) Multigraph. (g) Directed graph. (h) Königsberg graph, depicting the Königsberg-bridges problem posed and solved by Euler (see below).

A graph H is a subgraph of a graph G if N(H) is a subset of N(G) and E(H) is a subset of E(G). G is called a supergraph of H. In Fig. (a) above, if we delete the vertex y and also all the edges adjacent with y, then we obtain the subgraph G-y shown in Fig. (b).

If H and G have the same set of vertices, then H is called a spanning subgraph of G. For example, Fig. (c) has the same set of vertices as Fig. (a), but the edge ux is missing; consequently, G-ux is a spanning subgraph of G.

Fig. (d) depicts a spanning supergraph of G. In it, the vertices are the same as for G, but an edge vw has been added. It is denoted by G+vw.

Two graphs G and H are said to be isomorphic if there is a one-to-one mapping from the vertices of one graph onto the vertices of the other graph such that the edges are preserved. For example, the graph shown in Fig. (e) is isomorphic to that in Fig. (a).

A graph or subgraph in which every pair of vertices is adjacent is called a complete graph or subgraph. That is, each vertex of the graph or subgraph is connected to every other vertex of the graph or subgraph. If it is of order n, then each vertex in it is of degree (n-1), and its size is n(n-1)/2. A complete subgraph in a graph is said to constitute a cluster in the graph.

If the vertices of a graph G can be divided into two disjoint subsets G1 and G2 such that every edge in the graph G connects a vertex in G1 only to a vertex in G2, it is called a bipartite graph. If every vertex in G1 is connected to every vertex in G2, then G is a complete bipartite graph.

If all vertices of a graph have the same degree r, then it is called an r-regular graph, or regular graph.

A random graph is one in which the edges are distributed randomly.

If a graph has multiple edges between two vertices, or if it has edges in the form of loops (e.g. vv), it is called a multigraph (Fig. (f)).

A walk W in a graph G from a vertex u to a distinct vertex v is a finite sequence of alternating vertices and edges (W = v0e1v1...vkekvk+1, with v0 = u and vk+1 = v) such that each edge in the sequence is incident to each of the two vertices on either side of it in the sequence. The length of the walk is the number k, i.e. the number of edges in it.

If all the edges in W are distinct, it is called a trail.

A trail in which all the vertices are distinct is called a path.

A walk, trail, or path is said to be closed if the initial and the final vertex are the same (u = v). A closed path with k ≥ 3 is called a cycle.

If there is a path between two vertices of a graph, then the vertices are said to be connected. If each pair of vertices in a graph is connected, then the graph is said to be connected. If only a subset of the vertices in a graph are connected, and if they are connected to a particular vertex, then this subset constitutes a connected subgraph (or a cluster).

A graph that is not a connected graph can be partitioned into maximal connected subgraphs called the components or clusters of the graph. The graph in Fig. (a) has two components: {u, v, x, y} and {w}.

We define the distance between any two vertices u and v of a graph as the length of the shortest path between them. It is denoted by d(u, v). If the edge connecting these two vertices has been assigned a weight w, the weighted distance is wd(u, v).

A tree is a connected graph that does not contain any cycles. It is readily argued that any connected graph has a spanning tree.

The maximal distance between any pair of nodes of a graph defines the diameter of the graph. A disconnected graph is one that is made of two or more isolated clusters. Strictly speaking, for such a graph the diameter is infinite, so a modified definition of diameter is used by defining it as the maximum diameter of its clusters.

The first paper in graph theory was published in 1836 by Euler (cf. Barabási 2002). Euler solved the famous Königsberg bridges problem in that paper. There were seven bridges in Königsberg over a river, which connected pairs of regions from among the four which we may denote by, say, A, B, C, D. The problem posed was whether it is possible to traverse the seven bridges without crossing any bridge twice. If we represent the tour regions as the vertices in a graph, and the bridges as the edges connecting pairs of vertices, we obtain the multigraph shown in Fig. (h) above. Euler established that the problem posed had an answer in the negative. In other words, he showed that the graph in Fig. (h) does not have a trail that uses all the edges in the graph.

 

An Eulerian trail of a graph is defined as a trail that uses all the edges of the graph. A graph that contains a closed Eulerian trail is called an Eulerian graph. Euler showed that there is no Eulerian trail in the graph shown in Fig. (h). For such a trail to exist, a graph must be a connected graph, and all its vertices (except possibly the first and the last vertices of the trail) must be of even degree.

Euler proved the theorem that a connected graph or multigraph G has a closed Eulerian trail if and only if each vertex has even degree, and that G has an open Eulerian trail if and only if precisely two of its vertices are of odd degree.

So much for graphs. I shall discuss networks of various types in the next few posts.