| 課程與核心能力關聯配比(%) |
課程目標之教學方法與評量方法 |
| 課程目標 |
核心能力 |
配比(%) |
教學方法 |
評量方法 |
圖論中的圖是由若干給定的點及連接兩點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的邊表示相應兩個事物間具有這種關係。
圖論的研究常常跟益智問題或遊戲有很大的牽連，例如: 一筆畫問題、四色定理…甚至到最近很流行的數獨，都和圖論脫離不了關係。此外，圖論在現實生活上的應用和貢獻，也是不容忽視的! 其涉及的領域包含有: 網路、資訊科學、密碼學、分子生物學、社會科學…等等，族繁不及備載。
本課程挑選幾個圖論的經典主題，進行深入地探討。這堂課的學習重點在於，使學生透過不同的主題學習到圖的基本性質與結構，期望未來對於圖論或其他組合數學的研究工作能有所幫助。 |
| 1.數學專業思維與邏輯推理知識 |
| 2.數學分析專業知識 |
|
|
|
|
| 授課內容(單元名稱與內容、習作/每週授課、考試進度-共16週加自主學習) |
| 週次 |
授課內容 |
| 第1週 |
圖論簡介
真實世界的應用&動機
|
| 第2週 |
圖的基本定義與特殊圖類
圖的數學歸納法須知
圖的運算(從舊的圖生成新的圖) |
| 第3週 |
連通度
Menger’s Theorem
Whitney’s Theorem
|
| 第4週 |
樹圖的等價定義與基本性質
【Erdos-Sos 猜想】
Erdos-Gallai Theorem |
| 第5週 |
Decision trees
Binary search trees
秤偽幣問題(決策樹觀點)
|
| 第6週 |
BFS & DFS
Minimum spanning trees
|
| 第7週 |
春假 |
| 第8週 |
歐拉迴路
中國郵差問題
|
| 第9週 |
漢米爾頓圈的必要條件
充分條件
|
| 第10週 |
旅行推銷員問題 |
| 第11週 |
de Bruijn sequences
葛拉漢魔術
|
| 第12週 |
點著色
貪婪演算法
|
| 第13週 |
Brooks’ Theorem
|
| 第14週 |
平面圖
歐拉公式
|
| 第15週 |
【四色定理】
|
| 第16週 |
Sperner’s Lemma
自主跨域學習(相關教材閱讀)
自主跨域學習(相關教材閱讀) |
自主學習
內容 |
03.製作專題報告
|
|
| 學習評量方式 |
口頭簡報 Oral Presentation
習題演練 Exercises
心得報告 Experience report |
| 教科書＆參考書目(書名、作者、書局、代理商、說明) |
參考書單
Introduction to Graph Theory, 2nd edition, Douglas B. West
|
| 課程教材（教師個人網址請列在本校內之網址） |
|
| 課程輔導時間 |
| 課堂上公布 |
| 聯合國全球永續發展目標(連結網址) |
|
|