グラフ理論とネットワーク

　グラフとは物事の結び付きを抽象化した概念であり，構造をもつ多くの問題がグラフを用いて表現され，グラフ理論の手法を用いて解かれる．グラフ理論は，情報工学における不可欠な科目であると同時に，ネットワーク分野でも重要な基礎科目の一つである．当科目では，グラフの定義や基本問題，ネットワークにおける諸問題を扱うと同時に，これらの問題をコンピュータを用いて解決するための表現方法などを講義する．また，必要に応じて演習を行うことで，実際のプログラミング技術を身につける．

授業内容

1. グラフの定義
2. グラフの構造
3. グラフの行列表現
4. 演習１
5. グラフの連結性と連結度
6. オイラーグラフとハミルトングラフ
7. 演習２
8. グラフの探索
9. 最短経路と最小全域木
10. 演習３
11. ネットワークと最大フロー
12. 演習４
13. 彩色問題
14. 演習５
15. 期末試験

評価方法

期末試験と演習レポートにより評価する．評価の割合等，具体的な内容については授業中に説明する．

開講部	システム工学部
開講学科	電子情報システム学科
開講学年	3年次
開講時期	前期
単位数	2
単位区分	選択
系列区分	専門
講義区分	講義

P0700300

授業の教育目的及び方針

授業内容

評価方法

教科書

備考

環境との関連