科目ナンバー

SG-AN5-1C28

履修条件・関連科目等

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

グラフ理論とグラフに関するアルゴリズムについて講義する.

科目目的

グラフ理論とそのアルゴリズムに関する基本的な事柄の習得を目標とする.

到達目標

グラフ理論とそのアルゴリズムに関する基本的な事柄の習得を目標とする.

授業計画と内容

第１回　最小重みの全域木
第２回　オイラーの公式
第３回　平面的グラフの判定
第４回　グラフの彩色
第５回　グラフの辺彩色
第６回　ネットワーク
第７回　流れのアルゴリズム
第８回　グラフの辺素な道と無向ネットワークにおける流れ
第９回　グラフの内点素な道
第10回　立方体グラフ
第11回　k-連結グラフの性質
第12回　結婚定理とその応用
第13回　グラフのマッチング
第14回　最大マッチングを求めるアルゴリズム

授業時間外の学修の内容

授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

授業中に出題する問題を解いてレポートとして提出したもので評価する.

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

その他

授業におけるICTの活用方法（その他の内容等）

数学科の計算機器

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

テキストは特に指定しない。
参考書
加納幹雄、情報科学のためのグラフ理論、朝倉書店、2001年、入門〈有限・離散の数学〉6、978-4-254-11424-9

その他特記事項

参考URL