圖論

課程目標: 「圖論」是很基本的組合數學方面之課程,它在資訊及其它領域的應用相當多,希望藉由這門課,讓大家學習到「圖論」之基本概念,以及領悟到如何運用「圖論」來解決問題。 課程綱要: 上課內容以課本的前七章為主: 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)本課程為應用數學研究所「乙組--主修組合數學」之必修課程,作業份量非常的重,困難程度也遠高於大學部「基礎圖論」。 (2)我很在意學生是否盡力學習,因此會經常缺課者、或無法自動自發努力者,請勿修本課程! (3)以應數所「乙組」學生最優先,其他學生(包含外校)以不超過5人為原則。

平時表現 (課堂中或課後發問或提出自己想法) 及作業(報告)佔25分, 期中考1 佔25%, 期中考2 佔25%, 期末考佔25%。 為不影響上課進度,考試時間,原則上將移至晚上或假日。

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

地點

SA345

時間

will be announced later

聯絡方式

cychen@mail.nctu.edu.tw