離散数学特論

Topics in Discrete Mathematics

991JB02

14MAAPM509

小谷　佳子

Keiko Kotani

2026年度後期

2026年度

②Second semester

火曜4限

Tuesday, 4th Period

理学研究科　応用数学専攻

Department of Applied Mathematics, Graduate School of Science

2.00単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

グラフ理論について学習する．
Students will learn about graph theory.

グラフ理論における議論が理解できるようになる．
Students will become able to understand arguments in graph theory.

グラフ理論における定理の証明ができるようになる．
Students will acquire the ability to prove theorems in graph theory.

有限集合の部分集合の基本的な性質についての知識が必要である．
Students need to have knowledge about basic properties of subsets of finite sets.

-

-

１個の定理の証明を完了するのに２回以上の授業を要することがあるので，前回までの授業の理解を確実にしておくことが大切である．
It sometimes takes two or more lectures to complete the proof of a theorem. Thus it is
important to make sure of the understanding of what was proved in earlier lectures.

成績は提出するレポートに基づいて決定される．
Students' grades are determined based on the papers they turn in (assignments will be specified in the class).

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://gomykits.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://gomykits.kinokuniya.co.jp/tokyorika/

Graph Theory 6th Edition  (Graduate Texts in Mathematics)・Reinhard Diestel・Springer・2024・978-3662701065

コースライセンス購入したpdfファイルを配布します
We will distribute the PDF file of the purchased course license

本科目は原則として全ての講義回を対面講義として実施する対面授業科目である

1. 基礎概念: 頂点，辺，頂点の次数，道，閉路を学ぶ
1. Basic concepts: vertices, edges, the degree of a vertex, paths, cycles

2. 基礎概念: 連結度，辺連結度，木，林を学ぶ
2. Basic concepts: paths, cycles, connectivity, edge-connectivity, trees, forests

3. 基礎概念: ２部グラフ，縮約など を学ぶ
3. Basic concepts: bipartite graphs, contraction

4. 2部グラフにおけるマッチングを学習する 1　　
4. Matching in bipartite graphs 1　

5. 2部グラフにおけるマッチングを学習する 2　　　　
5. Matching in bipartite graphs 2　

6. 2部グラフにおけるマッチングを学習する 3
6. Matching in bipartite graphs 3

7.  一般のグラフにおけるマッチングを学習する 1
7.  Matching in general graphs 1

8.  一般のグラフにおけるマッチングを学習する 2
8. Matching in general graphs 2

9.  エルデシュポーサの定理を学習する 1
9.  The Erdős–Pósa theorem 1

10. エルデシュ-ポーサの定理を学習する 2
10. The Erdős–Pósa theorem 2

11. 木パッキングと樹化数を学習する1
11. Tree packing and arboricity 1

12.  パッキングと樹化数を学習する 2
12. Tree packing and arboricity 2

13. パッキングと樹化数を学習する 3
13. Tree packing and arboricity 3

14. 道被覆を学習する.
14. Path covers

15. まとめ　
15. Summarize this course

-

-

-

N

N