[前へ戻る]
   

 授業科目
 Course Title
グラフ理論特論
Graph Theory
 担当者
 Instructor
准教授 西澤 弘毅  前学期 月曜日2時限
 単 位
 Credit
2

到達目標 Target to be Reached
 本講義の到達目標は、受講生が、①グラフ理論に現れる基本的な概念の定義を述べられるようになること、②グラフ理論の基本的な命題を述べられるようになること、③同一の対象でも、集合、図、行列などのさまざまな表現を使って表せるようになることである。
 
授業内容 Course Content
 グラフ理論は、物と物のつながり具合の情報を扱う数学の一分野である。その定義は非常に抽象的だが、情報科学においても回路やアルゴリズムなど幅広い応用がある。この講義では、下記の使用書に沿って、グラフ理論の基本的な概念と命題を学ぶ。また、同一の対象でも、集合、図、行列などのさまざまな表現を使って表せるということも学ぶ。
 
授業計画 Course Planning
以下の内容を順に学ぶ。ただし、進捗状況により内容は前後する。

1 グラフとは何か
2 グラフの例
3 道と閉路
4 オイラー・グラフ
5 ハミルトン・グラフ
6 最短路問題
7 木
8 有向グラフ
9 マルコフ連鎖
10 直積集合と二項関係
11 順序関係
12 同値関係
13 グラフの行列表現
14 圏
15 総復習
 
授業運営 Course Management
受講者は、講義を聞いて理解したのち、簡単な演習問題を解く。
 
評価方法 Evaluation Method
総復習の試験100%で評価する。ただし、毎週の演習状況が良い場合、それを加味して評価を上げる場合がある。
 
オフィスアワー Office Hour (s)
水曜日 12:10~13:30(6-418室)
 
使用書 Textbook (s)
R.J.ウィルソン著/西関隆夫・西関裕子共訳『グラフ理論入門』原書第4版[近代科学社]2001年


 
 
 
[前へ戻る]