幾何学II
教授・桑原 類史
2単位
目的
幾何学とは，図形およびその入れ物である空間の性質を明らかにすることを目的とした理論である．どの様な対象を，どの様な視点および方法で研究するかによって，種々の幾何学体系がある． 本講義では，グラフ理論について講述する．グラフは，点と線からなる1次元の図形であるが，その概念は広い分野の問題と密接に関連しており，その有効性は，計算機科学の発展とともに，益々拡大している．
概要
グラフについての基礎的概念，性質を学び，更に，種々の話題(テーマ)について，応用を意識しつつ講義する．
キーワード
グラフ，最短経路問題，ネットワークフロー，マッチング
先行科目
関連科目
注意
普段から演習などの自主的勉強を期待する．
目標
| 1. | 1. グラフに関する基本概念とその性質を理解する． |
| 2. | 2. 数理科学や社会科学に関する種々の問題がグラフによって定式化，研究できることを理解する． |
| 3. | 3. 具体的な問題について，グラフによる解法例を学び，修得する． |
計画
| 1. | グラフとは -グラフの基礎概念 |
| 2. | グラフの基礎的諸性質 |
| 3. | オイラーグラフ，ハミルトングラフ |
| 4. | 歩道に関する最適化問題 |
| 5. | 木の基本性質，最小全域木 |
| 6. | 有向グラフ，最長経路問題 |
| 7. | ネットワークフロー |
| 8. | 最大フロー最小カット定理 |
| 9. | マッチング，Hallの結婚定理 |
| 10. | ネットワークフローとマッチング |
| 11. | 結婚定理の周辺 |
| 12. | グラフの点彩色 |
| 13. | 彩色多項式 |
| 14. | その他の話題(1) |
| 15. | その他の話題(2) |
| 16. | 総括授業 |
評価
授業中に課す演習問題，レポート課題などの評価と期末の試験によって評点を付ける．
再評価
有り
教科書
プリントを配布する
参考資料
ウイルソン著(西関訳)「グラフ理論入門」近代科学社，他
連絡先
桑原(088-656-7226, kuwabara@ias.tokushima-u.ac(no-spam).jp)
- オフィスアワー: 金曜日 15時から17時