D1 glossary 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 (of a problem)
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 (of an algorithm)
The order of an algorithm is a measure of its efficiency as a function of the size of the problem.
Middle position
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.
What is a graph?
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).
Subgraph
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
Network
If a graph has a number associated with each edge (usually called its weight) then the graph is called a weighted graph or network.
Degree
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.
Connected
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.
Digraph
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.
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.
Eulerian Cycle
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.
Total Float
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.
