Paths and cycles Flashcards
What is a network?
A graph that represents real life applications (eg: a road network)
What is a walk?
Any route through a graph from vertex to vertex along connecting edges
What is an open walk?
A route through a graph that starts and finishes at different vertices
What is a closed walk?
A route through a graph that starts and finishes at the same vertex
What is the length of a walk?
The number of edges of the walk
What is a trail?
A route through a graph with no repeated edges
What is an open trail?
A route through a graph with no repeated edges which starts and finishes different vertices
What is a closed trail?
A route through a graph with no repeated edges which starts and finishes at the same vertex
What is a closed trail also called?
A circuit
What is a path?
A route through a graph with no repeat use of edges or vertices (except start/end vertex)
What is an open path?
A route through a graph with no repeat use of edges or vertices which starts and finishes at different vertices
What is a closed path?
A route through a graph with no repeat us of edges or vertices which starts and finishes at the same vertex
What is the length of a path?
The number of edges of the path
What is a bridge?
An edge in a connected graph that leaves the graph disconnected if removed
What is a Eulerian trail?
A route through a connected graph with no repeated edges
What is a Eulerian circuit?
A route through a connected graph with no repeated edges that starts and finishes at the same vertex
What are the features of a Eulerian graph?
- Connected
- Has a closed trail (every edge travelled only once, starts and finished at same vertex)
- Only has even vertices
What is a semi-Eulerian trail?
A route through a connected graph with no repeated edges that starts and finishes at different vertices
What are the features of a semi-Eulerian graph?
- Has semi-Eulerian trail (connected, no repeated edges, starts and finishes at different vertices)
- Exactly 2 odd vertices
What is a Hamiltonian path?
- A route through a graph with no repeated edges or vertices that includes every vertex in the graph
- Starts and finishes at different vertices
What is a Hamiltonian cycle?
- A route through a graph with no repeated edges of vertices that includes every vertex in the graph
- Starts and finishes at the same vertex
What are the features of a Hamiltonian graph?
- Has Hamiltonian cycle (starts and finishes at same vertex, includes every vertex only once)
- Connected
What are the features of a semi-Hamiltonian graph?
- Connected
- Contains Hamiltonian path (starts and finishes at different vertices, includes every vertex only once) but not Hamiltonian cycle
