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.
No comments:
Post a Comment