[前へ戻る]
   

 授業科目
 Course Title
グラフ理論特論
Graph Theory
 担当者
 Instructor
教授   矢島 幸信  後学期 月曜日2時限
 単 位
 Credit
2

到達目標 Target to be Reached
いままでの一般的な数学と異なるグラフ理論の具体性を通して、受講生が数学がいかに応用可能であるかを実感していく。
 
授業内容 Course Content
グラフ理論は応用性の高い数学の一分野で、幾何学的側面をもつ応用数学として、工学系の種々の方面で応用されている。その意味で、現在の社会を数学的に解析する一つの手段としてグラフ理論は極めて有効であると言える。いかに数学的な結果が現実的事象に適用できるかを理解していきたい。数学的な証明の細部にこだわることなく、演習問題などを楽しみながら解いていく。 この過程で、数学的なもののとらえ方や考え方を習得させていきたい。
 
授業計画 Course Planning
予習としては、各回の該当頁をあらかじめ読んで来ること。復習としては、あいまいなところが無いかを確認すること。
Ⅰ.グラフ理論の基礎
 1.グラフと頂点の次数
 2.握手原理とその応用
 3.部分グラフ、同型なグラフ
 4.木
Ⅱ.グラフの彩色
 1.頂点彩色
 2.臨界なグラフ
 3.辺彩色
 4.回転トリック
 5.分解とハミルトンサイクル
 6.同型なグラフへの分解
Ⅲ.回路とサイクル
 1.オイラー回路
 2.オーバーヴォルファハの問題
Ⅳ.応用とアルゴリズム
 1.全域木アルゴリズム
 2.マッチングと予定表問題
 3.2進木と接頭語付きコード
 
授業運営 Course Management
授業は聴講すると言うよりも、セミナー形式で授業に参加するという雰囲気で進めていく。授業中の講義を聴いた後で、それを理解しているかどうかを確認する意味でも、院生が問題を自ら解決していくことを中心に進めていく。
 
評価方法 Evaluation Method
授業において提出された問題にどのように積極的に取り組んでいたかなどの平常点により評価する。
 
オフィスアワー Office Hour (s)
木曜日15時~16時(矢島研究室:6-422)yajimy01@kanagawa-u.ac.jp
 
使用書 Textbook (s)
N.ハーツフィールド/G.リンゲル共著『『グラフ理論入門』[サイエンス社]1993


 
 
 
[前へ戻る]