Discrete mathematicsLesson 1 of 1 in the course Graph theory

Eulerian Routes: Criteria, Construction, and Extensions

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

Eulerian paths provide a way to travel through a graph while using every edge exactly once. This lesson introduces the central vocabulary and explains how vertex degrees determine whether an Eulerian trail or circuit is possible.

A trail is a walk that does not repeat edges; vertices may be revisited. An Eulerian trail, also called an Eulerian path or Euler walk, is a trail that uses every edge of the graph exactly once. An Eulerian circuit is an Eulerian trail that returns to its starting vertex. It is also called an Eulerian cycle or Euler tour.

All flashcards

What is an Eulerian trail?
A trail that uses every edge of a graph exactly once; vertices may be revisited.
What is an Eulerian orientation?
An assignment of directions to undirected edges that gives each vertex equal in-degree and out-degree.
What is Fleury's algorithm's edge-choice rule?
Choose an unused edge that is not a bridge when another available edge exists.
What is Hierholzer's algorithm's central construction idea?
Build closed trails from unused edges and splice them into a growing circuit.
What does the BEST theorem help count?
Eulerian circuits in directed graphs, using degree-related factorials and arborescence counts.

Quiz questions

  1. What conditions guarantee a directed Eulerian circuit in a directed graph?Answer: Every vertex has equal in-degree and out-degree, and the nonzero-degree vertices are strongly connected.
  2. When applying Fleury's algorithm, which edge should be chosen when possible?Answer: An unused incident edge that is not a bridge in the remaining graph.
  3. With suitable data structures, what is the running time of Hierholzer's algorithm?Answer: O(∣E∣)O(|E|)
  4. Why can an Eulerian graph have no bridge?Answer: Every edge lies on a closed traversal, so deleting it cannot separate the graph.
  5. What is the complexity classification for counting Eulerian circuits in undirected graphs?Answer: The counting problem is #P-complete.

Based on the Wikipedia article Eulerian path, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Discrete mathematics

All Discrete mathematics lessons
Discrete mathematicsBinary Relations: Operations, Properties, Functions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsPigeonhole Principle: Counting, Collisions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsDe Morgan's Laws in Logic, Set Theory, and Boolean Algebra5 flashcards · 5 quiz questions · 4 gamesPlay free →