[前へ戻る]
   

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

関連するディプロマポリシー Related Diploma Policy
時代の課題と社会の要請に応えた専門的知識と技能/Expert knowledge and skills to address the issues of the age and the demands of society
 
到達目標 Target to be Reached
情報工学や経営工学におけるデータや問題の数理モデル化手法としてグラフ理論は有効であるが、非常に大きいグラフに対しては、性質を直接的に証明したり特徴量を計算したりするのは現実的に難しい場合もある。この科目では、代数的手法を使うことで、グラフに関する様々な性質を簡潔に証明できるようになることを目標とする。有向グラフの特殊な場合として、二項関係、順序、束、写像、全単射などに関する性質も含む。グラフ不変量について圏論的に理解することも目標とする。

また、グラフは幾何的な概念であるが、集合を用いて二項関係として理解したり、線形代数を用いて行列として理解するなど、様々な方法で表現できる概念である。このように同一のものを様々な方法で表現できることを学ぶことによって、高等学校までの「数学」における、式、関数、図形、確率などについても、様々な方法で表現できることを理解し、わかりやすく他人に説明できるようになる。したがって、この科目は高等学校の数学教育にも還元できる科目である。

 
授業内容 Course Content
前半は有向グラフの諸性質と行列表現について学ぶ。後半では、有向グラフの特別な例である、同値関係、順序、束、写像、全単射などを含めて、様々な有向グラフの諸性質を代数的に証明する方法を学ぶ。
 
授業計画 Course Planning
第2回以降についての資料は事前に配布する。予習として、毎週指定される問題について解いてくることが不可欠である。復習として、講義中の他の学生の発表内容や教員からの指摘内容を確認し、ノートを清書してくることも不可欠である。予習・復習併せて各回あたり4時間の自己学習を想定している。

第1回: シラバスの記載事項の確認、グラフとは何か、グラフの例
第2回: 有向グラフ
第3回: 隣接行列
第4回: 関係演算
第5回: 同値関係
第6回: 順序関係
第7回: 束
第8回: さまざまな代数
第9回: 関係代数
第10回: 全域性、一価性
第11回: 単射性、全射性
第12回: 圏
第13回: グラフ不変量
第14回: 総復習、グラフと代数と圏論の概観

 
授業運営 Course Management
受講者は、毎週指定される問題について解いたうえで講義に臨み、授業中に白板を使って説明する、という流れとなる。教員の質問に答えられない場合は、答えられるようになるまで何度でも復習が必要となる。
 
評価方法 Evaluation Method
毎回の発表内容で100%評価する。
 
オフィスアワー Office Hour (s)
西澤准教授:木曜日12:40~14:00(6-418室)
   あるいはnishizawa@kanagawa-u.ac.jpまで(常時)。


 
使用書 Textbook (s)
適宜資料を配布する。
参考書 Book (s) for Reference
R.J.ウィルソン著/西関隆夫・西関裕子共訳『グラフ理論入門 原書第4版』[近代科学社]2001
James L.Hein (著), 神林 靖 (翻訳)『独習コンピュータ科学基礎I 離散構造』[翔泳社]2011

 
 
 
[前へ戻る]