到達目標
1. グラフ理論の基礎を知る．
2. グラフ理論の応用例を提示することができる．
3. グラフ理論の応用例を提案することができる．
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 グラフ理論の基礎知識
| グラフ理論の用語・定理がわかり、基礎的な定理は証明することができる． | グラフ理論の用語・定理がわかる． | グラフ理論の用語・定理がわからない． |
| 評価項目2 応用例の提示
| グラフ理論の応用例を掲示することができ、その理由も詳細に説明することができる． | グラフ理論の応用例を掲示することができ、その理由も説明することができる． | グラフ理論の応用例を掲示することができない． |
| 評価項目3 応用例の提案 | グラフ理論の応用例が提案でき、その理由も詳細に説明することができる． | グラフ理論の応用例を提案することができる． | グラフ理論の応用例を提案することができない． |
学科の到達目標項目との関係
教育方法等
概要:
本講義では、グラフ理論を扱う．グラフ理論は、様々な工学分野に応用されている．
そこで、リベラルアーツ特論１では、工学に関連するグラフ理論の基礎知識を学習する．
授業の進め方・方法:
授業前半（45分程）では、講義形式で基礎的な知識の説明を行う．
授業後半（45分程）では、グループワーク形式で授業前半の内容の演習を行う．グループワーク活動での成果を受講生の前で発表してもらうことがある．
注意点:
1. この科目は通年科目である．
2. 欠席の場合は、必ず配布物などを各自手配し、次の授業までに前の授業内容を把握しておくこと．
3. 評価方法は下の「評価割合」の通りとし、60点以上を合格とする．
4. 授業は以前の内容を理解していることを前提で行うため，授業前までに前回の授業内容を復習しておくこと．
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス |
授業の内容、進め方を理解する．
|
| 2週 |
グラフと有向グラフ（集合・写像・関係） |
集合で利用する記号や全単射について知る．さらに、関係とは何かを理解する．
|
| 3週 |
グラフと有向グラフ（関係・有向グラフ・グラフ） |
同値関係や同値類を理解する．さらに、グラフとは何かを理解し、その基本的な性質を知る．
|
| 4週 |
グラフの連結性（グラフと有向グラフの連結性） |
初等的閉路の存在を示すことができる．
|
| 5週 |
グラフの連結性（部分グラフ・連結成分） |
部分グラフと連結成分について理解する．
|
| 6週 |
オイラー路とハミルトン路（オイラー路） |
与えられたグラフにオイラー路が存在することを示すことができる．
|
| 7週 |
オイラー路とハミルトン路（ハミルトン路） |
与えられたグラフがハミルトングラフであることを示すことができる．
|
| 8週 |
木と有向木（木・全域木） |
木や全域木の性質を理解する．
|
| 2ndQ |
| 9週 |
木と有向木（全域木の数・有向木） |
完全グラフの異なる全域木の数を示すことができる．さらに、有向木の有向辺の数に関する性質を理解する．
|
| 10週 |
グラフの行列表現（接続行列） |
与えられたグラフから接続行列を求めることができる．さらに、与えられた接続行列からグラフを図示することができる．
|
| 11週 |
グラフの行列表現（接続行列の階数） |
様々なグラフの接続行列の階数に関する性質を知る．
|
| 12週 |
独立集合と2部グラフ（独立集合と被覆・２部グラフ） |
独立集合と２部グラフに関する性質を理解する．さらに、グラフが２部グラフであるための必要十分条件を知る．
|
| 13週 |
独立集合と2部グラフ（マッチング・辺被覆） |
マッチング数を求めることができる．さらに、２部グラフやそのほかのグラフのマッチング数と被覆数の関係を知る．
|
| 14週 |
グラフの彩色（点彩色） |
与えられたグラフの点彩色数を求めることができる．さらに、点彩色数の性質を理解する．
|
| 15週 |
グラフの彩色（辺彩色） |
与えられたグラフの辺彩色数を求めることができる．さらに、辺彩色数の性質を理解する．
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 試験 | 発表 | レポート | 学習の成果物 | 態度 | その他 | 合計 |
| 総合評価割合 | 0 | 50 | 20 | 20 | 10 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 10 | 0 | 10 |
| 専門的能力 | 0 | 50 | 20 | 20 | 0 | 0 | 90 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |