# D1 Definitions

### Description

Definitions for Decision 1 Edexcel Maths
Flashcards by Trish Kelly, updated more than 1 year ago
 Created by Trish Kelly almost 8 years ago
8
0

## Resource summary

 Question Answer Algorithm Set of precise instructions which if followed will solve a problem Bubble-sort algorithm To sort a list compare adjacent members of the list, moving from left to right, and switch them if they are in the wrong order. Continue until pass produces no change in list. Quick-sort alogorithm Select middle as pivot. Write all numbers smaller than pivot on left, bigger on right. Take middle of each 2 lists as pivot and repeat until only one number left. First-fit algorithm Taking the boxes in the order listed, place the next box to be packed in the first available bin. Repeat. First-fit decreasing algorithm Order list so it is decreasing. Then do first-fit algorithm Binary-search algorithm Applied to search an ordered list. Compare required item with middle. If required is before then reject bottom half, if after reject top half. Repeat until required item is found or no items left to check. Graph G Consists of a finite number of points (called vertices/nodes) connected by lines (edges/arcs) Path Finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once Cycle (or circuit) Closed path i.e the end vertex of the last edge is the start vertex of the first edge Hamiltonian cycle Cycle that passes through every vertex of the graph once and only once and returns to its start vertex Eulerian cycle Cycle that includes every edge of a graph exactly once Vertex set Set of all vertices of a graph Edge set Set of all edges of a graph Subgraph (of a graph) Subset of the vertices together with a subset of edges Connected (vertices) Two vertices are this if there is a path between them Connected (graph) A graph is this if all pairs of its vertices are connected Simple graph When there is no edge with the same vertex at each end i.e no loops, and not more than one edge connecting any pair of vertices Degree (or valency or order) The degree of a vertex is the number of edges connected to it Directed edges/digraph When the edges of a graph have a direction associated with them. Tree Connected graph with no cycles Spanning tree Of a graph G, is a subgraph that includes all the vertices of G and is also a tree Bipartite graph Consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set Kr,s Graph When in a graph there are r vertices in X and s vertices in Y and every vertex in X is joined to every vertex in Y. Minimum spanning tree/minimum connector A spanning tree of a connected and undirected graph such that the total length of its edges is as small as possible Kruskal's algorithm Builds a minimum spanning tree by adding one edge at a time to a subgraph. At each stage the edge of smallest weight is chosen provided that it does not create a cycle with edges already chosen. Prim's algorithm Builds minimum spanning tree by adding on vertex at a time to a connected subgraph. The new vertex to be added is the one which is nearest to any vertex already in the subgraph Dijkstra's algorithm Obtains the shortest route from the initial vertex to any other vertex in a network. At each stage a fresh vertex is assigned a final which gives the shorted distance from the initial vertex to that vertex

### Similar

All AS Maths Equations/Calculations and Questions
Core 2 AS level maths formulae OCR
AS level Maths Equations to Remember
Ordinary Differential Equations
HISTOGRAMS
Maths C4 Trig formulae (OCR MEI)
TYPES OF DATA
FREQUENCY TABLES: MODE, MEDIAN AND MEAN
Using GoConqr to study Maths
The Weimar Republic, 1919-1929
A Level Chemistry Unit 1 - Organic Chemistry