Page 682 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 661

Hence, by the inductive hypothesis, the graph K has a complete matching. Combining this

complete matching with the complete matching from W to W , we obtain a complete matching
1 2
from W 1 to W 2 .
We have shown that in both cases there is a complete matching from W 1 to W 2 . This
completes the inductive step and completes the proof.

We have used strong induction to prove Hall’s marriage theorem. Although our proof is
elegant, it does have some drawbacks. In particular, we cannot construct an algorithm based on
this proof that finds a complete matching in a bipartite graph. For a constructive proof that can
be used as the basis of an algorithm, see [Gi85].

Some Applications of Special Types of Graphs

We conclude this section by introducing some additional graph models that involve the special
types of graph we have discussed in this section.
EXAMPLE 16 Local Area Networks The various computers in a building, such as minicomputers and per-
sonal computers, as well as peripheral devices such as printers and plotters, can be connected
using a local area network. Some of these networks are based on a star topology, where all
devices are connected to a central control device. A local area network can be represented using
a complete bipartite graph K 1,n , as shown in Figure 11(a). Messages are sent from device to
device through the central control device.

(a) (b) (c)

FIGURE 11 Star, Ring, and Hybrid Topologies for Local Area Networks.

Other local area networks are based on a ring topology, where each device is connected to
exactly two others. Local area networks with a ring topology are modeled using n-cycles, C n ,
as shown in Figure 11(b). Messages are sent from device to device around the cycle until the
intended recipient of a message is reached.
Finally, some local area networks use a hybrid of these two topologies. Messages may be
sent around the ring, or through a central device. This redundancy makes the network more
reliable. Local area networks with this redundancy can be modeled using wheels W n , as shown
in Figure 11(c). ▲

EXAMPLE 17 Interconnection Networks for Parallel Computation For many years, computers executed
programs one operation at a time. Consequently, the algorithms written to solve problems were
designed to perform one step at a time; such algorithms are called serial. (Almost all algorithms
described in this book are serial.) However, many computationally intense problems, such as
weather simulations, medical imaging, and cryptanalysis, cannot be solved in a reasonable
amount of time using serial operations, even on a supercomputer. Furthermore, there is a physical
limit to how fast a computer can carry out basic operations, so there will always be problems
that cannot be solved in a reasonable length of time using serial operations.
Parallel processing, which uses computers made up of many separate processors, each
with its own memory, helps overcome the limitations of computers with a single processor.
Parallel algorithms, which break a problem into a number of subproblems that can be solved