Mind map
D1 Revision

Mind map: D1 revision: graphs, algorithms and linear programming
Map content
D1 Revision
Graphs and Networks
- The order of a node is the number of arcs that meet at that point
- Eulerian graphs: each node be of even order; uses every vertex in the graph
- a connected graph with a closed trail containing every arc exactly once
- these can be drawn without taking your pen off of the paper, with your pen ending at the same node it started at
- Semi-Eulerian Graphs: exactly two nodes of odd order; uses every vertex in the graph
- a connected graph which has a trail (crucially not closed) that contains every arc exactly once
- Connected graph: is one where a path (not necessarily direct) can be found from any two nodes
- Simple graph: A graph with no loops, no multiple edges and every vertex is connected
- In any graph there must be an even number of odd nodes
- The total of the orders of all the nodes in a graph = 2 x the number of acrs, and therefore is even
- A planar graph is a graph that can be redrawn so that no arcs cross-over
- Kruskal's algorithm
- 1) List the arcs in order of weight, smallest first
- 2) Choose the arc with the smallest weight
- 3) Choose the next arc of smallest weight which does not form a cycle
- 4) Repeat step 3 until all vertices have been included
- Prim's Algorithm
- 1) Select any node
- 2) Select the shortest arc connecting the tree to a new node
- 3) Incorporate that arc and the node into the tree
- 4) Repeat steps 2 & 3 until all nodes are connected
- Can also be done from a matrix
- Dijkstra's algorithm (the one with the boxes)
- 1) Give the start node a permanent label of 0
- 2) Give each node connected to start node a temporary label
- 3) Find the smallest temporary label and make it permanent
- 4) Update temporary labels for any node that can be directly reached from new node in tree
- 5) Repeat 3 & 4 until destination is reached
- Route Inspection (chinese postman)
- 1) Find all the nodes of odd order
- 2) For each pair of odd nodes find the shortest path that joins them
- 3) Pair up all the odd nodes to find the pairing with the shortest total distance connecting them
- 4) In the original network, duplicate the minimum weight paths from step 3
- Lower Bound
- 1) Choose a node as the special node
- 2) Find a minimum connector for the remaining network
- 3) Add in the weights of the two least weighted arcs from the deleted node
- Upper Bound
- The upper bound is any cycle
- Nearest Neighbour
- 1) Choose any node as a starting point
- 2) Find the next nearest node the the previously selected one
- 3) Repeat step 2 until all nodes have been selected
- 4) Join the last vertex to the first vertex via the shortest route
Algorithms
- Bin packing
- First fit decreasing
- Sort the items into decreasing order and then perform first fit algorithm
- First fit
- First fit; place the next item in the first available bin that can take it
- First fit decreasing
- Shuttle sort
- 1) Compare 1st & 2nd numbers in the list, swap if necessary
- 2) Compare 3rd & 2nd numbers, swap if necessary. If a swap is made compare the 2nd & 1st
- 3) Compare 4th & 3rd number, swap if necessary. If sway made, compare 3rd & 2nd etc
- Repeat until there are no swaps or you reach the beginning of the list
- Number of passes = length of original list - 1
- Number of swaps = number of comparisons - 1, unless number moves to the front of the list
- Bubble sort
- 1) If there is only 1 number in list, stop
- 2) Work your way from right to left,comparing adjacent numbers, swapping if necessary. (after first pass the number furthest right is in its correct position)
- 3) If swaps were necessary then repeat step 2, comparing one less number in each pass
- 4) Algorithm is complete when no swaps are necessary
- Can finish early if no swaps are required
- Bin packing
Linear Programming
Information
- Description
- Mind Map on D1 Revision, created by shnoz on 28/02/2015.
- Created by
- shnoz
- Views
- 4
- Rating
More on Graph and Network Algorithms