グラフ理論 （社会情報・専門科目）

Graph Theory （社会情報・専門科目）

専門教育科目

−

社会情報科学部

3年

KCJBS3MCA1

2単位

講義 (Lecture)

2024年度後期

(Fall semester)

宮崎 修一

社会情報科学部

日本語

目標9

随時教員室に質問に来て構わないが、メール等で事前に予約を取るのが望ましい。

shuichi@sis.u-hyogo.ac.jp

3◎／2〇

ー

ー

ー

[講義目的]
グラフの基礎的概念とその性質や応用方法、またそれらに関連した基本的なアルゴリズムの動作原理を習得することを目的とする。

[到達目標]
上述したグラフの基礎的概念、その性質や応用方法、基本的なアルゴリズムの動作原理を他人に説明できるようになることを到達目標とする。

[講義内容]
本講義では、グラフ・ネットワークの基礎から解説し、最小全域木問題、最短経路問題、最大流問題といった通信ネットワークに関連する問題を取り上げる。また、グラフの基本的な問題であるハミルトン閉路、オイラー回路、頂点彩色、辺彩色、マッチング等についても述べる。

[講義計画]
1〜4．グラフの基礎
5．最小全域木
6．最短経路問題
7〜8．オイラー回路とハミルトン閉路
9〜10．グラフの彩色
11．最大流問題
12〜13．マッチング
14．関連トピックの紹介
15．総括

この授業ではパソコンは利用しない。ただし、配布されるスライドを閲覧するために必要な場合がある。

この授業では生成AI を利用しない。各自が自習の際に利用することは妨げないが、本学の指針（https://www.u-hyogo.ac.jp/topics/important/20230417/index.html）に沿うこと。

宮崎修一「グラフ理論入門 〜基本とアルゴリズム〜」(森北出版)

ISBN:978-4-627-85281-5

特になし。必要があれば授業中に紹介する。

事前学習：授業スライドを見て、講義内容を把握しておく。また、教科書の該当部分を読んでおく。これらの中で理解できない部分を把握しておく。1回あたり2時間程度。
事後学習：講義の内容を通して復習する。講義中に理解できなかった箇所があれば、そこを集中的に理解する。1回あたり2時間程度。

毎回の授業で演習問題を解く時間を設ける。その際、自分の解答を発表したり、他人の説明に対して質問するなど、ディスカッションをする機会を設ける。ディスカッションに積極的に参加すること。

[成績評価の基準]
講義目的・到達目標に記載した能力を身につけた者には、その到達度に基づき、S（90点以上）、A（80点以上）、B（70点以上）、C（60点以上）による成績評価のうえ、単位を付与する。

[成績評価の方法]
評価は期末試験（100%）により行なう。講義中に行う演習の受講度合いやディスカッションへの参加度などを考慮して加点する場合がある。

演習課題については授業中に解説する。
期末試験の内容について質問があれば、教員室等で対応する。（合否や点数などをフィードバックするものではない）

・特別な要件は設定しないが、「データ構造とアルゴリズム」、「数理モデリング」、「オペレーションズ・リサーチ」を事前に履修し習得ていることが望ましい。

該当しない。