教 授 要 目 |
| 応用情報工学科 | グラフ理論 |
| Theory of Graphs | |
| 2 年 2 単位 選択科目 | |
| 担当教員 西野寿一 | |
| 【 科目概要・到達目標 】 グラフとは点と線でつくられる網目のことで、グラフ理論はグラフを幾何学・代数的・位相的に分析する離散数学の一種である。現実のあらゆる情報・物流ネットワークはグラフ構造をもつもので、グラフ理論はその解析に有用な用具を提供する。本講義では理論の細部への深入りは避け、ネットワークの特性をその連結性と効率の観点から大づかみに把握してもらうことを目標とする。 |
|
| 【 成績評価 】 講義時間内に３〜４回予定してる小演習 50%、期末試験 50%、ただし意味のある独自の考察に対しては、正解か否かに関わり無く、最大20%まで加点する。 |
|
| 【 履修心得 】 前提科目なし。予習復習の必要なし。ただし時間中は講義に集中するよう心がけて欲しい。 |
|
| 【 授業計画 】 1．まえおき(グラフとは) 2．グラフの定式化I (有向グラフと無向グラフ) 3．グラフの定式化II(解析に必要な諸概念) 4．2部グラフとマッチング 5．平面グラフ 6．木I (定義と基本性質) 7．木II （アルゴリズムの2分木表現) 8．木III (重み和最小木) 9．木IV (最短経路木) 10．ネットワークフローI (輸送時間) 11．ネットワークフローII (最大流問題と最小切断） 12．ネットワークフローIII (整合流問題) 13．オイラー経路問題 14．ハミルトン閉路と巡回セールスマン問題 15．まとめ |
|
| 【 教科書 】 なし。ただし講義内容プリントを毎時間配布。 |
|
| 【 参考書 】 なし。 |
|
| 【e-mail address】 オンライン版では非公開です。 |
|
| 【 学生へのメッセージ 】 グラフ理論はある種のパズル的思考を含むので、離散数学的思考に関心をもつ糸口として欲しい。 |
|
| 【 オフィスアワー 】 毎週火・金の午前10時から午後5時まで16号館2Bに在室。 |
|
| | 目 次 | 科目一覧 | |