students book Flashcards
Kruskal’s algorithm - how does it work?
1) sort all the arcs into ascending order
2) Select the arc of least weight
3) If the next one forms a cycle reject it, if not add it to the spanning tree
4) Repeat until all vertices are connected
Binary search - how does it work?
1)To an ordered list, select the midpoint - given by the formula
0.5 (n+1) and round up - that’s the first pivot
2) The search is complete when the first pivot is the item we are locating, if not look at the first or second half of the list that most likely contains the item.
3) if the item is not yet located, use a second pivot and so on
4) if the item is not found then the item is missing from the list
Prim’s algorithm
1) choose a vertex to start the tree ( usually already known)
2)Select an arc of least weight that joins a vertex already in the tree. Choose any if there is a choice between arcs of equal weight
3) repeat until all vertices are connected
4) list the arcs in order they have been selected
Quick sort algorithm
1) choose the item at the midpoint of the list aka the pivot
2) write down the items that are less on one side and those that are bigger on the other, remember to write them in the same order they are given.
3) write down the 2nd and 3rd pivots of the two sublists.
4) add other pivots to each sublist until the list is sorted
The number of pivots double at each pass
Bubble sort
1) start at the beginning and work from the e left to the right comparing adjacent items. If they are in order, leave them. If not, swap them. After the first pass, the last item is in it’s final position
2) Continue with next passes until the list is sorted, when no swaps are made.
Eulerian graph/circuit
graph which contains a trail that includes every edge and starts and ends at the same vertex - called the Eulerian circuit.
Any connected graph whose vertices have even valencies is Eulerian
Semi-Eulerian graph
graph containing a trail which starts and finishes at different vertices. Usually those two with an odd valency.
Any connected graph with exactly 2 odd vertices are Semi-Eulerian
Nearest neighbour algorithm
Works only on a least distance matrix between each node, used in the travelling salesman problem - does not find an optimal solution
1) choose any vertex to start the path
2) Select an arc of least weight which joins a new vertex to the last vertex added ONLY
3) Repeat until all vertices are added
Route inspection algorithm
1) identify any vertices with odd degrees
2) consider all possible complete pairings of these vertices, select those with the least sum
3) add a repeat of the arcs indicated by this pairing to the network
Travelling salesman problem
using a min spanning tree method to find an upper bound for the practical TSP:
1) find the minimum spanning tree, enter Prim or Kruskal algorithm
2) double the minimum connector such that the cycle is completed
3) try to find shortcuts on the way back ( the non-included arcs might be useful)
walk
a route through a graph along the edges from one arc to another
path
a walk in which no vertex is visited more than once
trail
a walk in which no edge in visited more than once
cycle
a walk in which the end vertex and start vertex are the same and no one is visited more than once
hamiltonian cycle
cycle that includes every vertex
