ネットワーク・グラフ論

科目基礎情報

学校	釧路工業高等専門学校	開講年度	令和08年度 (2026年度)
授業科目	ネットワーク・グラフ論
科目番号	0057	科目区分	専門 / 必修
授業形態	講義	単位の種別と単位数	学修単位: 2
開設学科	情報工学分野	対象学年	3
開設期	後期	週時間数	2
教科書/教材	教科書：データ構造とアルゴリズム 五十嵐 数理工学社，参考書：アルゴリズムとデータ構造 平田 森北出版，参考書：アルゴリズムの基礎 岩野 朝倉出版 自学自習用問題集：データ構造とアルゴリズム 五十嵐 数理工学社
担当教員	本間 宏利

到達目標

・グラフ構造の名称や基本的な特性について理解できる．各グラフの描写ができる．
・グラフ，ネットワークが数理問題のモデル化ツールとして応用されることが説明できる．
・最短経路問題，木構築問題，彩色問題などに関する定理や解法を説明できる．

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	グラフ構造の名称や基本的な特性について説明できる．各グラフの描写ができる．	グラフ構造の名称や基本的な特性について説明できる．	グラフ構造の基本的な特性について説明できない．
評価項目2	グラフやネットワークを数理問題のモデル化ツールとして応用することができる．	グラフやネットワークが数理問題のモデル化ツールとして応用されることを説明できる．	数理問題のモデル化という概念が説明できない．
評価項目3	最短経路問題，木構築問題，彩色問題に関する定理，解法，計算コストを説明できる．	最短経路問題，木構築問題，彩色問題に関する定理・解法を説明できる．	最短経路問題，木構築問題，彩色問題の解法が説明できない．

学科の到達目標項目との関係

ディプロマ・ポリシー C （（技術的課題を解決できるように）工学の幅広い基礎知識（数学，自然科学，情報技術，基礎工学）を修得し，それらを応用する能力を身につける。）

教育方法等

概要:

この講義の目標はソフトウエア開発やプログラミングにおいて，ソフトウエア化の対象となる実モデルや関係をグラフツールを用いて定式化，解析する能力や，その問題に最適なデータ構造とアルゴリズムの構築を行える能力の習得することである．

授業の進め方・方法:

前関連科目：アルゴリズム論
後関連科目：自然言語処理
プレゼンスライドと黒板板書の両方を使った講義形式でおこなう．
小セクションごとに演習問題を与える．

成績評価方法：
定期試験2回の成績で行う．
中間試験(50%)，期末試験(50%)
合否判定：最終評価60点以上を合格とする．
再試合否：再試験の点数が60点以上を合格とし評点を60点とする．
中間評価：中間試験の評価とする．
学修単位科目のため，事前・事後学習として課したポートフォリオを必ず提出すること．

注意点:

基本的な離散数学・数論アルゴリズムの知識が必要である．
手続き型のプログラミング言語についての知識を習得していると望ましい．
講義は基本的にプロジェクタを利用して行う．
本科目は「授業時間外の学修を必要とする科目」である．授業時間外の学修（準備学習を含む）については科目担当教員から指示するので，必ず予習・復習等をおこなうこと．
事前に行う準備学習：各回の講義内容の復習をおこなうこと．

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	グラフ理論概論基礎 1	グラフ理論における用語や定義を説明できる．
		2週	グラフ理論概論基礎 2	同形の意味や除去，縮約等の操作を説明できる．
		3週	グラフ理論概論基礎 3	グラフの形状やその特性について説明できる．
		4週	パスとサイクル 1	歩道，小道，道，カット，橋の定義を説明できる．
		5週	パスとサイクル 2	オイラーグラフの必要十分条件を説明できる.
		6週	パスとサイクル 3	ハミルトン問題の困難性を説明できる.
		7週	パスとサイクル 4	最短経路問題，郵便配達員問題の解を導出できる.
		8週	中間試験	これまでの学習の理解度を深める．
	4thQ
		9週	木構造 1	基本的な木構造の特性を説明できる．
		10週	木構造 2	深さ優先探索木，幅優先探索木を構築できる．
		11週	木構造 3	最小全域木問題の導出や電気回路解析ができる．
		12週	平面グラフ 1	平面グラフの特性や，その応用例を説明できる．
		13週	平面グラフ 2	平面グラフに関する様々な定理を説明できる．
		14週	グラフの彩色 1	彩色問題の困難性やBrooksの定理を説明できる．
		15週	グラフの彩色 2	面辺彩色の特性やVizingの定理を説明できる．
		16週	期末試験	この講義の理解度・目標達成度を確認するため，試験を実施する．

評価割合

	試験	発表	相互評価	態度	ポートフォリオ	その他	合計
総合評価割合	100	0	0	0	0	0	100
専門的能力	100	0	0	0	0	0	100