シラバス参照

印刷
講義名 グラフ理論
代表ナンバリングコード BII3IT013C
講義開講時期 前期 講義区分 講義
基準単位数 2
受講定員の有無 なし
授業公開 科目等履修・聴講
履修年次 ３・４年次
2024年度カリキュラム　ナンバリング

担当教員
氏名
◎ 渡邉　扇之介

到達目標 ・組合せ論と数え上げに関する理論を理解し、具体的な問題に対する解を求めることができる。
・グラフの特徴的な問題の数理を理解し、具体的な問題に対する解を求めることができる。
・グラフ上の最適化問題の数理を理解し、対応するアルゴリズムによって具体的な問題の解を求めることができる。
授業概要 頂点と呼ばれる点の集合と2つの頂点を結ぶ辺と呼ばれる集合によって描かれる図形をグラフといい、様々な条件や目的に対してグラフが有する構造を調べる数学分野をグラフ理論という。グラフ理論はその数学的興味からくる数学研究のみならず、最適化問題やネットワークと幅広い応用研究に用いられ、情報科学においても基礎理論と応用理論の両面において重要な役割をもつ。
本講義では、グラフのような離散的な構造を扱うために必要な数学的な道具を準備したのち、グラフ理論で考えられている特徴的な問題に対する数理と解法アルゴリズムを紹介する。また、具体的なグラフ上の最適化問題も扱い、その組合せ論的な解法アルゴリズムについても解説を行う。
授業計画
回授業内容
第1回導入：離散数学とは何か
第2回組合せ論と数え上げ1：順列・組合せ・母関数
第3回組合せ論と数え上げ2：単射の数え上げ
第4回組合せ論と数え上げ3：全射の数え上げとスターリング数
第5回組合せ論と数え上げ3：ポリアの数え上げ定理
第6回グラフ理論入門：グラフの諸定義とオイラーの一筆書き定理
第7回グラフ理論における特徴的な問題1：木の数え上げ
第8回グラフ理論における特徴的な問題2：平面的グラフと彩色問題
第9回小テストと解説
第10回グラフ上の最適化問題1-A：最大マッチング問題
第11回グラフ上の最適化問題1-B：最大マッチング問題の解法アルゴリズム
第12回グラフ上の最適化問題2-A：最短経路問題
第13回グラフ上の最適化問題2-B：最短経路問題の解法アルゴリズム
第14回グラフ上の最適化問題3-A：最大流問題
第15回グラフ上の最適化問題3-B：最大流問題の解法アルゴリズム
準備学習（予習・復習等）の内容とそれに必要な時間 （毎回の授業前に行うべき予習）
事前にwebclassで配られる事業資料に目を通しておくこと。（60分）
写像や関数の扱いに不安がある者は、線形代数の学習（復習）を合わせて行うこと。

（毎回の授業終了後に行うべき復習）
教科書やノートをよく読み直し、わからない点を明らかにして教員や友人に質問すること。
演習課題が出た際は取り組むこと。（60分）

（その他）
様々な離散数学における問題に対して解を求めるための公式や組合せ論的なアルゴリズムを示す。サイズの小さい問題を手で計算できることは重要である一方で、プログラムを作成することもまた重要である。意欲的な者は、学んだ解法を自分で実装することにも挑戦してほしい。
評価方法（割合） 小テスト：30％
定期試験：60％
課題：10％
課題（試験やレポート等）に対するフィードバックの方法 授業中の演習課題により理解度を確認のうえ、次の授業でコメントし、授業内容に反映させる。
テキスト 授業資料をwebclassで配布する。
参考書・参考資料等 浅野孝夫、離散数学－グラフ・束・デザイン・離散確率－、サイエンス社、2010
猪股俊光・南野謙一、情報系のための離散数学、共立出版、2020
茨木俊秀、AI時代の離散数学、オーム社、2020
メッセージ ある条件をみたす解を見つけたり全て列挙することは、身の回りや社会に出てからも頻出する問題です。体力では解決できない規模の問題に対して数学がどのようにアプローチするかを楽しんでほしいと思います。
教員との連絡方法 sewatana（ａｔ）fukuchiyama.ac.jp までメールください。数学的な内容の質問はメールでは難しいかと思いますので、直接私の教員室まで来ていただければと思います。その際も事前にメールにてアポイントメントを取っていただければ確実です。
備考 講義中、特段の理由がない限り私語、飲食、着帽、無断退室、携帯電話の操作を慎むこと。授業計画の順序や学習内容の配分は変更の可能性がある。
他科目との関係性 【背景】記号化された情報を扱う計算機科学において、離散状態を対象とした離散数学はその基礎をなしている。本科目ではグラフ構造を中心に、数え上げなどに関わる数学的手法を学ぶ。
【関連】学んだ理論を実践的に必要とする計算機科学関連の科目、特に「アルゴリズム論」を履修していることが望ましい。「情報ネットワーク」の信頼性、「情報セキュリティ」における暗号なども、その基礎は「離散数学」であたえられるので、これらの科目との関連を踏まえて学ぶと効果的である。
卒業認定・学位授与方針との関連
◎特に関係性が深い、○関係性が深い
関連性
情報学実践の基盤となる堅固な基礎学力、基礎技術力を持つ
○
地域の現実のデータを収集・分析し、地域社会の持続と発展のためのシナリオ作成と評価ができる
情報システムやアプリケーションの開発等により、地域社会を支える情報基盤を構築できる
◎
人工知能技術やエンタテインメント技術を用いて、地域社会を豊かにできる
情報学の知見や技術を応用・活用して、公共経営、企業経営、交流観光、医療福祉、防災等のまちづくりに貢献できる
評価基準
列1
秀
具体的な問題の数学的構造について説明することができ、適切な方法で解を求めることができる。
優
具体的な問題の数学的構造についてある程度説明することができ、適切な方法で解を求めることができる。
良
具体的な問題の数学的構造についてある程度説明することができ、いくつかの問題に対しては適切な方法で解を求めることができる。
可
限られた問題の数学的構造について説明することができ、適切な方法で解を求めることができる。
不可
問題の数学的構造を説明することができず、解を求めることもできないができる。
放棄
課題を提出せず、試験も受験していない。