948234
Description
Flashcards by Lucy Denver, updated more than 1 year ago
|
|
Created by Lucy Denver
almost 10 years ago
|
|
| Question | Answer |
| Simple Graphs | Have no loops or multiple edges |
| Dijkstra's Algorithm | Label the start 0 and box Add temporary labels to vertices connected Choose the smallest number and box Repeat until all vertices are boxed |
| Prim's Algorithm | Choose smallest edge from start vertex Choose next smallest edge from either vertex Repeat until all vertices are connected |
| Prim's Matrix | Delete the row of the start vertex and number the column 1 Choose the smallest in this column and number the next column 2, deleting the row Repeat until all vertices are connected |
| Kruskal's Algorithm | Choose the smallest edge Choose the next smallest edge, not creating any cycles Repeat until all vertices are connected |
| Maximum degree of a vertex of a Simple Connected Graph | n-1 |
| Minimum degree of a vertex of a Simple Connected Graph | 1 |
| Maximum edges of a Simple Connected Graph | 0.5n (n-1) edges |
| Minimum edges of a Simple Connected Graph | n-1 edges |
| Hamiltonian Cycle | A cycle that visits every vertex in a network |
| Cycle | A closed path or route that does not repeat any vertices and finishes where it started |
| Complete Graph | If there is an edge connecting every possible pair of vertices |
| Semi Eulerian Graph | A graph with two odd vertices which is traversible, when starting at one odd vertex and finishing at the other |
| Eulerian Graph | A traversible graph with only even vertices where it is possible to start and finish at the same vertex |
| Traversible | A path over all edges of a graph without repeating any edge |
| Connected Graphs | When it is possible to travel from one vertex to any other |
| Path | A trail where none of the edges are repeated |
| Trail | Walk where none of the edges are repeated |
| Walk | Sequence of edges where the end vertex of one edge is the start vertex of the next |
| Explain Upper Bounds | A tour that exists but may be improved upon |
| Explain Lower Bounds | A tour cannot be any smaller than this but it may not exist as an actual tour |
| Quick Sort | Underline the first in each list Write down everything smaller than this pivot in the order that it appears Box the pivot C= No of ____ or boxed S= No of nos that slide to the left of the pivot |
| Shell Sort | Split into (n/2) sublists Compare adjacent numbers and swap if needed / sublists by 2 each time and repeat until in order Only show comparisons and swaps for the first pass |
| Shuttle Sort | Compare adjacent numbers inside the bracket and swap if needed Add the next number into the bracket and repeat S= Diagonally New no at start: C=S No new no at start: C=S+1 |
| Bubble Sort | Compare adjacent and swap if needed C= n-1 S= Look diagonally |
| Finding Lower bounds | Delete vertex told to Use Prim's on the remainder Add on the two shortest edges from the deleted vertex |
| Finding Upper Bounds NEAREST NEIGHBOUR ALGORITHM | Choose the smallest edge from the start vertex which has not already been visited Repeat, visiting all vertices and join back to the start |
| Travelling Salesman | Choose the lowest upper bound and the highest lower bound |
| Chinese Postman | Find the possible pairings of odd vertices Find the smallest pairing and repeat these edges Total the overall distance and paired egdes |
| Drawing a Profit Line | Consider coefficients of x and y Make p a number divisible by x and y Find x and y and plot |
| Edges in a minimum spanning tree | n-1 edges |
Want to create your own Flashcards for free with GoConqr? Learn more.