Advanced High-School Mathematics

124 CHAPTER 2 Discrete Mathematics

2.2.3 Networks and spanning trees

In this subsection we consider a problem similar to TSP but different
in the sense that efficientandoptimal solutions are possible. The basic
idea is this: suppose, for example, that we have the weighted graph

• •

•

c 3

c 1 c 2

A B

C

We need for these three points to be “networked,” i.e., in communi-
cation with each other, but without any redundancy. In other words,
we don’t need all three of the edges in the above graph because ifA
is networked withB, andB is networked withCthen Ais networked
with C: there is a “transitivity” of networking. Therefore, the above
idealized networking problem would be optimized by discarding the re-
dundant (and most expensive) edge so that the sum of the remaining
edge weights becomes a minimum.

Let us flesh out the above with a somewhat more detailed problem.

Example 1. Assume that we have
citiesA, B, C, D, andE and that
they can be networked according to
the costs depicted in the weighted
graph to the right.

What we are looking for is a network which will result in the the cities
being interconnected but without any redundancy. Also, we are looking
to do this with the least possible cost. The first condition simply states
that we are looking for a “subgraph” of the above graph containing all
of the vertices but without having any cycles in it. Such is called a