理工学部Faculty of Science and Engineering
MAT200XF（数学 / Mathematics 200）離散数学Discrete Mathematics
髙澤 兼二郎Kenjiro TAKAZAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | H6782 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 水3/Wed.3 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
経営システム工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
[Course outline]
This course introduces the basis of graph theory and graph algorithms.
[Learning objectives]
Understand the concept of graphs and how to represent practical problems on graphs. Learn the basis of graph theory and basic graph algorithms.
[Learning activities outside of classroom]
Students are expected to review the topics learned in the class and solve the exercises.
[Grading criteria/policies]
The overall grade in the class will be decided based on the term-end examination (100%). The class contribution may be added.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
グラフ理論およびグラフアルゴリズムの基礎について学ぶ．
到達目標Goal
グラフの概念を理解し，現実の様々な問題がグラフ上の問題として表現できることを学ぶ．グラフ理論の基礎を習得する．代表的なグラフアルゴリズムを理解し，具体的な問題例に対してアルゴリズムを用いて解を求められるようになる．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義形式で行う．必要に応じて，質疑応答，問題演習，および演習問題の解説の時間を十分にとる．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：イントロダクション
本授業の内容を概説する．
第2回[対面/face to face]：グラフとは
グラフの定義や表現方法を学ぶ．
第3回[対面/face to face]：よく現れるグラフ
実用上頻繁に現れる，木・2 部グラフ・正則グラフ・完全グラフなどについて紹介する．
第4回[対面/face to face]：平面グラフ
平面描画が可能なグラフについて学ぶ．
第5回[対面/face to face]：最小全域木
グラフにおける最小全域木と，それを求めるアルゴリズムを学ぶ．
第6回[対面/face to face]：最短路問題
グラフにおいて 2 頂点間の最短路を求めるアルゴリズムを学ぶ．
第7回[対面/face to face]：これまでのまとめ
これまでの講義のまとめを行う．
第8回[対面/face to face]：オイラー閉路
グラフがすべての辺を通る閉路をもつ条件，および，それを求めるアルゴリズムについて学ぶ．すなわち，グラフを一筆書きする方法を学ぶ．
第9回[対面/face to face]：ハミルトン閉路
グラフがすべての頂点を通る閉路をもつ条件について学ぶ．
第10回[対面/face to face]：グラフの彩色 (1)
グラフの頂点彩色や辺彩色について学ぶ．
第11回[対面/face to face]：グラフの彩色 (2)
グラフの彩色に関する様々な定理や，4 色問題を紹介する．
第12回[対面/face to face]：マッチング
最大マッチングを求めるアルゴリズムを学ぶ．
第13回[対面/face to face]：最大流問題
ネットワークにおける最大流問題と，それに対するアルゴリズムについて学ぶ．
第14回[対面/face to face]：まとめ
講義全体のまとめを行う.
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】授業中に配布する演習問題および下記の参考書内の演習問題を解いて授業内容の理解度を確認し，理解を確実なものにする．
テキスト（教科書）Textbooks
宮崎修一：グラフ理論入門 基本とアルゴリズム，森北出版，2015．
参考書References
R.J. ウィルソン (著), 西関隆夫, 西関裕子 (訳): グラフ理論入門, 第 4 版, 近代科学社, 2001.
成績評価の方法と基準Grading criteria
定期試験の結果 (100%) によって評価する．平常点を加味することがある．
学生の意見等からの気づきChanges following student comments
具体的な例を示しながら講義することや，授業内に問題演習の時間を設けることを心がける．