Key terms for d1 Flashcards
efficiency
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.
Size
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.
Order
The order of an algorithm is a measure of its efficiency as a function of the size of the
problem.
Degree of a vertex
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.
path
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.
Cycle
A cycle (circuit) is a closed path, i.e. the end vertex of the last edge is the start vertex of
the first edge.
tree
A tree is a connected graph with no cycles.
Spanning tree
A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also
a tree.
Eulerian graph
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.
semi-Eulerian graph
A semi-Eulerian graph is a graph with exactly two vertices of odd degree.
Hamiltonian cycle
A Hamiltonian cycle is a cycle that passes through every vertex of a graph once and only
once, and returns to its start vertex
Planar graph
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
Isomorphic
Two graphs are isomorphic if they have the same number of vertices and the degrees of
corresponding vertices are the same.
Travelling salesman problem
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.
triangular inequality
For three vertices A, B and C, the triangular inequality is ‘length AB length AC +
length CB’, where AB is a longest length.
walk
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
tour
A walk which visits every vertex, returning to its starting vertex, is called a tour.
Float
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
Bubble sort comparisons
(n - 1) + (n - 2)…(2) + (1) etc
MST prims
Choose any vertex to start then select arc of min weight which is connected (can be done on distance matrix)
MST Kruskals
List arcs in order and choose min to start, add arcs as long as no cycle formed
Handshaking lemma
Sum of degrees of vertices = 2x number of edges
Gant chart
Graphical way to see range of possible start and finish times
Scheduling diagram
Condensed gant chart
Resource histogram
SHows number of workers that are active at any given time, events start at earliest possible time. (graph of little squares).
