山口大学教務システム - 1042220031-グラフ理論

開講年度	開講学部等
2025	理学部
開講学期	曜日時限	授業形態	AL（アクティブ・ラーニング）ポイント
後期	水3～4	講義	4.0
時間割番号	科目名[英文名]			使用言語	単位数
1042220031	グラフ理論[Graph Theory]			日本語	2
担当教員（責任）[ローマ字表記]					メディア授業
谷合由章					ー
担当教員[ローマ字表記]
谷合由章, 葛崎偉　[KATSU Kii]
特定科目区分		対象学生	物理・情報科学科所属学生対象	対象年次	2～4
ディプロマ・ポリシーに関わる項目			カリキュラムマップ(授業科目とDPとの対応関係はこちらから閲覧できます)

授業の目的と概要

グラフの基本定義，性質から，通信ネットワークにおける経路決定問題とそのアルゴリズムまで講義する．

授業の到達目標


グラフ・ネットワークの理論、またそれに基づいたネットワーク問題のモデル化とその解決のためのアルゴリズムの設計についての基礎的知識を習得し，論理的に思考できる。システムをモデル化するためのグラフの選別し、アルゴリズムを設計できる

授業計画

【全体】

本授業は，週単位の計画に従って実施していく．

	項目	内容	授業時間外学習	備考

第1回	基礎的事項のまとめ	本講義の概要および進め方	次回内容の予習（学修時間の目安:４時間以上）

第2回

グラフの基本定義

・グラフの構成要素
・諸定義
・例

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第3回

道と閉路(1)

・歩道・小道・道の定義
・グラフの連結性
・閉路

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第4回

道と閉路(2)

・オイラーグラフ
・ハミルトングラフ
・最短経路

宿題として，「道と閉路」をまとめることおよび次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第5回

木グラフ

・木の定義
・木の性質
・最小全域木

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第6回

グラフの平面性(1)

・平面グラフ
・平面的グラフ
・平面的グラフの性質

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第7回

グラフの平面性(2)

・オイラーの公式
・双対グラフ

宿題として，「木グラフとグラフの平面性」をまとめることおよび次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第8回

グラフの彩色(1)

・面彩色の定義
・地図の彩色

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第9回

グラフの彩色(2)

・点彩色の定義
・点彩色の性質

宿題として，「グラフの彩色」をまとめることおよび次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第10回

有向グラフ(1)

・有向グラフの定義
・強連結性

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第11回

有向グラフ(2)

・オイラー有向グラフ
・最長経路

宿題として，「有向グラフ」をまとめることおよび次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第12回

マッチング

・マッチングの定義
・結婚問題への応用
・完全マッチング

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第13回

ネットワークフロー

・ネットワークフローの定義
・最大フロー最小カット定義
・最大フローの求め方

宿題として，「マッチングとネットワークフロー」をまとめることおよび次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第14回

AIによるネットワークの経路決定

・通信経路のモデリング
・最適ルーティング
・機械学習によるルーティング決定

今回内容の復習および次回内容の予習（学修時間の目安:４時間以上）

グループワーク/演習を実施

第15回

総括

本講義のまとめ

全般内容のまとめ（学修時間の目安:４時間以上）

グループワーク/演習を実施

第16回

学修評価

期末試験

全般内容の復習（学修時間の目安:４時間以上）

※AL（アクティブ・ラーニング）欄に関する注
・授業全体で、AL（アクティブ・ラーニング）が占める時間の割合を、それぞれの項目ごとに示しています。
・A〜Dのアルファベットは、以下の学修形態を指しています。
【A：グループワーク】、【B：ディスカッション・ディベート】、【C：フィールドワーク（実験・実習、演習を含む）】、【D：プレゼンテーション】

A: 20%　B: --%　C: 20%　D: --%

成績評価法

レポート、学期末の筆記テストで評価します。
レポート　20％、学期末の筆記テスト　80％

教科書にかかわる情報

教科書	書名	グラフ理論入門				ISBN	9784764902961
教科書	著者名	R.J. ウィルソン著 ; 西関隆夫, 西関裕子共訳	出版社	近代科学社				出版年	2001

備考

参考書にかかわる情報

備考

必要とする場合は教員が指定する．

メッセージ

キーワード

道と閉路，木グラフ，グラフの平面性，彩色問題，有向グラフ，ネットワークフロー

持続可能な開発目標（SDGs）

(教育)すべての人に包摂的かつ公正な質の高い教育を確保し、生涯学習の機会を促進する。

(インフラ、産業化、イノベーション)強靱（レジリエント）なインフラ構築、包摂的かつ持続可能な産業化の促進及びイノベーションの推進を図る。

(持続可能な都市)包摂的で安全かつ強靱（レジリエント）で持続可能な都市及び人間居住を実現する。

メディア授業