Graph Theory ｜ Syllabus data

Course Title

Graph Theory

Course Title in English

Graph Theory

Course Type

Major Courses

−

Eligible Students

School of Social Information Science

Target Grade

3Year

Course Numbering Code

KCJBS3MCA1

Credits

2.00Credits

The course numbering code represents the faculty managing the subject, the department of the target students, and the education category (liberal arts / specialized course). For detailed information, please download the separate manual from the upper right 'question mark'.

Type of Class

講義 (Lecture)

Eligible Year/Semester

Fall semester 2026

(Fall semester)

Instructor

宮崎修一

Affiliation

社会情報科学部

Language of Instruction

Japanese

Related SDGs

9

Office Hours and Location

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

Contact

shuichi@sis.u-hyogo.ac.jp

Corresponding Diploma Policy

A double circle indicates the most relevant DP number and a circle indicates the associated DP.

Corresponding Undergraduate School DP

3◎／2〇

Corresponding Graduate School DP

ー

Corresponding University-Wide DP

N/a

Academic Goals of Teacher Training Course

ー

Course Objectives and Learning Outcome

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

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

Subtitle and Keywords of the Class

Course Overview and Schedule

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

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

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

In-person/Remote Classification

In-person

Implementation Method and Remote Credit Limit Application

・対面授業のみ
・遠隔授業単位上限の適用を受けない

Uses of Generative AI

Limited permission for use

Precautions for using Generative AI

生成ＡＩの利用にあたっては『本学の教育における生成ＡＩの取扱いについて（学生向け）』の記載内容について留意すること。

この授業においては、授業内、予習復習等において生成ＡＩの利用を許可する。ただし、授業内で行う演習を解く際には生成ＡＩを利用してはならない（結果の確認には利用してよい）。
自習等において利用する場合、生成ＡＩによる出力結果を鵜吞みにせず自分で検証すること。
教員が認める範囲を超えて生成ＡＩを利用したことが判明した場合は、単位を認定しない、又は認定を取り消すことがある。

Textbook

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

ISBN:978-4-627-85281-5

References

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

Contents and Estimated Time for Pre- and Post- Learning (Preparation and Review)

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

Contents of Active Learning

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

Grading Criteria and Methods

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

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

How to Disclose Assignments and Exam Results

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

Precautions and Requirements for Course Registration

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

Practical Education

該当しない。

Remarks

In cases where any differences arise between the English version and the original Japanese version, the Japanese version shall prevail as the official authoritative version.