離散数学入門#6: オイラーグラフと郵便配達員問題

This is one of the lecture videos of the "Introduction to Discrete Mathematics" by Dr Momoko Hayamizu, a module open to all 3rd and 4th-year students of Waseda University, Tokyo, Japan. By her lecture series, students can learn the basics of discrete mathematics and how to use graph-theoretical theorems and algorithms to solve real-world problems. --------------------------------------------------------------------------------------- A graph that can travel in a single stroke, passing through all edges exactly once, is called an Eulerian graph, and a circuit corresponding to such a single stroke travel path is called an Eulerian circuit. In the real world, for example, when we want to design a patrol route for a street sweeper or a snowplow to pass through all streets without wasting time, problems to determine whether a given graph is an Eulerian graph or not, or to find a specific Eulerian circuit appear. In this lecture, we prove a characterization theorem for Eulerian graphs given by Euler himself and explain Fullali's algorithm as a method for finding Eulerian circuits. As an application of Fuller's algorithm, we will also show how to solve the postman's problem (a problem to find a circular path with the minimum weight of overlapping paths) in a Semi-Eulerian graph. 0:00 Opening 1:15 Two types of traversability: traversability to edges and circularity to vertices 6:38 Review: trails and circuits 8:38 Definitions: Eulerian circuits, Eulerian graphs, Eulerian trails, Semi-Eulerian graphs 10:08 Characterization of Eulerian graphs and their proofs ☆ The proof of "There exists a closed path in a graph whose minimum degree is greater than or equal to 2" used in the proof is as follows    • 離散数学入門#2: グラフの基礎知識（後編），木と最小全域木   17:55 Characterization of Eulerian graphs (directed graph version) 18:20 Characterizing Semi-Eulerian graphs 18:58 How to find Eulerian circuits: Fullali's algorithm 22:12 Postman problem for Semi-Eulerian graphs (application of Fullali's algorithm) ▷ Playlist: List of the videos in this lecture series    • 離散数学入門 〜グラフ理論の世界にようこそ〜   --------------------------------------------------------------------------------------- Assistant video editor: SK