lt Graph Theory Lesson 46: Weighted Graphs, Shortest Paths

image
Graph Theory Lessons

rule

previous index next Lesson 46: Weighted Graphs, Shortest Paths

Recall that in the adjacency matrix of a graph we have a 1 in position i,j if vertex i is adjacent to vertex j. This allows us to express whether two vertices are related or not. However, we sometimes want to say more. Suppose, for example the vertices represent cities and we have an edge between two vertices if we can get an airline flight from one city to the other. We might want to include more information like how long the flight takes. This brings us to the idea of a weighted graph. This is a graph in which each edge is assigned a number, called a weight.

In the Petersen program if you look under the menu item Mouse | Add/Delete Edge you will have the option Weighted Edge. 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. You can also draw directed weighted edges by choosing the Directed Weighted Edge option.

Drawing in the weights is tedious so in the program there is an option to assign weights arbitrarily to the edges. The Operations | 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.

Another way to add information to a graph is by labeling the vertices so that the labels include that information rather than just 1, 2, 3, ... or a, b, c, .... We would call such a graph a labeled graph.

Once we have a weighted graph we can ask a lot of questions. For example we might want to know which path from a vertex v to another vertex w has the least weight. The weight of a path will be the sum of the weights of the edges in the path. Since we often think of the weights as representing distance we call this the shortest path.

Java Web Start Activity:
There are quite a few algorithms for finding the shortest path between two vertices. This Java Web Start activity demonstrates a famous one is by the Dutch mathematician, Edsger Dijkstra which uses graph labeling. In the application you can draw a graph in the left pane and use the "weight +" and "weight -" to indicate if you want to increase or decrease the weight of an edge. You then drag the mouse from one vertex to another to adjust the weight of the edge between them. When you click the "Start/End" button, the next two vertices you click on will be the start and end of the path you want to find. The shortest path will be displayed in blue with the start vertex in green and the end vertex in red. At this point you can click on the "Step" button to get a step by step demonstration of Dijkstra's algorithm.

Java Web Start Application 46.1: Dijkstra's shortest path algorithm

A vertex v in a connected graph G has eccentricity e if the maximum of the lengths of the shortest paths to the other vertices of G is e.

Let G be a connected graph. The minimum of the eccentricities of the vertices of G is called the radius of G. The maximum of the eccentricities of the vertices of G is the diameter of G.

Let G have radius r and diameter d. The vertices of G that have eccentricity r are said to be in the center of the graph. The vertices of G that have eccentricity d are said to be in the periphery of the graph.

Java Web Start Activity:
The Java Web Start activity below will help you understand the definitions. In the application you can draw a graph in the left pane and the eccentricities of the vertices will be displayed on the right. By clicking on a row you will get the application to display the longest of the shortest paths from the chosen vertex to another vertex of the graph.

Java Web Start Application 46.2: Eccentricities of vertices

Questions:
Use the Petersen program to answer the following questions. You can get information on the eccentricity of the vertices of a graph by using the menu item Properties | Eccentricity. We shall assume that all edges have weight 1.
  1. Prove that a connected graph G with more than one vertex is a complete graph is and only if it has diameter 1.
  2. Prove that if a graph has radius r and diameter d then r ≤ d ≤ 2r.
  3. Give two examples of each of these:
    • Graphs where the radius r and diameter d satisfy d = r.
    • Graphs where the radius r and diameter d satisfy d = 2r.
    • Graphs where the radius r and diameter d satisfy r < d < 2r.
  4. A graph G on five vertices has adjacency matrix A. You are given the first few powers of A.
    A
    01100
    10100
    11001
    00001
    00110
    A2
    21101
    12101
    11310
    00110
    11002
    A3
    23411
    32411
    44204
    11002
    11421
    A4
    76 615
    67 615
    661242
    11 420
    55 206
    Find the radius and diameter of the graph.

Answers


© C. Mawata