4.4 Application of the connectivity.
If we have a graph in our mind as representing a communication network, the connectivity becomes the smallest number of communication stations whose breakdown would destroy communication in the system.
Two statements are plausible:
- The higher the connectivity and edge connectivity, the more reliable is the system.
- The higher the connectivity and edge connectivity, the more expensive is the system.
So, the tree network is cheap, but it is not very reliable. This leads to consider the following generalisation of the spanning tree problem.
The Reliable Communication Network Problem: Let k be given positive integer and let G be a weighted graph. Determine a minimum-weight k-connected spanning subgraph of G.
-
If then this problem reduces to the spanning tree
problem.
-
If then the problem is unsolved and is known to
be difficult.
- If G is a complete graph in which edge is assigned unit weight, then the problem has a simple solution.
For a weighted complete graph on n vertices in
which each edge is assigned unit weight, a minimum-weight k-connected
spanning subgraph is a k-connected graph on n vertices with as
few edges as possible. Let us denote by the least number of edges that a k-connected
graph on n vertices can have. (It is clear that
.)
From the Handshaking Lemma and the Whitney's Connectivity Theorem it follows immediately that
.
For given n
and k Harary gave a construction for
a graph which has exactly
edges and he proved that is
k-connected. The structure of his
construction depends on the parities of n and k, and it is as
follows:
Case 1. k is even. Let Then
is constructed as follows. It has vertices
and two vertices i and j
are joined if
(where addition is taken modulo n.)
Case 2. k odd, n even. Let . Then
constructed by first drawing
and then adding edges joining vertex i
to vertex
.
Case 3. k odd, n odd. Let . Then
is constructed by first drawing
then adding edges joining vertex 0 to
vertices
and
and vertex
.
Figure 4.3. Some example for the Harary's construction