圖論

課程目標: 「圖論」是很基本的組合數學方面之課程,它在資訊及其它領域的應用相當多,希望藉由這門課,讓大家學習到「圖論」之基本概念,以及領悟到如何運用「圖論」來解決問題。 課程綱要: 上課內容以課本的前七章為主: 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的部份均不講、「課程進度表」將於開學後發給、請留意「課程進度表」中的上課及考試日期)

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

1. 本課程上課時段為 1CD 3CD (3學分3小時), 教室為 SC206. 2. 為不影響上課進度, 考試時間將移至晚上或假日. 3. 本課程之課程進度有可能修改. 4. 本課程為應用數學研究所「乙組--主修組合數學」之必修課程, 作業份量非常的重, 困難程度也遠高於大學部「基礎圖論」. 5. 我很在意學生是否盡力學習, 因此會經常缺課者、或無法自動自發努力者, 請勿修本課程! 6. 本課程以應用數學研究所「乙組--主修組合數學」學生最優先, 其他學生(包含外校)以不超過5人為原則.

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

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

地點

SA345

時間

3E (3E 老師有可能去參加學校會議, 一學期大約4~5次; 若是如此, 老師會提前通知) 5G (5G 老師有可能臨時有事, 一學期大約4~5次; 若是如此, 老師會提前通知)

聯絡方式

cychen@mail.nctu.edu.tw