Discrete Math 4: Orientation & DFS (depth-first search) algorithm скачать в хорошем качестве

Discrete Math 4: Orientation & DFS (depth-first search) algorithm

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. --------------------------------------------------------------------------------------- In the previous lecture, we discussed the "breadth-first" search algorithm, and in this lecture, we will discuss another graph search method called "depth-first" search algorithm. Depth-first search is used in a variety of graph algorithms and has many important graph-theoretic applications. Here, we focus on the problem of finding a strongly connected orientation of a graph, which appears in the design of one-way streets and tour routes, and introduce two types of solutions: an orientation algorithm based on Robbins' theorem (one-way street theorem) and an orientation algorithm utilizing depth-first search trees. Please try practicing on various graphs. 0:00 Opening 0:45 Review of previous session (Searching for graphs using breadth-first search algorithm) 1:24 Depth-first algorithm 6:40 Connectivity of directed graphs 8:10 Orienting graphs, strongly connected orientations 9:25 Significance of strongly connected orientations of graphs (real world applications) 11:14 Points to note about strongly connected orientations 11:55 Characterizing graphs with strongly connected orientations (Robbins' theorem) 14:25 Corollary used in the proof of Robbins' Theorem (edge e is not a bridge ⇔ edge e is contained in some closed path) 15:29 Essentials of the proof of Robbins' Theorem (1) (Ear decomposition of connected graphs without bridges) 18:38 Essentials of the proof of Robbins' Theorem (2) (How to find strongly connected orientations using ear decomposition) 21:11 Using depth-first search trees (DFS trees) to find strongly connected orientations. ▷ Playlist: List of the videos in this lecture series    • 離散数学入門 〜グラフ理論の世界にようこそ〜   --------------------------------------------------------------------------------------- Assistant video editor: SK