Decision 1

Description

An flashcard overview of the AQA Decision Maths 1 topics
Lucy Denver
Flashcards by Lucy Denver, updated more than 1 year ago
Lucy Denver
Created by Lucy Denver over 10 years ago
137
10

Resource summary

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
Show full summary Hide full summary

Similar

TYPES OF DATA
Elliot O'Leary
FREQUENCY TABLES: MODE, MEDIAN AND MEAN
Elliot O'Leary
HISTOGRAMS
Elliot O'Leary
CUMULATIVE FREQUENCY DIAGRAMS
Elliot O'Leary
Using GoConqr to study Maths
Sarah Egan
STEM AND LEAF DIAGRAMS
Elliot O'Leary
Maths C4 Trig formulae (OCR MEI)
Zacchaeus Snape
Geometry Theorems
PatrickNoonan
Biology AQA 3.2.5 Mitosis
evie.daines
Enzymes and Respiration
I Turner
Fractions and percentages
Bob Read