基礎圖論

「圖論」在資訊、通訊、運輸、管理等許多領域中,都有重要的應用,「圖」是許多問題的數學模型,本課程的目的在於認識及學習 : 1. 「圖論」的基本定義以及「圖」如何做為許多問題的數學模型 2. 重要的「圖論」定理 3. 「圖論」的應用 ===== 本課程可視為應用數學系"離散數學"的接續課程 "離散數學"以學習計數的技巧為主(鴿籠原理,容斥原理,遞迴關係,...等等); "基礎圖論"則是學習圖論為主; "離散數學"和 "基礎圖論"那一門課先修都可以 ===== 課程將介紹以下概念: 1. 基本定義(vertex, edge), 度(degree) 2. 圖的同構(isomorphism) 3. Walk及path相關 4. 子圖(subgraph) 5. 圖的表示法(graph representation) 6. 尤拉迴路(一筆畫), 中國郵差問題 7. 漢彌爾頓圈及路徑 8. 二分圖(bipartite graphs) 9. 樹(tree), 樹的等價敘述, 樹的性質 10. 寬先(BFS),深先(DFS) 11. Dijkstra演算法 12. 擴張樹(spanning tree), 換邊, Kruskal及Prim演算法 13. 毛毛蟲, 優美標號 14. 圖的著色(coloring), 貪婪著色法, 著色多項式 15. 平面圖的尤拉公式, 平面圖的刻劃, 五色定理 16. 獨立集 (independent set), 控制集 (dominating set), 點團 (clique) 17. 配對與SDR, 二分圖的配對(matching) 18. Connectivity, blocks 19. Digraphs, core allocation, stable marriages 20. Network flow

高中數學

*** 相當重要 (i) 開學後第1~2週採遠距同步上課 (老師人會在 SA345 研究室) 已選及旁聽同學: 請在上課後5分鐘內 使用 @nycu.edu.tw 的信箱, 登入 Google Meet 開學後第1週 https://meet.google.com/enf-qmpc-rkn 開學後第2週 https://meet.google.com/另行公告 (ii) 考試採實體教室考試 (at SC206), 不提供遠距考試 -------------------------------------------------------------- 應用數學系大學部同學優先, 老師保有最終決定權 (已轉資工系的同學請考慮改選資工系圖型理論) 會點名, 無法自動自發努力者, 切勿修本課程! 實際進度及配分有可能改變!

平時表現 (上課出席,課堂參與) 及作業表現佔25%,期中考1佔25分,期中考2佔25分,期末考佔25分

Introductory Combinatorics, 5th edition, Richard A. Brualdi, Prentice Hall 2010.

地點

SA345

時間

3GH

聯絡方式

cychen@nycu.nctu.edu.tw