幾何学ＩＩ（Geometry II）[4N14]

＜学位授与の方針＞

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

＜授業のねらい＞

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

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

建築学部は「微分積分I」、他学科は「数学I」あるいは「微分」「積分」を履修済であることが望ましい。

＜具体的な到達目標＞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

14．学習成果の確認
準備学習：総復習を行っておくこと。

＜成績評価方法＞

試験期間に実施する期末試験100％。到達目標に照らして、6段階のGrade(A+,A,B,C,D,F)で評価し、D以上の者に単位を認める。

＜教科書＞

指定教科書なし。適宜プリントを配布する。

＜参考書＞

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

＜オフィスアワー＞

金曜日15:30-16:30（八王子校舎総合教育棟01E-315)

＜学生へのメッセージ＞

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