幾何学ＩＩ（Geometry II）[4568]

＜学位授与の方針＞

◎	1. 基礎知識の習得
○	2. 専門分野知識の習得
	3. 汎用的問題解決技能
	4. 道徳的態度と社会性
	5. 創成能力

＜授業のねらい＞

有限幾何学の代表であるグラフ理論について、毎週ひとつのトピックを取り上げ、グラフ理論の基本的事柄を理解し、問題を点と辺からなるグラフで表現し、短時間で正しい解を探す、グラフ理論独特の解法を身につける。

＜受講にあたっての前提条件＞

１年次の数学の必修科目を履修済であること。

＜具体的な到達目標＞

（１）問題を点と辺からなるグラフで表現し、解を求めることができる。
（２）連結、閉路、木、ネットワークなどグラフ理論の基本概念を理解し、
最小となる解や最大となる解を求めることができる。
（３）PERT法などを理解し、最短時間のスケジュールを求めることができる。

＜授業計画及び準備学習＞

１．結婚定理
グラフ理論の基本となる点と辺の概念について学び、結婚定理について学びます。
準備学習：インターネットなどでグラフ理論とは何かについて、調べておく。

２．オイラーグラフ
道、連結、次数、閉路について学び、オイラーグラフについて学びます。
準備学習：第１回のプリントの問題を解いておく。点、辺、グラフなどの用語を復習しておく。

３．区間グラフ
区間グラフと閉路について学びます。
準備学習：第２回のプリントの問題を解いておく。道、連結、次数などの用語を復習しておく。

４．木と平面グラフ
木と平面グラフの性質について学びます。
準備学習：第３回のプリントの問題を解いておく。第２回と第３回のプリントで連結、次数、閉路などの用語を確認しておく。

５．クルスカルのアルゴリズム
最小木とクルスカルのアルゴリズムについて学びます。
準備学習：第４回のプリントの問題を解いておく。木、連結、閉路などの用語を確認しておく。

６．彩色問題
平面グラフの彩色問題について学びます。
準備学習：第５回のプリントの問題を解いておく。第４回のプリントで平面グラフ、次数、連結などの用語を確認しておく。

７．ネットワーク
ネットワークと最大流について学びます。
準備学習：第６回のプリントの問題を解いておく。

８．スケジュール作成問題
スケジュール作成問題におけるLIST法とPERT法について学びます。
準備学習：第７回のプリントの問題を解いておく。

９．可視性の問題
可視性に問題における美術館定理と要塞定理について学びます。
準備学習：第８回のプリントの問題を解いておく。できれば第６回のプリントで彩色などの用語を復習しておく。

１０．集合場所問題
集合場所問題について学びます。
準備学習：第９回のプリントの問題を解いておく。

１１．順序付け問題
順序付け問題におけるJohnsonの定理について学びます。
準備学習：第１０回のプリントの問題を解いておく。できれば第８回のプリントでPERT法も復習しておく。

１２．割り当て問題
割り当て問題について学びます。
準備学習：第１１回のプリントの問題を解いておく。

１３．区間グラフの応用
区間グラフを中心に第１回〜第７回の理論の応用について学びます。
準備学習：第１回〜第７回のプリントの苦手な部分を復習しておく。

１４．PERT法の応用
PERT法を中心に第８回〜第１２回の理論の応用について学びます。
準備学習：第８回〜第１２回のプリントの苦手な部分を復習しておく。

１５．学習成果の確認（定期試験）
準備学習：第１回〜第１４回の総復習を行うこと。

＜成績評価方法及び水準＞

定期試験で最終成績を評価、60点以上の者に単位を認める。

＜教科書＞

指定教科書なし。
※講義でプリントを配ります。

＜参考書＞

※講義でプリントを配るため特に必要ないと思いますが、休んでわからなくなった場合、深く知りたい場合の参考書として以下を挙げておきます。
１．「グラフ理論入門」R. J. ウィルソン（近代科学社）（第１、２、４、５、６、７、１３回）
２．「グラフ論要説」秋山仁、浜田隆資共著（槇書店）（第１、２、４、５、６、７、１３回）
３．「離散数学入門」秋山仁、R.L.Graham 共著（朝倉書店）（第８、９、１４回）
４．「応用数学入門」小林みどり著（牧野書店）（第１０、１１、１２、１４回）

＜オフィスアワー＞

木曜日14：50〜15:50（八王子校舎1E-315）

＜学生へのメッセージ＞

一見簡単そうだが、頭が硬いと解けない難しいトピックばかりを選んでいます。毎週、独立したトピックを扱うため、必ず復習して下さい。復習の方法としては、プリントの問題をできる限り記憶が残っているうちに（できれば、その日のうち）に解いてみてください。頭が硬いと、あとになればなるほど、わからなくなります。