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.
---------------------------------------------------------------------------------------
This (the second) issue of "Fundamentals of Graphs (Part 2)/Trees and Minimum Spanning Trees" is a two-part series.
In "Fundamentals of Graphs (Part 2)," first, we will organize and explain the terms "walk," "trail," "path," "circuit," and "cycle," which are confusing and easy for beginners to stumble upon. The course also explains graph connectivity concepts such as cutpoints, bridges, cut sets, and point connectivity, as well as geometric concepts such as distance in graphs (shortest distance) and graph diameter.
In "Trees and Minimum Spanning Trees," after discussing important properties of trees and theorems on spanning trees, we explain the minimum spanning tree problem in the practical context of knowing the cheapest way to lay optical fiber to connect all towns to the Internet, and describe the widely used Kruskal's algorithm that is widely used to solve it efficiently.

0:00 Opening
0:32 Key words for today's class
1:05 Sidewalks, trails, paths, roads, circuits, closed circuits
9:22 Some theorems on sidewalks, paths, trails, roads, circuits, and closed circuits
15:12 Cutting points, bridges, cut sets, point connectivity
28:26 Distance in graphs, diameters of graphs
33:40 Trees and spanning trees
45:09 Minimum spanning tree problem and Kruskal's algorithm
56:12 Ending (notice for next time)

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