【授業の目的】
近年、計算機の発達などと共に離散的なデータを扱うことが多くなり、組み合わせ論
的な考え方の重要性は増している。本講義では離散的対象であるグラフの基本的な性
質について学習し、離散的な対象ならではの解法などについて学習する。
【授業の到達目標】
（１) グラフの基本的事項について理解し、与えられたグラフが一筆書きできるかどうかや、彩色可能かどうかなどが定理に基づいて判定できる。 2) 帰納法な
どを用いて組み合わせ論的な議論ができる ３）グラフ上のランダムウォークについての基本的事項について理解し、与えられたグラフ上の推移確率が計算できる。
【授業概要（キーワード）】
グラフ、隣接行列、握手補題、次数、位数、大きさ、完全グラフ、２部グラフ、木、オイラーグラフ、ハミルトングラフ、ランダムウォーク、推移確率
【学生主体型授業（アクティブラーニング）について】
D-1．演習、実習、実験等を行う機会がある。：1～25％
【科目の位置付け】
ディプロマポリシー「2. 幅広い教養と汎用的技能：数学、物理学、化学、生物学、地球科学、情報科学などの理学全般にわたる科学・技術の基礎知識を身に付けている。」に則り、近年のデータサイエンスの目覚ましい発展に伴い、離散的対象の扱い方、解析の仕方を身に着ける。
【授業計画】
・授業の方法
最初にいくつかの例を交えてグラフ理論とはどのような学問であるかを簡単に説明する。その後それらを理解するために板書による講義および演習を行う。授業の動画をネットにアップし、状況に応じてオンラインでの受講も可能なかたちでおこなう。
・日程
第１回 授業全体の概要説明
第２回 グラフとは（ラベル無しグラフ、ラベル付きグラフ）
第３回 グラフの位数、大きさ、次数、握手補題
第４回 グラフの基本的事項に関する演習
第５回 グラフの同型、部分グラフ
第６回 同型かどうか、部分グラフかどうかの演習
第７回 中間まとめと補足
第８回 特別なグラフについて：２部グラフ、木
第９回 特別なグラフの判定法
第１０回 オイラーグラフ
第１１回 オイラーグラフの判定法
第１２回 確率論の復習１：確率空間
第１３回 確率論の復習２：確率変数、平均、分散
第１４回 ランダム・ウォーク
第１５回 まとめと補足
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
予備知識は仮定しないが、数学の基本的事項（集合論や記号などの使い方）についてはよく復習しておくこと。確率論の知識があると理解の援けになる。
・授業時間外学習（予習・復習）のアドバイス
講義で学習したグラフ理論の基本的事項について様々な例を用いてよく復習をし、離散的な対象の取り扱いになれるとよい。
【成績の評価】
・基準
グラフの基本的事項を理解し、グラフの基本的な量や性質について計算・判定できるかどうか、グラフ上のランダムウォークについて理解し、推移確率が計算できるかどうかが基準である。
・方法
授業中に課す演習レポートにより評価する。（オンラインでの提出も可にする予定）
【テキスト・参考書】
テキスト：指定しない
参考書：
R.J. ウィルソン著、 西関 隆夫訳「グラフ理論入門」近代化学社
熊谷隆「確率論」共立出版
【その他】
・学生へのメッセージ
数学は積み重ねの学問なのでわからないことがあったら本で調べたり、友人や先輩、先生に聞いたりして自分の中で納得がいくまで十分に考えることが大切である。
・オフィス・アワー
火曜日１２：００－１３：００．不在のことも多いので質問を希望する方はなるべく ishiwata@sci.kj.yamagata-u.ac.jp にメールをしてアポイントメントをとってください。
|