Definitions Flashcards
What is a subgraph of a graph?
A subgraph has all vertices and edges belonging to the original graph
What is a path?
Finite sequence of edges
Such that the end vertex of one edge in the sequence is the start vertex of the next
No vertex appears more than once
What is a cycle/ circuit
A closed path
End vertex of the last edge is the start vertex of the first edge
What is a tree
A connected graph with no cycles
What is a spanning tree
The spanning tree of a graph G is a subgraph which includes all vertices of G and is a tree
What is an Eulerian graph
A graph where every vertex has an even degree
What is an Eulerian cycle
A cycle that includes every edge of a graph exactly once
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 the graph once and returns to the start vertex
What is a planar graph
A graph that can be drawn such that no two edges meet each other except at the vertex they are both incident
What are isomorphic graphs
Isomorphic graphs have the same number of vertices and the degrees of corresponding vertices are the same
What is the difference between the classical and practical TSP
Classical - only visit each vertex once
Practical - you can revisit vertices
What is a walk
Finite sequence of edges
End vertex of one edge is the start vertex of the next
(different to a path because you can repeat edges)
What is the handshaking lemma
The sum of degrees is two times the number of edges
