AQA D1 Theory 3.0 / 5 based on 1 rating ? MathematicsGraphs and transformationsASAQA Created by: maddieCreated on: 21-05-13 17:00 No. of possible pairings in a Chinese postman problem (n-1) x (n-3) x (n-5)... x 1 1 of 13 No. of hamiltonian cycles [(n-1)!]/2 2 of 13 Eulerian Graph A cycle can be found which travels every edge once only, starting and finishing at the same vertex (all vertices must be even)- Chinese Postman 3 of 13 Semi-eulerian A trail can be found which travels every edge one only, starting and finishing at different vertices (exactly 2 odd vertices) 4 of 13 Number of passes in shuttle sort n-1 5 of 13 Max number of passes in bubble sort n 6 of 13 Max no. of swaps/comparisons in bubble sort (n-1) + (n-2) + (n-3)... +1 OR n/2(n+1) (occurs when items are in reverse order) 7 of 13 No. of edges in a minimum spanning tree n-1 8 of 13 No. of edges in a complete graph n(n-1)/2 9 of 13 No. edges in a hamiltonian cycle n 10 of 13 Traversable A path can be found which travels across each edge once only 11 of 13 Hamiltonian cycle A cycle that goes through every vertex exactly once- Travelling Salesperson 12 of 13 Upper bound for travelling salesperson problem Nearest Neighbour Algorithm 13 of 13
Comments
No comments have yet been made