Decision Maths Glossary Flashcards
What is efficiency of an algorithm?
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
What is the size of a problem?
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
What is the order of an algorithm?
A measure of its efficiency as a function of the size of the problem
A list contains N items, where N is odd, what is the position of the middle item?
1/2 (N+1)
A list contains N items, where N is even, what is the position of the middle item?
1/2 (N+2)
What does a graph consist of?
Points (vertices/nodes) connected by lines (edges/arcs)
What is a subgraph of graph G?
A graph, each of whose vertices belongs to G and each of whose edges belongs to G
What is a weighted graph?
A graph with numbers associated with each edge
What is the degree/valency of a vertex?
Number of edges incident to it
What is a cycle?
A closed path
When are two vertices connected?
A path between them
When is a graph connected?
All its vertices are connected
What is a digraph?
If the edges of a graph have a direction associated with them
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A subgraph which includes all the vertices and is also a tree
What is an Eulerian graph?
A graph with every vertex of even degree
What is a semi-Eulerian graph?
A graph with exactly two vertices of odd degree
What is a Hamiltonian cycle?
A cycle that passes through every vertex of a graph once and only once, and returns to its start vertex
What is a planar graph?
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
When are two graphs isomorphic?
Same number of vertices and the degrees of the corresponding vertices are the same
What is the travelling salesman problem?
Find a route of minimum length which visits every vertex in an undirected network
What is the difference between the classical and practical travelling salesman problems?
Classical: each vertex is visited only once
Practical: A vertex may be revisited
What is the triangular inequality for the vertices A, B and C?
length AB =< length AC + length CB
Where AB is a longest length
What is a walk?
A route through a graph along edges from one vertex to the next
What is a tour?
A walk which visits every vertex and returns to its starting vertex
What is a path?
A walk in which no vertex is visited more than once
What is a trail?
A walk in which no edge is visited more than once
What is a loop?
An edge that starts and finishes at the same vertex
What is a simple graph?
A graph in which there are no loops and there is at most one edge connecting any pair of vertices
