Decision Maths Glossary

Question 1

What is efficiency of an algorithm?

Answer 1

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

What is the size of a problem?

Answer 2

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

What is the order of an algorithm?

Answer 3

A measure of its efficiency as a function of the size of the problem

Question 4

A list contains N items, where N is odd, what is the position of the middle item?

Answer 4

1/2 (N+1)

Question 5

A list contains N items, where N is even, what is the position of the middle item?

Answer 5

1/2 (N+2)

Question 6

What does a graph consist of?

Answer 6

Points (vertices/nodes) connected by lines (edges/arcs)

Question 7

What is a subgraph of graph G?

Answer 7

A graph, each of whose vertices belongs to G and each of whose edges belongs to G

Question 8

What is a weighted graph?

Answer 8

A graph with numbers associated with each edge

Question 9

What is the degree/valency of a vertex?

Answer 9

Number of edges incident to it

Question 10

What is a cycle?

Answer 10

A closed path

Question 11

When are two vertices connected?

Answer 11

A path between them

Question 12

When is a graph connected?

Answer 12

All its vertices are connected

Question 13

What is a digraph?

Answer 13

If the edges of a graph have a direction associated with them

Question 14

What is a tree?

Answer 14

A connected graph with no cycles

Question 15

What is a spanning tree?

Answer 15

A subgraph which includes all the vertices and is also a tree

Question 16

What is an Eulerian graph?

Answer 16

A graph with every vertex of even degree

Question 17

What is a semi-Eulerian graph?

Answer 17

A graph with exactly two vertices of odd degree

Question 18

What is a Hamiltonian cycle?

Answer 18

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

Question 19

What is a planar graph?

Answer 19

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

Question 20

When are two graphs isomorphic?

Answer 20

Same number of vertices and the degrees of the corresponding vertices are the same

Question 21

What is the travelling salesman problem?

Answer 21

Find a route of minimum length which visits every vertex in an undirected network

Question 22

What is the difference between the classical and practical travelling salesman problems?

Answer 22

Classical: each vertex is visited only once
Practical: A vertex may be revisited

Question 23

What is the triangular inequality for the vertices A, B and C?

Answer 23

length AB =< length AC + length CB

Where AB is a longest length

Question 24

What is a walk?

Answer 24

A route through a graph along edges from one vertex to the next

Question 25

What is a tour?

Answer 25

A walk which visits every vertex and returns to its starting vertex

Question 26

What is a path?

Answer 26

A walk in which no vertex is visited more than once

Question 27

What is a trail?

Answer 27

A walk in which no edge is visited more than once

Question 28

What is a loop?

Answer 28

An edge that starts and finishes at the same vertex

Question 29

What is a simple graph?

Answer 29

A graph in which there are no loops and there is at most one edge connecting any pair of vertices