2021年度 学院等開講科目 工学院 専門科目
グラフ理論とその応用
- 開講元
- 専門科目
- 担当教員
- WIMER SHMUEL
- 授業形態
- 講義
- メディア利用科目
- -
- 曜日・時限
(講義室) - 月3-4
- クラス
- -
- 科目コード
- XEG.S404
- 単位数
- 100
- 開講時期
- 2021年度
- 開講クォーター
- 3Q
- シラバス更新日
- 2025年7月10日
- 使用言語
- 英語
シラバス
授業の目的（ねらい）、概要
Graph theory results are widely used to model and solve many engineering, social and natural science problem; it is also an excellent mean to explore proof techniques in discrete mathematics. This course aims at introducing basic graph theory concepts, and it demonstrates how they can be used in facing real-life modeling and design problem.
到達目標
The main goal of this course is to equip the students with graph theory “state of mind” in facing engineering problems. The students will acquire graph theory basic knowledge and will experiencing solutions to some common problems, which will direct them towards utilizing analytical approach in their R&D challenges, in addition to simulation and experiments, which are commonly used in R&D.
キーワード
Graph theory, Algorithms, Complexity, Linear algebra, Combinatorics, and Probability
学生が身につける力
- 専門力
- 教養力
- コミュニケーション力
- 展開力 (探究力又は設定力)
- 展開力 (実践力又は解決力)
授業の進め方
This course aims at introducing basic graph theory concepts, and it demonstrates how they can be used in facing real-life modeling and design problem. Its approach it a mix of formal and intuition, where no previous knowledge in graph theory is assumed. There will be formal proofs of some important theorems (though few), while others will only be overviewed. Algorithms and complexity will only be briefly discussed as those are widely covered in other courses. Each of the topics will demonstrate related practical problems.
授業計画・課題
| 授業計画 | 課題 | |
|---|---|---|
| 第1回 | Matching | Maximum matching, bipartite graphs. |
| 第2回 | Matching (cont’d) | Perfect matching, matching algorithms. |
| 第3回 | Cliques and independent sets | Shannon capacity, Turán’s theorem, Ramsey’s theorem. |
| 第4回 | Graph coloring | Vertex coloring, the chromatic number, perfect graphs, map coloring, edge coloring. |
| 第5回 | Connectivity | Vertex connectivity, edge connectivity, 3-connected graphs. |
| 第6回 | Planar graphs | Duality, Euler formula, bridges, planarity recognition, the four-color problem. |
| 第7回 | The probabilistic method | Random graphs, expectation, variance, evolution of random graphs. |
準備学修(事前学修・復習)等についての指示
学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。
教科書
None
参考書、講義資料等
All lectures slides will be available on-line.
J.A. Bondy and U.S.R. Murty, Graph Theory, Springer.
D.B. West, Introduction to Graph Theory, Prectice-Hall.
成績評価の方法及び基準
Learning achievement is evaluated by the quality of the written reports, exercise problems, and etc.
関連する科目
- XEG.S405 ： ディジタルVLSI設計
- XEG.S605 ： ディジタルVLSI設計特論
- XEG.S406 ： 計算機アーキテクチャ(工学院）
- XEG.S607 ： 計算機アーキテクチャ特論(工学院）
履修の条件・注意事項
Students are supposed to have some background in algorithms, basic knowledge of linear algebra, combinatorics and probability.
連絡先 (メール、電話番号) ※”[at]”を”@”(半角)に変換してください。
atsushi [at] ict.e.titech.ac.jp
オフィスアワー
Contact by e-mail in advance to schedule an appointment