離散数学入門#1: グラフの基礎知識（前編），握手補題の証明と応用

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 this (Part 1), "Fundamentals of Graphs (Part 1)," basic terms in graph theory are explained. This video explains vertex and edge sets of graphs, rank and size of graphs, multiple edges and loops, simple and multiple graphs, directed graphs, weighted graphs, graph isomorphisms, subgraphs, spanning subgraphs, induced subgraphs, complete graphs, bipartite and complete bipartite graphs, n-partite and complete n-partite graphs, roads, closed roads, connected graphs, trees, forests, degrees, etc. The very famous theorem on degree, "the handshaking lemma" and two corollaries of handshaking lemma are introduced with proofs. Other theorems on degree and regular graphs will also be introduced. 0:00 Opening 0:03 Graphs 5:52 Multiple edges and loops, simple and multiple graphs 7:39 Directed graphs (digraphs) 10:24 Weighted graphs 13:45 Graph isomorphisms 17:41 Subgraphs, spanning subgraphs, and induced subgraphs 22:28 Complete graphs and cliques 24:35 Bipartite and complete bipartite graphs 27:08 n-part graphs and complete n-part graphs 28:04 Paths and closed paths (cycles) 29:53 Connectivity of graphs 31:29 Trees and forests 33:26 Vertex degree 35:20 Degree of a vertex in a directed graph (in-degree and out-degree) 37:31 Handshaking lemma (undirected graph version) 41:10 Handshaking lemma (directed graph version) 42:54 Corollary of handshaking lemma (1) (even number of odd points) 45:16 Other theorems on degree (simple graphs of degree 2 or more have vertices of the same degree) 47:45 Regular graphs, corollary of handshaking lemma (2) (If r is odd, then the rank of an r-regular graph is even) 50:33 Other theorems on regular graphs (how to construct regular graphs) 54:17 Adjacency matrices 56:56 Closing remarks and preview of next session ▷ Playlist: List of the videos in this lecture series    • 離散数学入門 〜グラフ理論の世界にようこそ〜   --------------------------------------------------------------------------------------- Assistant video editor: SK