D1 Further Maths Flashcards
(16 cards)
What is a walk?
A route through a graph along edges from one vertex to the next
What is a path?
A walk in which no vertex is visited more than once.
A path is a (i) finite sequence of edges, such that (ii) the end vertex of
one edge in the sequence is the start vertex of the next, and in which (iii)
no vertex appears more than once
What is a trail?
A walk in which no edge is visited more than once
What is a cycle?
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
What is a Hamiltonian cycle?
A cycle that includes every vertex
What is a simple graph?
A graph where there are no loops and there is at most one edge connecting any pair of vertices
What is Euler’s handshaking lemma?
Sum of the vertices = 2 x Number of edges
What is a complete graph?
A graph in which every vertex is directly connected by a single edge to each of the other vertices
What are isomorphic graphs?
Graphs which show the same information but may be drawn differently
What is a planar graph?
One that can be drawn in a plane such that no 2 edges meet except at a vertex
What is a Eulerian graph?
One which contains a trail that includes every edge and starts and finishes at the same vertex
What is a Semi-Eulerian graph?
One that contains a trail that includes every edge but starts and finishes at different vertices. Any connected graph with exactly 2 odd vertices is semi-Eulerian.
What is a tour?
A walk which visits every vertex
Difference between classical and practical problem
Classical visits every node exactly once but practical visits every node at least once.
What does Simplex always do?
Maximise
What is M in terms of Big M?
An arbitrary large, real number
