A 
B 
C 
D 
E 
F 

A 
0 
1 
0 
2 
0 
0 
B 
1 
0 
1 
0 
0 
0 
C 
0 
1 
0 
1 
0 
1 
D 
2 
0 
1 
0 
1 
1 
E 
0 
0 
0 
1 
1 
1 
F 
0 
0 
1 
1 
1 
0 
1. Identify a Hamiltonian cycle in the graph
2. Redraw the graph so that the Hamiltonian cycle forms a regular polygon and all edges are drawn as straight lines in the polygon
3. Choose any edge AB and decide this will stay inside the polygon
4. Consider any edges that cross AB
(a) if it is possible to move all these outside without producing crossings, go to step 5
(b) if it is not possible then the graph is non planar
5. Consider each remaining crossing inside and see if any edge may be moved outside to remove it, without creating a crossing inside
6. Stop when all crossings inside have been considered
(a) if there are no crossings inside or outside then the graph is planar
(b) if there is a crossing inside that cannot be removed then the graph is nonplanar
Example: Applying the algorithm to the graph below
Results in the Hamiltonian path ABCD below
The edge BD can stay inside the polygon. AC can move outside the polygon and no arcs cross so the graph is planar.
The graph below is not planar. The arcs BE and BD can be moved outside the polygon but then the arc CE still crosses the arc AC and cannot be moved outside without crossing one of the newly outside arcs BE or BD.
]]>To find the lower bound, sum the numbers to be packed and divide this total by the size of the bin. The lower bound is the least integer greater than or equal to the result.
Example
Pack the following items in bins of size 20
8 7 14 9 6 9 5 15 6 7 8
The sum is 94
94 divided by 20 is 4.7
So the lower bound is 5 and we need at least 5 bins
FIRSTFIT ALGORITHM
Take the items in the order given and place each item in the first available bin that can take it, starting from Bin 1 each time.
Bin 1 8 7 5
Bin 2 14 6
Bin 3 9 9
Bin 4 15
Bin 5 6 7
Bin 6 8
]]>A complete graph is such that every pair of vertices must be connected by a single edge.
The above diagram is of a complete graph with 6 vertices.
We can to find out the total number of edges in this graph.
We could list all possible edges in terms of the vertices they connect.:
AB, AC, AD, AE, AF
BC, BD, BE, BF
CD, CE, CF
DE, DF
EF
Note that we include AB but not BA as this would be counting the same edge twice.
There are 5+4+3+2+1=15 edges in the above graph.
Of course, with a set that has many more than 6 elements, you probably wouldn’t want to list all possible pairs. Thankfully there is another, easier way to work out the number of edges in a complete graph, using binomial coefficients. We want the number of ways we can pick two elements from a set of n.
By using either the formula above, or by counting pairs, we see that the total number of possible pairs in the set is 15. This is the same as the total number of edges in the complete graph for that set.
]]>Example: A factory produces two cars, A and B. Each A car requires 3 hours of labour and each B car requires 5 hours. There are 480 hours of labour available.
If the number of A cars produced is a, thenhours of labour are required to produce them.
If the number of B cars produced is b, thenhours of labour are required to produce them.
The total number of hours of labour required to producecars of type A andcars of type B isThe total number of hours available is 480, so we can write
Example: A ferry is to carry a school party on a trip. The ferry can accommodate 500. It is required that the number of children can be at most ten times the number of adults, and that there be at least ten children for every adult.
If the number of children isand the number of adults isthen since the ferry can accommodate 500, we must have
'The number of children can be at most ten times the number of adults' can be rewritten as the ten times the number of adults is greater than or equal to the number of children, allowing us to write
'There must be at least four children for every adult' can be rewritten as the number of children is at least four times the number of adults, allowing us to write
Example: Mean and women are to be picked as candidates for election. The number of female candidates is to be greater than one quarter of the number of candidates, but no more than three fifths.
If the number of female candidates isand the number of male candidates isthen the number of candidates is'The number is female candidates is greater than one quarter the number of candidates' becomes
and 'no more than three fifths' becomes
]]>Dijkstra’s algorithm requires that each node in the network be assigned values (labels). The labels are assigned in order of distance from the starting point, with the labels assigned as we work our way through the network. There is a working label and a permanent label, as well as an ordering label. The smallest working label ateach iteration will become permanent.
The steps of Dijkstra’s algorithm are:
Give the start point the permanent label of 0.
Any vertex directly connected to the last vertex given a permanent label is assigned a working value equal to the weight of the connecting edge added to the permanent value of the node you are coming from. If it already has a working value replace it only if the new working value is lower.
Select the minimum current working value in the network and make it the permanent value for that node.
If the destination node has a permanent label go to step 5, otherwise go to step 2.
Connect the destination to the start, working backwards. Select any edge for which the difference between the permanent labels at each end is equal to the weight of the edge.
In this example we will consider the network in the diagram below. We would like to find the shortest path from node A to node F.
It is a good idea to use a system for keeping track of the current working labels and the ordering and permanent labels of each of thenodes in the network. A small grid is drawn near each of the nodes, working labels are written in the lower box, ordering labels in the upper right box.
Node A is labelled 0. The distance from A to A is 0. The closest to A is B, distance 4 from A, so B is labelled 1.
C and D are directly connected to B. The working value is of D is 4+6=10 and the working calue of C is 4+9=13. A lesser distance 5 from A exists for C, and this becomes the permanent value. Node C has label 2.
E and G are directly connected to C. The closest to C is E, distance 6 from A. E is labelled 3.
E is connected to F.
By inspection all the distances are minimised and we can label the remaining nodes.
]]>In the table below C cannot start until A has finished and D cannot start until both A and B have finished.
Activity 
Preceding Activities 
A 
 
B 
 
C 
A 
D 
A, B 
We need to include a dummy to show D cannot start until B has finished. The dummy is shown below.
Sometimes we need two dummies – or even more – at a time, to show how activities depend on each other.
Activity 
Preceding Activities 
A 
 
B 
 
C 
A 
D 
B 
E 
A, B 
Dummies are also needed because of what may seem a technical reason. It is not allowed to have two activities between the same two nodes, as shown below.
This is because although two or more activities may depend on the same preceding activities, the finishing of each activity are separate events, so must end at separate nodes. This is only relevant at the terminal node of an activity network, where some of the last activities depend on the same events.
H and G are the last activities. Without the dummy both activities would link to same two nodes. Notice that the length of the dummy is 0, so it is usual to place the dummy between the activity of least duration – G above – and ther terminal node.
]]>In order to make the identification of earliest and latest times easier, they are often put into a pair of boxes. The left box will be the earliest time and the right box will be the latest time. When working out the earliest times for each event you must start at the first event and assign an earliest time of 0. Work through each event in turn. Add the duration of the activity to the earliest time of the start event to get the earliest time of the end event. If there is more than one way of arriving at the end event then take the largest value for the earliest time.
Once you have gone through the entire network assigning earliest times you can begin to work out the latest times. This is done by starting at the last event and working backwards though the network. To start the process let the latest time of the last event be equal to the earliest time of that event. By subtracting the duration of an activity from the event that it ends at you will be able to find the latest time for the start event for that activity. If there is more than one way to arrive at a start event then take the smallest value for the latest time.
By looking at the earliest and latest times for the last event you will see that they are not the same for all events – some events have slack like B, which may start any time between 2 and 3 without delaying the whole project.
]]>A network containing odd arcs is non – Eulerian because each node must be entered and exited from separate arcs, so that the number of arcs connected to a node is twice the number of exits or entrances to that arc in traversing the network.
If a network is non Eulerian, we can modify it so that it becomes Eulerian by simply replicating each arc. Each node then becomes even and the network becomes Eulerian.
An attempt to construct an Eulerian path for the network on the left may start DCABCD. The path AD has not been traversed, and if it is there is no way to return to D without travelling over at least one path at least one, since every path has been traversed.
The network on the right has Eulerian path DCABCABCDAD.
]]>A property of Eulerian graphs is that they can be completely traversed, returning to the start point without following any edge more than once or lifting pen from paper.
Note that an Eulerian graph may not be simple – so that some of the above arcs cross each other.
An Eulerian graph may have no odd vertices.
Proof
Suppose Q is an odd vertex.
We can divide the arc connecting Q to the rest of the graphs into entry arcs to Q and exit arcs from Q, and match each entry arc with a unique and distinct exit arc, else some arc would be traversed twice.
Since Q is a vertex of odd degree, the must be an arc left over. If this is an entry arc, then there is no exit arc that would not be otherwise traversed since every entry arc is associated with an exit arc. If this is an exit arc, then there is no entry arc that would not be otherwise traversed since every exit arc is associated with an entry arc.
]]>