科目分野	理工学部
選必区分	選択
担当教員 ［ローマ字表記］	蓮沼　徹　[Toru Hasunuma]
授業形態	講義

授業の目的

　離散数学の範疇に属するグラフ理論，組合せ論は，離散構造をもつ対象への幅広い応用をもつことから，計算機科学（コンピュータサイエンス）と密接に関連している。グラフ理論，組合せ論の有用性を理解し，応用できる能力を身につけることを目標とする。

授業概要

　グラフ理論，組合せ論の諸概念，結果及び手法（各種全域木，連結度，オイラー閉路，ハミルトン閉路，平面グラフ，グラフ描画，グラフ彩色，因子分解，支配集合，数え上げ，母関数等）について応用を交え講述する。また，適宜演習を設け演習問題を通じて理解を深めさせる。

到達目標

　グラフ理論の諸概念（各種全域木，連結度，オイラー閉路，ハミルトン閉路，平面グラフ，グラフ描画，グラフ彩色，因子分解，支配集合）及び組合せ論の手法（数え上げ，母関数等）を理解する。

授業計画

第１回：グラフ
第２回：各種全域木
第３回：点連結度と辺連結度
第４回：オイラーグラフとハミルトングラフ
第５回：平面グラフ
第６回：本型埋め込み
第７回：キューレイアウト
第８回：点彩色と辺彩色
第９回：L(p,q)-ラベリング
第１０回：埋め込みと因子分解
第１１回：支配集合
第１２回：数え上げ
第１３回：母関数
第１４回：再帰関係
第１５回：包含排除の原理
定期試験

教科書

特になし

キーワード

グラフ