課程與核心能力關聯配比(%) |
課程目標之教學方法與評量方法 |
課程目標 |
核心能力 |
配比(%) |
教學方法 |
評量方法 |
圖論中的圖是由若干給定的點及連接兩點的邊所構成的圖形,這種圖形通常用來描述某些事物之間的某種特定關係,用點代表事物,用連接兩點的邊表示相應兩個事物間具有這種關係。
圖論的研究常常跟益智問題或遊戲有很大的牽連,例如: 一筆畫問題、四色定理…甚至到最近很流行的數讀,都和圖論脫離不了關係。儘管如此,圖論在現實生活上的應用和貢獻,也是不容忽視的! 其涉及的領域包含有: 網路、資訊科學、密碼學、分子生物學、社會科學…等等,族繁不及備載。在過去的兩百多年間,圖論在無數學者的努力之下,逐漸慢慢成型、茁壯,成為近代一門重要的數學分枝。
本課程挑選幾個圖論裡面較熱門的研究主題,進行深入地探討。這堂課的學習重點在於,使學生透過不同的主題學習到圖的基本性質與結構,期望未來對於圖論或其他組合數學的研究工作能有所幫助。 |
1.數學專業思維與邏輯推理知識 |
2.數學分析專業知識 |
|
|
|
|
授課內容(單元名稱與內容、習作/每週授課、考試進度-共18週) |
週次 |
授課內容 |
第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
|
第17週 |
自主跨域學習(相關教材閱讀) |
第18週 |
自主跨域學習(相關教材閱讀) |
|
學習評量方式 |
口頭簡報 Oral Presentation
習題演練 Exercises
心得報告 Experience report |
教科書&參考書目(書名、作者、書局、代理商、說明) |
參考書單
Introduction to Graph Theory, 2nd edition, Douglas B. West
|
課程教材(教師個人網址請列在本校內之網址) |
|
課程輔導時間 |
課堂上公布 |
聯合國全球永續發展目標 |
|