早稲田大学の全学部の3〜4年生を対象とする全学オープン科目「離散数学入門」（担当教員：早水 桃子）の授業動画です．文理を問わず，誰でもグラフ理論やグラフアルゴリズムの初歩を学ぶことができます．グラフ理論の定理やグラフに関するアルゴリズムを正しく理解して，現実の諸問題を解決するための応用力を身につけましょう．
---------------------------------------------------------------------------------------
今回（第1回）は「グラフの基礎知識（前編）」ということで，グラフ理論の基本的な用語を解説します．この動画で説明するのは，グラフの頂点集合と辺集合，グラフの位数とサイズ，多重辺とループ，単純グラフと多重グラフ，有向グラフ，重み付きグラフ，グラフの同型性，部分グラフ，全域部分グラフ，誘導部分グラフ，完全グラフ，二部グラフと完全二部グラフ，n部グラフと完全n部グラフ，道，閉路，連結グラフ，木，森，次数などです．次数に関する非常に有名な定理「握手補題 (the handshaking lemma)」と握手補題の二つの系を証明つきで紹介します．次数に関するその他の定理や，正則グラフに関する定理も紹介します．

0:00 オープニング
0:03 グラフ
5:52 多重辺とループ，単純グラフと多重グラフ
7:39 有向グラフ（ダイグラフ）
10:24 重み付きグラフ
13:45 グラフの同型性
17:41 部分グラフ，全域部分グラフ，誘導部分グラフ
22:28 完全グラフとクリーク
24:35 二部グラフと完全二部グラフ
27:08 n部グラフと完全n部グラフ
28:04 道（パス）と閉路（サイクル）
29:53 グラフの連結性
31:29 木と森
33:26 頂点の次数
35:20 有向グラフにおける頂点の次数（入次数と出次数）
37:31 握手補題（無向グラフ版）
41:10 握手補題（有向グラフ版）
42:54 握手補題の系①（奇点の個数は偶数）
45:16 次数に関するその他の定理（次数2以上の単純グラフには次数が同じ頂点が存在する）
47:45 正則グラフ，握手補題の系②（rが奇数ならば，r-正則グラフの位数は偶数である）
50:33 正則グラフに関するその他の定理（正則グラフの作り方）
54:17 隣接行列
56:56 おわりの挨拶と次回の予告

▷ 再生リスト：「離散数学入門」の動画一覧
   • 離散数学入門 〜グラフ理論の世界にようこそ〜  
---------------------------------------------------------------------------------------
▷ 2021年度 授業シラバス
https://www.wsl.waseda.jp/syllabus/JA...
▷ Twitter（早稲田大学 早水桃子研究室）
  / hayamizu_lab  
▷ 質問箱
https://peing.net/ja/hayamizu_lab
---------------------------------------------------------------------------------------
▷ 教科書
『例題で学ぶグラフ理論』（安藤 清, 土屋 守正, 松井 泰子 共著）森北出版
https://www.amazon.co.jp/dp/462705281...
▷ 参考書やアプリなど
・『グラフ理論入門：基本とアルゴリズム』（宮崎 修一 著） 森北出版
https://www.amazon.co.jp/dp/462785281...
・『グラフ理論入門』（R.J. ウィルソン 著, 西関 隆夫, 西関 裕子 共訳）近代科学社
https://www.amazon.co.jp/dp/476490296...
・『アルゴリズム図鑑 絵で見てわかる26のアルゴリズム』（石田 保輝, 宮崎 修一 共著）森北出版（iOS/Android 無料アプリ版だと色々なアルゴリズムをアニメーションで学べます．）
https://www.amazon.co.jp/dp/479814977...
---------------------------------------------------------------------------------------
【モデレーターより】
早水研究室の動画を見てくださり誠に有難うございます。当チャンネルの動画は早稲田大学の学生や教員が視聴するものですので、YouTubeのポリシーに反するコメントや教育上の観点から不適切と思われるコメントは、モデレーターの判断で削除する場合がございます。受講生や他の教員に読まれることを想定した上でのコメント投稿をお願い申し上げます。