トップ カリキュラム・授業 グラフ・ネットワーク理論



授業科目名 グラフ・ネットワーク理論
　 履修期 秋   2単位   履修基準年度 2年
担当者 加藤　直樹（KATOH NAOKI）
授業目的 / Course Objectives
グラフ理論とネットワーク理論から、基礎的かつ重要な話題を選んで、数学的理解を図ると共に、代表的なアルゴリズムを紹介する。これらは情報科学のあらゆる分野で必要とされる基礎知識であるので、本講義を通じて理解を深めておくことが求められる。
到達目標 / Attainment Objectives

授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.)
離散数理を履修しておくことが望ましい。
授業計画 / Class Overall Plan
１．序論：グラフとネットワークの理論
２．グラフの用語と基礎的事項
３．最短路問題１
４．最短路問題２
５．最小木アルゴリズム
６．ネットワークフロー
７．最大フロー問題
８．最大フローと最小カット
９．最小費用問題
１０．マッチング問題
１１．施設配置問題１
１２．施設配置問題２
１３．巡回セールスマン問題
１４−１５．演習
教科書 / Textbook(s)
加藤直樹「数理計画法」（コロナ社　２００８）
参考文献 References Books
斎藤・西関・千葉「離散数学」（朝倉書店　１９８９）
授業方法 / Method of Instruction
講義形式で行う
学生による授業評価の方法 / Course Evaluation by Students
ネット利用(所定のフォーマット)
成績評価 / Evaluation Criteria/Method
定期試験(Final examination)/平常リポート(Ordinary paper)
備考 / Note

検索キーワード / Keywords
グラフ/ネットワーク/アルゴリズム/平面グラフ/最小木/最短路/彩色/ネットワークフロー/マッチング

ページトップへ ▲