Key terms for d1

Question 1

efficiency

Answer 1

The efficiency of an algorithm is a measure of the ‘run-time’ of the algorithm and in most
cases is proportional to the number of operations that must be carried out.

Question 2

Size

Answer 2

The size of a problem is a measure of its complexity and so in the case of algorithms on
graphs it is likely to be the number of vertices on the graph.

Question 3

Order

Answer 3

The order of an algorithm is a measure of its efficiency as a function of the size of the
problem.

Question 4

Degree of a vertex

Answer 4

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.

Question 5

path

Answer 5

A path is 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.

Question 6

Cycle

Answer 6

A cycle (circuit) is a closed path, i.e. the end vertex of the last edge is the start vertex of
the first edge.

Question 7

tree

Answer 7

A tree is a connected graph with no cycles.

Question 8

Spanning tree

Answer 8

A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also
a tree.

Question 9

Eulerian graph

Answer 9

An Eulerian graph is a graph with every vertex of even degree. An Eulerian cycle is a
cycle that includes every edge of a graph exactly once.

Question 10

semi-Eulerian graph

Answer 10

A semi-Eulerian graph is a graph with exactly two vertices of odd degree.

Question 11

Hamiltonian cycle

Answer 11

A Hamiltonian cycle is a cycle that passes through every vertex of a graph once and only
once, and returns to its start vertex

Question 12

Planar graph

Answer 12

A graph that can be drawn in a plane in such a way that no two edges meet each other,
except at a vertex to which they are both incident, is called a planar graph

Question 13

Isomorphic

Answer 13

Two graphs are isomorphic if they have the same number of vertices and the degrees of
corresponding vertices are the same.

Question 14

Travelling salesman problem

Answer 14

The travelling salesman problem is ‘find a route of minimum length which visits every
vertex in an undirected network’. In the ‘classical’ problem, each vertex is visited once only.
In the ‘practical’ problem, a vertex may be revisited.

Question 15

triangular inequality

Answer 15

For three vertices A, B and C, the triangular inequality is ‘length AB  length AC +
length CB’, where AB is a longest length.

Question 16

walk

Answer 16

A walk in a network is a finite sequence of edges such that the end vertex of one edge is the
start vertex of the next

Question 17

tour

Answer 17

A walk which visits every vertex, returning to its starting vertex, is called a tour.

Question 18

Float

Answer 18

The total float F(i, j) of activity (i, j) is defined to be F(i, j) = lj – ei – duration (i, j), where ei
is the earliest time for event i and lj is the latest time for event j

Question 19

Bubble sort comparisons

Answer 19

(n - 1) + (n - 2)…(2) + (1) etc

Question 20

MST prims

Answer 20

Choose any vertex to start then select arc of min weight which is connected (can be done on distance matrix)

Question 21

MST Kruskals

Answer 21

List arcs in order and choose min to start, add arcs as long as no cycle formed

Question 22

Handshaking lemma

Answer 22

Sum of degrees of vertices = 2x number of edges

Question 23

Gant chart

Answer 23

Graphical way to see range of possible start and finish times

Question 24

Scheduling diagram

Answer 24

Condensed gant chart

Question 25

Resource histogram

Answer 25

SHows number of workers that are active at any given time, events start at earliest possible time. (graph of little squares).