Flashcards
Decision 1
Flashcards do conjunto (31)
- 1Simple GraphsHave no loops or multiple edges
- 2Dijkstra's AlgorithmLabel the start 0 and box
Add temporary labels to vertices connected
Choose the smallest number and box
Repeat until all vertices are boxed - 3Prim's AlgorithmChoose smallest edge from start vertex
Choose next smallest edge from either vertex
Repeat until all vertices are connected - 4Prim's MatrixDelete 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 - 5Kruskal's AlgorithmChoose the smallest edge
Choose the next smallest edge, not creating any cycles
Repeat until all vertices are connected - 6Maximum degree of a vertex of a Simple Connected Graphn-1
- 7Minimum degree of a vertex of a Simple Connected Graph1
- 8Maximum edges of a Simple Connected Graph0.5n (n-1) edges
- 9Minimum edges of a Simple Connected Graphn-1 edges
- 10Hamiltonian CycleA cycle that visits every vertex in a network
- 11CycleA closed path or route that does not repeat any vertices and finishes where it started
- 12Complete GraphIf there is an edge connecting every possible pair of vertices
- 13Semi Eulerian GraphA graph with two odd vertices which is traversible, when starting at one odd vertex and finishing at the other
- 14Eulerian GraphA traversible graph with only even vertices where it is possible to start and finish at the same vertex
- 15TraversibleA path over all edges of a graph without repeating any edge
- 16Connected GraphsWhen it is possible to travel from one vertex to any other
- 17PathA trail where none of the edges are repeated
- 18TrailWalk where none of the edges are repeated
- 19WalkSequence of edges where the end vertex of one edge is the start vertex of the next
- 20Explain Upper BoundsA tour that exists but may be improved upon
- 21Explain Lower BoundsA tour cannot be any smaller than this but it may not exist as an actual tour
- 22Quick SortUnderline 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 - 23Shell SortSplit 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 - 24Shuttle SortCompare 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 - 25Bubble SortCompare adjacent and swap if needed
C= n-1
S= Look diagonally - 26Finding Lower boundsDelete vertex told to
Use Prim's on the remainder
Add on the two shortest edges from the deleted vertex - 27Finding Upper Bounds NEAREST NEIGHBOUR ALGORITHMChoose the smallest edge from the start vertex which has not already been visited
Repeat, visiting all vertices and join back to the start - 28Travelling SalesmanChoose the lowest upper bound and the highest lower bound
- 29Chinese PostmanFind the possible pairings of odd vertices
Find the smallest pairing and repeat these edges
Total the overall distance and paired egdes - 30Drawing a Profit LineConsider coefficients of x and y
Make p a number divisible by x and y
Find x and y and plot - 31Edges in a minimum spanning treen-1 edges
Informações
- Descrição
- An flashcard overview of the AQA Decision Maths 1 topics
- Criado por
- Lucy Denver
- Visualizações
- 178
- Tags
- Avaliação