P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38
28 Graph Essentials34643216221236821420102430v 1 v 6v 2v 7v 5 v 8v 3v 4v 9
Figure 2.12. Minimum Spanning Tree. Nodes represent cities and values assigned to
edges represent geographical distance between cities. Highlighted edges are roads that
are built in a way that minimizes their total length.can represent each city with a node and the distance between these
nodes using an edge between them labeled with the distance. This
graph-based view is shown in Figure2.12. In this graph, nodesv 1 ,
v 2 ,...,v 9 represent cities, and the values attached to edges represent
the distance between them. Note that edges only represent distances
(potential roads!), and roads may not exist between these cities. Due
to construction costs, the government needs to minimize the total
mileage of roads built and, at the same time, needs to guarantee that
there is a path (i.e., a set of roads) that connects every two cities.
The minimum spanning tree is a solution to this problem. The edges
in the MST represent roads that need to be built to connect all of
the cities at the minimum length possible. Figure 2.2 highlights the
minimum spanning tree.- Steiner Tree.The Steiner Tree problem is similar to the minimum
spanning tree problem. Given a weighted graphG(V,E,W) and a
TERMINAL subset of nodesV′⊆V(terminalnodes) , the Steiner tree problem
NODES aims to find a tree such that it spans all theV′nodes and the weight
of the tree is minimized. Note that the problem is different from the
MST problem because we do not need to span all nodes of the graph
V, but only a subset of the nodesV′. A Steiner tree example is shown
in Figure2.13. In this example,V′={v 2 ,v 4 ,v 7 }.
2.5.3 Complete Graphs
A complete graph is a graph where for a set of nodesV, all possible edges
exist in the graph. In other words, all pairs of nodes are connected with