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.
---------------------------------------------------------------------------------------
The theory of matching is involved in various real-world decisions, such as matching marriage partners, assigning jobs to workers, assigning residents to hospitals, and assigning students to laboratories. As an introduction to matching theory, this lecture will explain basic knowledge about matching, and will introduce Hall's Marriage Theorem and Tutte's Theorem, which characterize bipartite graphs with perfect matching and generalize it, and a method for solving the postman problem using minimum weight perfect matching of a weighted perfect graph K_2n. Various results on perfect matching are outlined.

0:00 Opening
0:35 Matching Example 1: Matching marriage partners
1:51 Matching example 2: Distributing gifts
2:53 Matching example 3: Assigning work to translators
3:51 Matching example 4: Matching a sixth-year medical student with a clinical training hospital
5:38 Definitions and notes on terms related to matching
12:09 Hall's marriage theorem (characterization of bipartite graphs with perfect/saturated matching)
16:06 Tutte's theorem (characterization of graphs for which perfect matching exists)
17:30 Edge coloring of complete graphs 𝑲_𝟐𝒏 and decomposition of the edge set of 𝑲_𝟐𝒏 into complete matching
19:29 Decomposition of the complete graph 𝑲_𝟐𝒏-1 into edge colorings and maximal matching of edge sets of 𝑲_𝟐𝒏-1
19:47 Review of the postman problem
22:06 Outline of the solution of the postman problem with application of perfect matching of 𝑲_𝟐𝒏

▷ Playlist: List of the videos in this lecture series
   • 離散数学入門 〜グラフ理論の世界にようこそ〜  
---------------------------------------------------------------------------------------
Assistant video editor: SK