圖論

課程目標: 「圖論」是基本的組合數學方面之課程,「圖論」在資訊及其它領域的應用相當多,希望藉由這門課,讓大家學習到「圖論」之基本概念,以及領悟到如何運用「圖論」來解決問題。 課程綱要: 上課內容以課本的前七章為主: Chap 1 Fundamental Concepts What is a graph? Path, Cycles, and Trails. Vertex Degrees and Counting. Directed Graphs. Chap 2 Trees and Distances Basic Properties. Spanning trees and Enumeration. Optimization and Trees. Chap 3 Matchings and Factors Matchings and Covers. Algorithms and Applications. Matchings in General Graphs. Chap 4 Connectivity and Paths Cuts and Connectivity, k-connected Graphs. Network Flow Problems. Chap 5 Coloring of Graphs Vertex Coloring and Upper Bounds. Structure of k-chromatic Graphs. Enumerative Aspects. Chap 6 Planar Graphs Embeddings and Euler's Formula. Characterization of Planar Graphs. Parameters of Planarity. Chap 7 Edges and Cycles Line Graphs and Edge-coloring. Hamiltonian Cycles. Planarity, Coloring, and Cycles. (書上標示optional的部份基本上都不會講、「課程進度表」將於開學後發給、請留意考試日期)

修過"離散數學" (大二及以下之學生不適合本課程,請改為選修大學部「基礎圖論」)

*** 相當重要 (i) 開學後第1~2週採遠距同步上課 (老師人會在 SA345 研究室) 已選及旁聽同學: 請在上課後5分鐘內 使用 @nycu.edu.tw 的信箱, 登入 Google Meet 開學後第1週 https://meet.google.com/usj-wufy-dmr 開學後第2週 https://meet.google.com/另行公告 (ii) 考試採實體教室考試 (at SC206), 不提供遠距考試 ------------------ 1. 本課程為 3學分3小時課程. 2. 本課程之進度及配分有可能修改. 3. 本課程為應用數學研究所「乙組--主修組合數學」之必修課程, 作業份量非常重, 困難程度遠高於大學部「基礎圖論」. 4. 我很在意學生是否盡力學習, 因此, 無法自動自發努力者, 請勿修本課程! 5. 本課程以應用數學研究所「乙組--主修組合數學」學生最優先, 應數系大三大四曾獲書卷獎,數學書卷獎者, 老師也會考慮.

平時表現 (出席, 課堂中或課後發問或提出自己想法)及作業佔25分, 期中考1 佔25%, 期中考2 佔25%, 期末考佔25%。 ***修習本課程即代表你同意本課程所有規定

“Introduction to Graph Theory” by Douglas B. West, 2nd Ed, Prentice Hall (若有更新的版本將會採用新版)

地點

SA345

時間

3GH (老師有可能臨時有事; 若是如此, 老師會提前通知)

聯絡方式

cychen@nycu.nctu.edu.tw