Types of Paths and Cycles Flashcards
1
Q
What is a walk?
A
- Can start & end on same or different vertices
- Include repeated vertices/ or edges
2
Q
What is an open walk?
A
Start & finishes at different vertices
3
Q
What is a closed walk?
A
Start & finishes at same vertex
4
Q
What is a trail?
A
No edges repeated + (vertices may be repeated)
5
Q
What is an open trail?
A
- No edge repeated
- Starts & ends at different vertex
6
Q
What is a closed trail?
A
- No edge repeated
- Starts & ends at same vertex
7
Q
What is a path?
A
- All edges and all vertices are different
- No repeat in vertices & edges (except starting & ending at same vertex in a closed path)
8
Q
What is an open path?
A
- No edges or vertices repeated
- Start & ends at different vertex
9
Q
What is a closed path?
A
- No edge & vertices repeated
- Starts and ends at same vertex
10
Q
What is a cycle?
A
Cycle is a closed path
11
Q
What is a circuit?
A
Circuit is a closed trail
12
Q
What is eulerian?
A
- EEEO (Eulerian, every, edge, once)
- Every vertex must have an even degree
- Start & end at same vertex
13
Q
What is semi-eulerian?
A
- EEEO (Eulerian, every, edge, once)
- 2 vertices are odd degrees and the rest are even degrees
14
Q
What is a Hamiltonian path?
A
- HEVO (Hamiltonian, every, vertex, once)
- Connected graph
- Edges can be repeated
- Starts & ends at different vertices
15
Q
What is a Hamiltonian cycle?
A
- HEVO (Hamiltonian, every, vertex, once)
- Edges may be repeated
- starts and ends at same vertex
16
Q
What is semi-Hamiltonian?
A
- Contains Hamiltonian path but no Hamiltonian cycle
