D1 terms

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

every other vertex.

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

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

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

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.)

 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) 

degree

An algorithm that finds the shortest paths from a single 

source vertex to all other vertices in a directed graph.

 A line on a graph connecting two nodes

A vertex is even if it has even degree.

 The last point in a network

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

connected by lines (edges or arcs).

An algorithm used to find the minimum spanning tree of a 

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

Same as a minimum spanning tree

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

small as possible. (MST is sometimes called a minimum 

connector.

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

weighted graph)

A point on a graph (same as a vertex)

A vertex is odd if it has odd degree

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

An algorithm used to find the minimum spanning tree of a 

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

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

all the vertices of G and is also a tree.

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

to G and each of whose edges belongs to G.

A connected graph with no cycles.

Same as degree

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

The number associated with each edge on a graph

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

network).

 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

 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

 A technique for locating a particular value in a sorted list

by finding the median value and comparing it to the target 

value

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

A graph is connected if all its vertices are connected.