シラバス参照

講義概要/Course Information
2024/03/28 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
グラフとネットワーク
英文授業科目名
/Course title (English)
Graphs and Networks
科目番号
/Code
開講年度
/Academic year
2015年度 開講年次
/Year offered
3
開講学期
/Semester(s) offered
前学期 開講コース・課程
/Faculty offering the course
情報理工学部
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講類・専攻
/Cluster/Department
情報・通信工学科
担当教員名
/Lecturer(s)
岡本 吉央
居室
/Office
西4-206
公開E-mail
/e-mail
okamotoy の後に @uec.ac.jp
授業関連Webページ
/Course website
http://dopal.cs.uec.ac.jp/okamotoy/lect/2015/gn/
更新日
/Last update
2015/03/05 06:45:02 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標(2,000文字以内)
/Themes and goals(up to 2,000 letters)
主題:離散最適化の入門として,グラフとネットワークを用いた数理モデル化,および,アルゴリズム的解法の背後にある数理を概説する.
キャッチフレーズは「本当の離散数学がここから始まる」.

達成目標:以下の4項目をすべて達成することを目標とする.
(1) グラフやネットワークに関する用語を正しく使うことができる.
(2) 現実世界の諸問題をグラフやネットワークで表現し,数理モデルを構築できる.
(3) アルゴリズム的解法の背後にある数理,特に,最小最大定理の重要性を説明でき,それを用いて最適性の証明ができる.
(4) グラフとネットワークに関する簡単な数学的事実を証明できる.
前もって履修
しておくべき科目(1,000文字以内)
/Prerequisites(up to 1,000 letters)
離散数学,プログラミング通論
前もって履修しておくこ
とが望ましい科目(1,000文字以内)
/Recommended prerequisites and preparation(up to 1,000 letters)
なし
教科書等(1,000文字以内)
/Course textbooks and materials(up to 1,000 letters)
教科書:指定しない.講義資料を毎回用意するので,講義webページより各自入手すること.

参考書:
藤重悟,「グラフ・ネットワーク・組合せ論」,共立出版,2002
繁野麻衣子,「ネットワーク最適化とアルゴリズム」,朝倉書店,2010
R.J. ウィルソン (著),西関隆夫,西関裕子 (訳),「グラフ理論入門 原書第4版」,近代科学社,2001.
授業内容と
その進め方(2,000文字以内)
/Course outline and weekly schedule(up to 2,000 letters)
(a)授業内容
第1回 グラフの定義と次数:数理
第2回 道と閉路:数理
第3回 木:数理
第4回 全域木:数理とモデル化
第5回 マッチング:数理
第6回 マッチング:モデル化
第7回 最大流:数理
第8回 まとめ1
第9回 最大流:モデル化 (1)
第10回 最大流:モデル化 (2)
第11回 彩色:数理
第12回 彩色:モデル化
第13回 平面グラフ:数理
第14回 平面グラフ:モデル化
第15回 まとめ2

(b)授業の進め方
はじめの75分に講義を行い,最後の15分で演習を行う.
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)(1,000文字以内)
/Preparation and review outside class(up to 1,000 letters)
演習問題を解き,レポートとして提出することを推奨する.(なお,レポートは成績評価に勘案されない.)
成績評価方法
および評価基準
(最低達成基準を含む)
(1,000文字以内)
/Evaluation and grading
(up to 1,000 letters)
評価方法:中間試験と期末試験による.試験日程は講義中に連絡する.
評価基準:以下の到達レベルをもって合格の最低基準とする.
(1) グラフやネットワークに関する用語を正しく使うことができる.
(2) 現実世界の諸問題をグラフやネットワークで表現し,数理モデルを構築できる.
(3) アルゴリズム的解法の背後にある数理,特に,最小最大定理の重要性を説明でき,それを用いて最適性の証明ができる.
(4) グラフとネットワークに関する簡単な数学的事実を証明できる.
ただし,用語を暗記する必要はない.
オフィスアワー:
授業相談(1,000文字以内)
/Office hours(up to 1,000 letters)
初回の講義で指示する
学生へのメッセージ(1,000文字以内)
/Message for students(up to 1,000 letters)
3年後学期に開講される「数理計画法」は本講義の内容と深く関係している.
そのため,「数理計画法」を受講する予定の学生はこの講義も受講することが強く望まれる.
また,3年前学期に開講される「アルゴリズム論第一」や「オートマトン理論」,さらに,3年後学期に開講される「アルゴリズム論第二」,「離散数理工学」,「計算理論」にも関わっているので,それらを受講する予定の学生もこの講義を受講することを推奨する.
その他
/Others
情報・通信工学科で開講されていた「数理解析」を履修したものは,この科目を履修できないので,注意する.
キーワード
/Keywords
グラフ,ネットワーク,道,閉路,木,最大流,最小カット,マッチング,頂点被覆,彩色,染色数,クリーク,平面グラフ,オイラーの公式