シラバス | グラフ・ネットワーク理論

グラフ・ネットワーク理論

授業目的
情報科学や実社会において様々な数理モデルとして使用されるグラフ理論について，数学的な基本事項と代表的な命題を理解する．
到達目標
グラフに関する基本的な用語や性質を理解し，要求された問題をグラフを用いて表現できる．また，グラフに関する定理とその証明，アルゴリズムなどを理解し，それを用いて各種問題を解くことができる．

授業計画
第1回	オンライン授業（オンデマンド型）グラフの定義，次数【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第2回	部分グラフ，特徴的なグラフ【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第3回	連結性，距離，木【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第4回	連結度（1）低連結グラフの構造【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第5回	連結度（2）Mengerの定理，扇補題【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第6回	オイラー周遊【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第7回	ハミルトン道，ハミルトン閉路【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第8回	オンライン授業（オンデマンド型）有向グラフ【復習課題】60分　授業の内容を復習し，演習課題に取り組む．
第9回	マッチング（1）交互道，2部グラフにおけるマッチング【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第10回	マッチング（2）Tutteの定理【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第11回	平面グラフ【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第12回	彩色（1）Welsh-Pawellのアルゴリズム【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第13回	彩色（2）Brooksの定理，辺彩色【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第14回	彩色（3）四色問題【復習課題】60分　授業の内容を復習し，演習課題に取り組む．【予習課題】60分　次回の講義資料に目を通し，内容を確認する．
第15回	ラムゼー理論【復習課題】120分　授業の内容を復習し，授業中に終わらなかった演習課題に取り組む．また，本授業全体の復習を行い，演習課題を含めた内容の確認を行う．

＊＊こちらの内容は2026年4月1日を基準としたものです．最新のシラバス情報，詳細は大学提供のシラバス情報照会ページで確認してください＊＊