離散数学入門11 マッチング2：最大マッチングを見つける２つの方法

>> YOUR LINK HERE: ___ http://youtube.com/watch?v=3NYI15FsWBM

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 maximum matching problem is the problem of finding a match that matches as many pairs as possible. Of particular importance is the maximum matching of a bipartite graph, for which there are many examples, such as optimizing the assignment of workers and tasks. In this lecture, we will explain two different algorithms for finding the maximum matching of a bipartite graph: one is to transform the problem into a maximum flow problem and the other is to use an augmenting path of matching. • 0:00 Opening • 0:54 Review of the previous lesson: Examples of maximum matching of bipartite graphs • 2:42 Finding the maximum matching of a bipartite graph (1): Solution by transforming to the maximum flow problem • 12:18 Finding maximum matching of a bipartite graph (2): Solution by using augmenting paths of matching • ▷ Playlist: List of the videos in this lecture series • • 離散数学入門〜グラフ理論の世界にようこそ〜 • --------------------------------------------------------------------------------------- • Assistant video editor: SK

#############################

New on site