Definitions Flashcards
(17 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
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 = 2x 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 an 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 Semi-Eulerian graph?
A graph with exactly 2 odd vertices is semi-Eulerian.
What is a tour?
A walk which visits every vertex.
What is the difference between classical and practical problems?
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.
