Graph Theory Flashcards
Get gud (20 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 = 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 is M in terms of Big M?
An arbitrary large, real number
