D1 terms

these are the terms for the first three chapters of edexcels D1 

Complete graph

A graph in which each of the n vertices is connected to 

every other vertex.

1 of 29


A closed path, i.e. the end vertex of the last edge is the start 

vertex of the first edge. (Same as a circuit.)

2 of 29


 A curved line connecting points (nodes or vertices) on a 


3 of 29

Bipartite graph

A graph consisting of two sets of vertices X and Y. The 

edges only join vertices in X to vertices in Y, not vertices 

within a set. (If there are r vertices in X and s vertices in Y

then this graph is Kr ,s.)

4 of 29


 The degree or valency of a vertex is the number of edges 

incident to it. A vertex is odd (even) if it has odd (even) 


5 of 29

Dijkstra’s algorithm

An algorithm that finds the shortest paths from a single 

source vertex to all other vertices in a directed graph.

6 of 29


 A line on a graph connecting two nodes

7 of 29

Even vertex (or node)

A vertex is even if it has even degree.

8 of 29

End node

 The last point in a network

9 of 29


A graph G consists of points (vertices or nodes) which are 

connected by lines (edges or arcs).

10 of 29

Kruskal’s (greedy) algorithm

An algorithm used to find the minimum spanning tree of a 

network. Uses a different method to Prim’s algorithm.  

11 of 29

Minimum connector

Same as a minimum spanning tree

12 of 29

Minimum spanning tree (MST)

 A spanning tree such that the total length of its arcs is as 

small as possible. (MST is sometimes called a minimum 


13 of 29


 A graph where each edge has a ‘weight’. (Also known as a 

weighted graph)

14 of 29


A point on a graph (same as a vertex)

15 of 29

Odd vertex (or node)

A vertex is odd if it has odd degree

16 of 29


A 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 then once

17 of 29

Prim’s algorithm

An algorithm used to find the minimum spanning tree of a 

network. Uses a different method to Kruskal’s algorithm.  

18 of 29

Spanning tree

A spanning tree of a graph G is a subgraph which includes 

all the vertices of G and is also a tree.

19 of 29


A subgraph of G is a graph, each of whose vertices belongs 

to G and each of whose edges belongs to G.

20 of 29


A connected graph with no cycles.

21 of 29


Same as degree

22 of 29


A point on a graph (also called a node).

23 of 29


The number associated with each edge on a graph

24 of 29

Weighted graph

A graph where each edge has a ‘weight’. (Also known as a 


25 of 29

Bubble sort

 A simple sorting procedure that begins by ordering the first 

and second items, then the second and third, and so on, 

until the end of the set is reached. The process is repeated 

until all items are correctly ordered

26 of 29

Bin packing

 Refers to problems that involve the packing of objects into 

well defined regions called bins, so that they do not 

overlap. The main purpose is to make efficient use of the 

available space

27 of 29

Binary search

 A technique for locating a particular value in a sorted list

by finding the median value and comparing it to the target 


28 of 29


Two vertices are connected if there is a path between them. 

A graph is connected if all its vertices are connected.

29 of 29


No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Graphs and transformations resources »