D1 glossary

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 (of a problem)

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 (of an algorithm)

Answer 3

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

Question 4

Middle position

Answer 4

In a list containing N items the ‘middle’ item has position (1/2)(N+1) if N is odd and (1/2)(N+2) if N is even.

Question 5

What is a graph?

Answer 5

A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).

Question 6

Subgraph

Answer 6

A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.

Question 7

Network

Answer 7

If a graph has a number associated with each edge (usually called its weight) then the graph is called a weighted graph or network.

Question 8

Degree

Answer 8

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 9

Path

Answer 9

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 10

Cycle

Answer 10

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 11

Connected

Answer 11

Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.

Question 12

Digraph

Answer 12

If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.

Question 13

Tree

Answer 13

A tree is a connected graph with no cycles.

Question 14

Spanning Tree

Answer 14

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

Question 15

Eulerian Graph

Answer 15

An Eulerian graph is a graph with every vertex of even degree.

Question 16

Eulerian Cycle

Answer 16

An Eulerian cycle is a cycle that includes every edge of a graph exactly once.

Question 17

Semi-Eulerian Graph

Answer 17

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

Question 18

Hamiltonian Cycle

Answer 18

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 19

Planar Graph

Answer 19

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 20

Isomorphic

Answer 20

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

Question 21

Travelling Salesman Problem

Answer 21

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 22

Triangular Inequality

Answer 22

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

Question 23

Walk

Answer 23

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 24

Tour

Answer 24

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

Question 25

Total Float

Answer 25

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