The concept of drawing a graph to represent information has been used extensively in mathematics. These ideas have been used to plot the routes of the mailman, and of various delivery companies. These ideas are also extended to the airline industry. They have been used in determining routes between cities, and in providing a time line for doing various activities that enable the efficient disembarkation and unloading of baggage on an aircraft.
Just as model aircraft are used to represent the real thing, models in this section will be used as a representation of something else. The model or graph will be used to give us an idea of what reality is.
A graph is a finite set of points, called vertices, together with a finite set of curved or straight connecting lines called edges, each of which joins a pair of vertices. These vertices and edges satisfy the condition that no edge begins or ends at the same vertex. Graphs without edges are called null graphs.
(figure available in print form)
(a) null graph
(figure available in print form)
b) complete graph
(figure available in print form)
c) not a graph
The figure in c) is not a graph because it violates the condition that no end may join a vertex to itself. When a graph has two or more different edges joining the same pair of vertices, these edges are called multiple edges.
(figure available in print form)
The edge of a graph can be identified by using a letter to name it, and the vertices (endpoints) can also be named. The edge E can be named (X1 X2)
Graphs are important tools in representing a vast number of real world problems. Graphs that are used to represent the lay out of streets are called street networks. In this instance the edges of the graph can have a direction indicated by arrow. These graphs are called digraphs. A digraph is a finite, non empty set of points called vertices, together with some directed edges joining these points. These edges are subjected to one restriction. The initial and terminal vertices of a directed edge may not be the same.
(figure available in print form)
(figure available in print form)
(figure available in print form)
A. Graphs and Matrices: Matrices from Drawings
Matrices are presented as a means of storing information in which the position of the information is very important. The direct route matrix is used since it enables us to predict properties of more complicated networks without reproducing them.
The figure shows a network of roads
(figure available in print form)
A direct route is the journey which does not pass through another endpoint.
One way of describing a direct route linking endpoints is to use an arrow diagram.
(figure available in print form)
Another way of describing this is to use a table where zero means no direct route, 1 means 1 direct route, 2 means two direct route etc.
(figure available in print form)
The rectangular array of numbers from the table can be represented in a matrix:
(figure available in print form)
Instead of talking about endpoints or vertices and edges these ideas can be applied to real life situations. The vertices or endpoints can be referred to as towns or cities and the edges can be called routes or roads.
The diagram shows a network of roads between several towns with their direct routes.
(figure available in print form)
One way of showing the direct routes linking the towns is to draw the arrow diagram.
(figure available in print form)
(figure available in print form)
(figure available in print form)
Directed Maps: A map of a one way system is called a directed map because arrows are placed on the roads to show in which direction to go.
(figure available in print form)
(figure available in print form)
(figure available in print form)
The matrix of a directed map is different from the matrix of an undirected map since it is not symmetrical and it is also possible to have odd elements on the leading diagonals.
B. Finding the Shortest Path
A graph or network is defined by two sets of symbols, nodes and arcs. Nodes are the set of pints or vertices, arcs consists of an ordered pair of vertices and represents a possible direction of notion that may occur between vertices.
(figure available in print form)
Arcs can be considered as one way roads. For shortest path problems it will be assumed that each arc in the network has a length associated with it. The problem of finding the shortest path is the minimum length from one node to any other node in the network.
DIJKSTRA’S Algorithm:10 This algorithm for finding the shortest path between a pair of nodes requires that all the arcs in the network have non-negative arc length.
The algorithm uses this method:
-
1. Designate node one as the starting point.
-
2. Find the node closest to node one.
-
3. Find the second closest node to node one.
-
4. Find the third closest node to node one.
-
5. Continue until all the paths are used.
Let us use this method in the following example:
(figure available in print form)
The distances can be summarized in a table:
1. Determination of the second closest node to node 1.
|
|
The arc (1,2)
|
4
|
|
|
The shortest path from node 1
|
|
|
to node 3 + arc (3,5)
|
3 + 3 = 6
|
2. Determination of the third closest node to node 1
____
The shortest path from 1 to 3
|
|
+ arc (3,5)
|
3 + 3 = 6
|
|
|
Shortest path from 1 to 2
|
|
|
+ arc (2,5)
|
4 + 2 = 6
|
|
|
Shortest path from 1 to 2
|
|
|
+ arc (2,5)
|
4 + 3 = 7
|
3. Determination of the fourth closest node to node 1
____
Shortest path from 1 to 2
|
|
+ arc (2,4)
|
4 + 3 = 7
|
|
|
Shortest path from 1 to 5
|
|
|
+ arc (5,6)
|
6 + 2 = 8
|
4. Determination of the fifth shortest path from node 1
____
Shortest path from 1 to 4
|
|
+ arc(5,6)
|
7 + 2 = 9
|
|
|
Shortest path from 1 to 5
|
|
|
+ arc(5,6)
|
6 + 2 = 8
|
Summary of shortest path
|
Nodes
|
Closest Nodes
|
Path from Node 1 to
|
Length of
|
|
|
|
to node 1
|
the nth closet node
|
path
|
|
0
|
|
1
|
-
|
-
|
|
1
|
|
3
|
1 - 3
|
3
|
|
2
|
|
2
|
1 - 2
|
4
|
|
3
|
|
5
|
1 - 2 - 5 or 1-3-5
|
6
|
|
4
|
|
4
|
1 - 2 - 4
|
7
|
|
5
|
|
6
|
1-3-5-6 or 1-2-5-6
|
8
|
The shortest path from node 1 to node 6 is either 1-2-5-6 or 1-3-5-6 both have length 8.
The digraph can also be used to solve complicated problems. Consider this problem: We wish to minimize the time an aircraft spends at an airport. The component activities can be placed in a table:
|
A1
|
Disembark passengers
|
1/2 hr.
|
|
A2
|
Unload baggage
|
1 hr
|
|
A3
|
Clean the plane
|
1/2 hr
|
|
A4
|
Take on new passengers
|
1 hr.
|
|
A5
|
Load new baggage
|
1 hr.
|
We could simply sum all the numbers of hours but some of these tasks can be done simultaneously and some operations are independent of others. A good way to proceed is to draw a model called “The Activity Analysis Digraph.”
An Activity Analysis Digraph is constructed in the following way.
-
1. Represent each activity by a node A1, A2, . . . An with the time required for the activity.
-
2. Create two additional nodes each labeled with the number zero. One representing the job’s beginning and the other the job’s end.
-
3. Draw a directed edge from one activity to the next only if the first activity precedes the second.
Now that we have drawn a model, the problem is to determine the shortest time for the completion of the whole job. We can proceed as follows:
-
1. Denote time t measured from starting point B; t = 0
-
2. Rephrase the problem; given an Activity Analysis Digraph for a project. What will be the shortest time at which E, the end, can be completed?
-
3. Add the times for all activities on the path up to but not including E (There may be more than one path from B to E).
The critical path is the path of longest time from B to E. To determine the most efficient schedule in the problem is the critical path B, A2, A4, which has length of two hours and this gives the minimum time for the whole job to be completed.
To explain the activities A1 and A2 can both be started at time zero (Passengers can disembark and luggage be taken off at the same time).
The activity A3 cannot be started until all the passengers are taken off; the activity A4 cannot be started until A3 is completed but can be made to overlap with A5; we cannot arrive at E until both A4 and A5 are completed.
