GLOSSARY Flashcards
What is the 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 (proportional to order/complexity)
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.
(In a list it would be the number of items)
What is the order of an algorithm?
A measure of its efficiency as a function of the size of the problem
If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the runtime of an algorithm by a factor of f(n)/f(m)
How to calculate middle items
1/2(N+1) for odd sets, 1/2(N+2) for even sets
What does a graph consist of?
Points (vertices/nodes) which are connected by lines (edges/arcs)
What is a subgraph of a graph G?
A graph each of whose vertices belong to G, and edges belong to G
What is a weighted graph, and give an alternate name for it
A graph whose edges have a number associated with them,
Also called a network
What is the degree/valency of a vertex?
The number of edges incident on it
What are odd/even vertices?
Odd vertices have odd degree, even vertices have even degree
What is a path?
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
What is a walk?
A finite sequence of edges such that the end vertex of one edge is the
start vertex of the next.
What is a trail?
A walk where no edge is visited more than once
tr”aidgel”
What is a cycle/circuit?
A closed path, i.e. the end vertex of the last edge is the start vertex of
the first edge.
What does it mean for vertices to be connected, and what does it mean for a graph to be connected?
Two vertices are connected if there is a path between them. A graph is connected if all its
vertices are connected.
What is a digraph, and what are the edges in a digraph known as?
A digraph contains edges that have a direction associated with them, which are called directed edges
What is a tree?
A connected graph with no cycles
What is a spanning tree of a graph G?
A subgraph of G containing each vertex of G and is also a tree
What is a Eulerian graph?
A graph where every vertex is even
What is a semi Eulerian graph?
A graph with exactly 2 odd vertices
What is a Eulerian cycle/circuit?
A cycle that contains every arc of the graph ONLY ONCE, returning to the starting vertex
In a circuit number of times visited doesn’t rlly matter
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 in such a way that no two edges meet each other, except at a vertex to which they are both incident.
What makes two graphs isomorphic?
Two graphs are isomorphic if they have the same number of vertices and the degrees of
corresponding vertices are the same
What is a tour?
A walk which visits every vertex, returning to its starting vertex
(A closed path)
What is Euler’s handshake lemma?
in every finite undirected graph, the number of vertices that touch an odd number of edges is even
As the sum of the degrees of the vertices = 2x the number of edges
What is the float of an activity?
The maximum time that the activity can be delayed from its start time, without delaying the finish time of the total project
Difference between classical and non classical travelling salesman
Classical - can only traverse each node exactly once
Non Classical - Can visit at least once
Difference between chinese postman and travelling salesman
Chinese wants to visit every arc
Salesman wants to visit every node
Both want to start and end at the same point
What is a simple graph?
A graph that is undirected and does not have any loops or multiple edges between 2 vertices and at most one arc connecting any two vertices
Types of orders of graphs
exponential, linear, factorial, quadratic etc
Difference between a distance and adjacency matrix
Distance describes weight of each arc, adjacency describes number of arcs joining corresponding vertices
(Distance matrix only possible with weighted networks)
Semi Eulerian graph
One that includes a trail that traverses every arc, but starts and finishes at different vertices
Explanation for handshake lemma
(each arc contributes 1 to the orders of two nodes, and so) the
sum of the orders of all the nodes is equal to twice the number of arcs
Which implies that the sum of the orders of all the nodes is even and
therefore there must be an even (or zero) number of vertices of odd
order hence there cannot be an odd number of vertices of odd order
If a graph represented a telephone network, why would you want multiple edges?
So an organisation can make multiple phone calls simultaneously.
Linear programming cavear
Note the > for “more than”, < for “less than”, ≤ for “no more than” and ≥ for “no less than”
Isomorphic meaning
Two graphs are isomorphic when they contain the same number of vertices of the same degree connected in the same way.
Planarity check
If arc appears as O in separate list, graph isn’t planar
Shape of each box in a flow chart
Oval - start/end
Rectangle - instruction
Diamond - decision
