| Relevance of Course Objectives and Core Learning Outcomes(%) |
Teaching and Assessment Methods for Course Objectives |
| Course Objectives |
Competency Indicators |
Ratio(%) |
Teaching Methods |
Assessment Methods |
圖論中的圖是由若干給定的點及連接兩點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的邊表示相應兩個事物間具有這種關係。
圖論的研究常常跟益智問題或遊戲有很大的牽連，例如: 一筆畫問題、四色定理…甚至到最近很流行的數獨，都和圖論脫離不了關係。此外，圖論在現實生活上的應用和貢獻，也是不容忽視的! 其涉及的領域包含有: 網路、資訊科學、密碼學、分子生物學、社會科學…等等，族繁不及備載。
本課程挑選幾個圖論的經典主題，進行深入地探討。這堂課的學習重點在於，使學生透過不同的主題學習到圖的基本性質與結構，期望未來對於圖論或其他組合數學的研究工作能有所幫助。 |
| 1.Mathematical Thinking and Logic |
| 2.Professional Knowledge in Mathematical Analysis |
|
|
| Discussion |
| Exercises |
| Lecturing |
|
| Oral Presentation |
| Assignment |
| Written Presentation |
|
| Course Content and Homework/Schedule/Tests Schedule |
| Week |
Course Content |
| Week 1 |
圖論簡介
真實世界的應用&動機
|
| Week 2 |
圖的基本定義與特殊圖類
圖的數學歸納法須知
圖的運算(從舊的圖生成新的圖) |
| Week 3 |
連通度
Menger’s Theorem
Whitney’s Theorem
|
| Week 4 |
樹圖的等價定義與基本性質
【Erdos-Sos 猜想】
Erdos-Gallai Theorem |
| Week 5 |
Decision trees
Binary search trees
秤偽幣問題(決策樹觀點)
|
| Week 6 |
BFS & DFS
Minimum spanning trees
|
| Week 7 |
春假 |
| Week 8 |
歐拉迴路
中國郵差問題
|
| Week 9 |
漢米爾頓圈的必要條件
充分條件
|
| Week 10 |
旅行推銷員問題 |
| Week 11 |
de Bruijn sequences
葛拉漢魔術
|
| Week 12 |
點著色
貪婪演算法
|
| Week 13 |
Brooks’ Theorem
|
| Week 14 |
平面圖
歐拉公式
|
| Week 15 |
【四色定理】
|
| Week 16 |
Sperner’s Lemma
自主跨域學習(相關教材閱讀)
自主跨域學習(相關教材閱讀) |
self-directed
learning |
03.Preparing presentations or reports related to industry and academia.
|
|
| Evaluation |
口頭簡報 Oral Presentation
習題演練 Exercises
心得報告 Experience report |
| Textbook & other References |
參考書單
Introduction to Graph Theory, 2nd edition, Douglas B. West
|
| Teaching Aids & Teacher's Website |
|
| Office Hours |
| 課堂上公布 |
| Sustainable Development Goals, SDGs(Link URL) |
| include experience courses：N |
|