Discrete Math 8: Maximum flow problem (1): Basic knowledge of flow networks скачать в хорошем качестве

Discrete Math 8: Maximum flow problem (1): Basic knowledge of flow networks

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 flow problem, which asks the maximum amount of flow from the source to the sink of a network with capacity constraints, is one of the most fundamental and important problems in network theory. The problem has a historical background in that it started to be studied intensively in the mid-1950s due to military requirements, but it has a wide range of applications in modern society. For example, when we consider networks such as traffic networks, water supply networks, and telecommunication networks where each road, pipe, and wire has a certain capacity, the problem of maximizing the flow of cars, water and data within the capacity limits naturally arises. In this video, she first describes some motivating real-world examples of the maximum flow problem and then explains some basic concepts and ideas of flow networks that are necessary to understand the next lecture (Ford-Fulkerson algorithm and the max-flow min-cut theorem). 0:00 Opening 0:55 Example of maximum flow problem (1): Routing of spectators home from events 2:16 Example of maximum flow problem (2): Routing of internet communications 3:44 History of research on the maximum flow problem (Analysis of the railway network around the Soviet Union by the US Air Force in 1955) 6:47 Definition of flow networks 10:37 Definitions related to flow 14:22 Description of the maximum flow problem 14:54 A useful theorem on the maximum flow problem with integer capacities 15:59 How can we tell whether a flow is optimal or not? 17:19 Relationship between the maximum flow and minimum cut problems 22:00 Preview of the next lecture ▷ Playlist: List of the videos in this lecture series    • 離散数学入門 〜グラフ理論の世界にようこそ〜   --------------------------------------------------------------------------------------- Assistant video editor: SK English and Chinese subtitles by Renko Gracia