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*G*and_{1}*G*such that every edge in the graph_{2}*G*connects a vertex in*G*only to a vertex in_{1 }*G*, it is called a_{2}*bipartite graph*. If every vertex in*G*is connected to every vertex in_{1}*G*, then_{2}*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*=*v*_{0}*e*_{1}*v*_{1}...*v*_{k}*e*_{k}*v*_{k+1}, with*v*_{0}=*u*and*v*_{k}_{+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.

## No comments:

## Post a Comment