シラバス参照

印刷
講義名 演習グラフ理論(EJ)
基準単位数 2
校地 石川
科目群 情報科学系科目（石川）
科目コード I438E
授業実施言語 日本語/英語
開講時期

担当教員
氏名
◎ 金子　峰雄

達成目標 グラフ理論は自然科学、工学、社会科学などにおける様々な現象をモデル記述、特性解析、設計する強力かつ重要な数学的ツールである。グラフの重要な性質や諸定理を理解すると共に、演習を通してグラフ理論を支える論理的な思考と定理証明の技術を修得する。
概要 グラフの基本となる諸定義、名前のついたグラフ、平面グラフ、グラフ彩色、マッチング、ラムゼーの定理、及びこれらに関する問題演習。
評価の観点 グラフの性質と諸定理に関する理解度および応用力による。
評価基準 定期的な宿題・課題・レポート提出（20％）、講義での発表・議論への貢献度（20％）、中間試験（30％）、期末試験（30％）
評価方法 定期的な宿題・課題・レポート提出、講義での発表・議論への貢献度、中間試験、期末試験による。中間試験はチュートリアルアワーにて実施する。
教科書 講義資料を配付する。（教科書としては指定しないが、下記参考書１に準拠して講義を進める。）
参考書 1. Combinatorics and Graph Theory, J. M. Harris, J. L. Hirst, M. J. Mossinghoff, Springer, 2000.
2. Graph Theory, R. Diestel, Springer, 2000.（邦訳：「グラフ理論」R.ディーステル著、根上生也・太田克弘訳、シュプリンガーフェアラーク、2000)
関連項目 なし
履修条件 なし
準備学修等の具体的な指示

本学では、15時間の授業
を含む45時間の学修をもって
1単位とすることを踏まえて、
準備学修に取り組むこと。		 対偶法、背理法、数学的帰納法などの数学的証明法の基本的な考え方を復習しておくこと。
獲得可能な能力・性質 先端科学技術分野の専門家としての、
＜社会的能力＞　論理的思考力、コミュニケーション能力、主体性・忍耐力
＜創出力＞　専門的知識とスキルの探求力、発想力、表現力
＜実践力・行動力＞　情報収集力、批判を受容する力、課題定義力
講義アーカイブ ＜収録内容＞全ての講義・チュートリアルアワーを収録

＜配信方法＞一般配信（学内ネットワークでいつでも視聴可能）

講義計画 1．グラフに関する諸定義、名前のついたグラフ
2．木とその性質、関連定理
3．演習：グラフの基本と木に関する定理証明
4．演習：グラフの基本と木に関する定理証明
5．平面グラフ
6．演習：平面グラフに関する定理証明
7．演習：平面グラフに関する定理証明
8．グラフ彩色
9．演習：グラフ彩色に関する定理証明
10．演習：グラフ彩色に関する定理証明
11．マッチング
12．演習：マッチングに関する定理証明
13．演習：マッチングに関する定理証明
14．ラムゼー定理とそれに関する定理証明演習
曜日/時限 月2/金1