Section 1.1 - Euler Circuits
Instructions
- The first video below explains the concepts in this section.
- This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.
Concepts
- Definition of a graph
- Definition of paths, circuits, and deadheading
- Definition Euler paths and Euler circuits
- Determining if a list of vertices is a path, circuit, Euler path, and/or Euler circuit
Exercises
Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.
1. Draw a graph depicting the Howdy bus route. MSC \(\rightarrow\) Beutel \(\rightarrow\) Kleberg \(\rightarrow\) Lot 97 \(\rightarrow\) PEAP \(\rightarrow\) Park West \(\rightarrow\) Olsen \(\rightarrow\) Kleberg \(\rightarrow\) MSC
2. How many vertices and edges does the following graph have?
6 vertices, 8 edges
3. Identify the adjacent edges in the following graph.
AB, BC, BE, CE, CF, EF
4. What are two different paths from A to F in the graph below?
ABCDLGF, AIHF, ABKLGF, ABCDEGF, etc.
5. Is ABECDEA a path, a circuit, an Euler path, an Euler circuit, or none of the above?
Circuit
6. Is DEFGCFABCDGH a path, a circuit, an Euler path, an Euler circuit, or none of the above?
Euler path
7. Is FBDEAFBC a path, a circuit, an Euler path, an Euler circuit, or none of the above?
Path
8. Is ABCHFGDE a path, a circuit, an Euler path, an Euler circuit, or none of the above?
None of the above
9. Is BCDCBADAB a path, a circuit, an Euler path, an Euler circuit, or none of the above?
Euler circuit
10. Is ABCACBA a path, a circuit, an Euler path, an Euler circuit, or none of the above?
Circuit
11. Find a path from F to A with deadheading in the following graph.
One possible answer: FDCBEDCBA