Graph Theory Lessons
Lesson 23:
Weighted Graphs,
Shortest Paths and Minimal Spanning Trees
Recall that in the adjacency matrix we have a 1 in position i,j if vertex
i is adjacent to vertex j. We
now want to introduce the idea of a weighted graph. This is a graph in which each edge has a weight
(for
instance if the vertices are cities the weight of an edge from vertex i to vertex
j could be the cost of moving materials from vertex i to j. ) In
the program if you look under the menu item
Picture and Weights you will have the option On and Off. Turn
the weights option on and you will notice that all the edges in your graph have a weight of one. This is
the default. When
the weights option is turned on you can draw and erase edges as before (using the right mouse
button) but this time you are also asked the weight of the edge. Try editing a graph to get a feel for this.
Drawing in the weights is tedious so in the program there is an option to assign
weights arbitrarily to the edges. The Assign Weights option will randomly assign
weights between 1 and 100 to the edges. This is a quick way to produce weighted graphs that we can
study. The weights will be in brown and the vertices will be in various
colors. If it gets difficult to read the numbers it may help to make the graph large (under Picture, Size,
Full Size). Also by moving the vertices a little you might get a better picture.
In the program check out the Shortest Path and the Minimal Spanning Tree options. We shall
discuss them in class.
Fig. 41, A weighted graph with the minimal spanning tree in blue.
e-mail:
C. Mawata
© C. Mawata