文理学部シラバスTOP > 文理学部 > 数学科 > 数学序論１
日本大学ロゴ

数学序論１

このページを印刷する

令和６年度以前入学者 数学序論１
教員名 斎藤明
単位数    2 学年    2 開講区分 文理学部
科目群 数学科
学期 前期 履修区分 選択
授業形態 対面授業
授業の形態 対面授業 : Zoomやオンデマンド教材での対応はしない。
やむを得ない事情で授業を欠席するときには、担当教員に申し出ること。申し出た受講者には、当該授業を課題学習するための教材を与え、指導、助言を行う。
授業概要 いくつかの点とそれらを結ぶ線からなる構造をグラフという。グラフはインターネット、電話回線網、物流ネットワークなどを調べるために利用される数理モデルである。グラフの性質を調べる理論をグラフ理論とよぶ。グラフには様々な工学的応用があるが、その一方で興味深い理論的テーマも数多くある。本講義ではグラフ理論に関する各種の概念とテーマを学ぶ。
授業のねらい・到達目標 ＜授業のねらい・到達目標＞
グラフの用語や概念に関する知識を身につける。実用的な問題をグラフで数理モデル化し、問題解決をすることができる。

＜ディプロマポリシーとの関係＞
この科目は文理学部（学士（理学））のディプロマポリシー DP3,4,6,8 及びカリキュラムポリシー CP3,4,6,8に対応しています。

＜日本大学教育憲章との関係＞
・数理科学に基づいて学んだ知識をもとに、物事の本質を論理的、客観的に捉えることができる(A-3-2)。
・日常生活における現象に潜む数理科学的問題を発見し、内容を説明することができる(A-4-2)。
・親しい人々とコミュニケーションを取り、自分の考えを説明することができる(A-6-2)。
・A-8-2：自分の学修経験の振り返りを継続的に行い、分析することができる(A-8-2)。
授業の形式 講義、演習
授業の方法 対面授業を行う。各話題ごとにそれがどのような工学的な応用をもつかを提示し、学習の動機づけを行う。その後グラフ理論おける理論的、応用的側面をバランス良く解説する。
講義の中で授業内演習を課しその場で解法を説明する。授業の各回に宿題を課し、添削後返却する(フィードバック方法)。
期末試験は15回の講義とは別に日時を設定する。試験時間は150分を予定している。
授業計画
1 グラフを使ってパズルを解こう：グラフを使って１つのパズルを解く。この例を通してグラフの感覚的な理解を促し、同時に本講義受講の動機付けを行う(A-3, A-4)。
【事前学習】インターネットで「グラフ」、「グラフ理論」という用語を検索し、それらの意味を自分なりの解釈でまとめてみる(A-4, A-6)。 （2時間）
【事後学習】講義で取り上げたパズルについて講義時とは異なる問題を課すので、それを解く(A-3, A-4)。 （2時間）
【授業形態】対面授業
2 グラフの定義と基本的な用語：数理モデルとしてのグラフの定義を与え、前回講義で感覚的に理解したグラフを数学的対象として取り扱うための基礎を学ぶ。またグラフに関する基本的な用語と概念を学ぶ(A-3)。
【事前学習】前回の授業で視覚的に理解したグラフを数学の言葉で記述する方法について、自分なりの考えをノートにまとめる(A-4, A-6)。 （2時間）
【事後学習】位数、サイズ、グラフと多重グラフ、次数などの用語に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
3 次数と握手定理、いろいろなグラフ：グラフの次数の概念を学び、握手定理を理解する。またグラフ理論に現れる有名なグラフについて、その定義と性質を学ぶ(A-3)。
【事前学習】先行して渡す本講義のレジメに目を通し、次数、握手定理、完全グラフ、２部グラフなどの用語の事前理解を試みる。不明な点をノートにまとめる(A-4, A-6)。 （2時間）
【事後学習】次数と握手補題、各種グラフの性質に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
4 ウォーク、パス、回路、サイクルなど、グラフ内の頂点列に関する概念を学ぶ。また連結グラフの定義と性質を学習し、連結グラフのサイズの下界を考察する(A-3)。
【事前学習】先行して渡す本講義のレジメに目を通し、ウォーク、パス、回路、サイクルなどの概念の事前理解を試みる。不明な点をノートにまとめる(A-4, A-6)。 （2時間）
【事後学習】連結性に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
5 グラフの最短路問題：グラフとその中の２頂点が与えられたとき、これらの２頂点間の最短パスを求める問題を最短路問題とよぶ。最短路問題とその代表的解法であるダイクストラ法を学ぶ(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、最短路問題とダイクストラ法の事前理解を試みる。不明な点をノートにまとめる(A-4, A-6)。 （2時間）
【事後学習】事後学習教材として課すダイクストラ法の問題を解く(A-3, A-4, A-8)。 （2時間）
【授業形態】対面授業
6 ダイクストラ法の原理とそのアルゴリズムの正当性を解説する。また連結度の概念を学ぶ(A-3, A-4)。
【事前学習】事前学習用の教としてやや規模の大きいダイクストラ法の問題を課すので、それを解く(A-3, A-8)。 （2時間）
【事後学習】連結度と辺連結度に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
7 オイラー回路、ハミルトンサイクル：与えられたグラフの全ての辺を通る回路をそのグラフのオイラー回路、全ての頂点を通るサイクルをハミルトンサイクルとよぶ。与えられたグラフにオイラー回路が存在するための必要十分条件（オイラーの定理）とハミルトンサイクルが存在するための十分条件を学ぶ(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、オイラー回路とハミルトンサイクルの違いについての事前理解を試みる。不明な点をノートにまとめる(A-3, A-4, A-6)。 （2時間）
【事後学習】オイラー回路とハミルトンサイクルに関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
8 総合演習：第１回から第７回までに学習した内容について試験形式で演習を行う。演習終了後に問題の解説を行う(A-3, A-8)。
【事前学習】第１回から第７回までに学習した内容について復習する(A-3, A-8)。 （3時間）
【事後学習】総合演習で出題された問題を解き直す(A-3, A-8)。 （1時間）
【授業形態】対面授業
9 グラフ上の距離と距離を用いて定義されるグラフの直径、半径、中心、周辺などの概念を学ぶ。また木の定義と基本的な性質を学ぶ(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、グラフの半径、直径に関する内容の事前理解を試みる。不明な点をノートにまとめておく(A-4, A-8)。 （2時間）
【事後学習】グラフの直径と半径、木の性質に関する事後学習用演習問題を解く(A-3, A-4, A-8)。 （2時間）
【授業形態】対面授業
10 木の性質に関する発展的内容、特にラベル木に関するプリューファーの変換と逆変換のアルゴリズムを学ぶ。
【事前学習】先行して渡す本講義のレジメに目を通し、プリューファーのアルゴリズムについて事前理解を試みる。不明な点をノートにまとめておく(A-4, A-6)。 （2時間）
【事後学習】プリューファーのアルゴリズムに関する事後学習問題を解く(A-3, A-6)。 （2時間）
【授業形態】対面授業
11 ネットワークにおける最大流と最小カットの概念を学び、最大流を求めるアルゴリズムを理解する(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、最大流と最小カットの概念やそれらの求め方について事前理解を試みる。不明な点をノートにまとめておく(A-4, A-6)。 （2時間）
【事後学習】最大流と最小カットを求める事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
12 グラフの平面性の概念を学び、オイラーの公式とクラトフスキーの定理を理解する(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、グラフの平面性に関する事前理解を試みる。特に「平面的グラフ」と「平面グラフ」の違いについて理解を試み、不明な点をノートにまとめる(A-4, A-6)。 （2時間）
【事後学習】オイラーの公式に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
13 グラフのマッチングの定義とその性質を学ぶ。２部グラフにマッチングが存在するための必要十分条件（ホールの定理）を理解する(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、グラフのマッチングに関する事前理解を試みる。特に講義に現れる「交互道」の概念について理解を試み、不明な点をノートにまとめる(A-3, A-6)。 （2時間）
【事後学習】マッチングに関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
14 一般のグラフに完全マッチングが存在するための必要十分条件(タットの定理)を学ぶ(A-3, A-4)。
【事前学習】先行して渡す本講義のレジメに目を通し、タットの定理の事前理解を試みる。特に比較的簡単な必要性の証明についてその理解を試みる(A-3, A-6)。 （2時間）
【事後学習】タットの定理に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
15 グラフの彩色、辺彩色の定義と性質を学ぶ。
【事前学習】先行して渡す本講義のレジメに目を通し、グラフの彩色、辺彩色についての事前理解を試みる。特にブルックスの定理とビジングの定理の理解を試みる。不明な点をノートにまとめておく(A-3, A-8)。 （2時間）
【事後学習】ブルックスの定理とビジングの定理に関する事後学習用演習問題を解く(A-3, A-8)。 （2時間）
【授業形態】対面授業
その他
教科書 教科書は使用しない。
参考書 加納幹雄 『情報科学のためのグラフ理論 （入門有限・離散の数学）』 朝倉書店 2001年 第1版
成績評価の方法及び基準 試験(45%)、レポート:毎回の宿題(30%)、授業内テスト:第８回の総合演習(25%)
宿題の評価30％のうち、15％を答案提出の回数、15％を提出された答案の質に充てる。
オフィスアワー 初回の講義の際に知らせる。

↑このページのトップ