課程資訊
課程名稱
圖論二
Graph Theory (Ⅱ) 
開課學期
100-2 
授課對象
理學院  數學研究所  
授課教師
張鎮華 
課號
MATH7704 
課程識別碼
221 U3460 
班次
 
學分
全/半年
半年 
必/選修
選修 
上課時間
星期二2(9:10~10:00)星期四1,2(8:10~10:00) 
上課地點
天數204天數204 
備註
總人數上限:40人 
Ceiba 課程網頁
http://ceiba.ntu.edu.tw/1002GT_2 
課程簡介影片
 
核心能力關聯
核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

這是一學年的課。上學期的內容包含最基本的圖論知識,諸如:通論、演算法簡介、樹狀圖、匹配、圖的連通性、平面圖、圖著色、Hamilton圖。下學期的內容包含進階的圖論知識,諸如:完美圖、擬陣、Ramsey理論、極值圖論、機率方法、NP-完全問題、代數方法:時間允許時,並將介紹目前的一些研究題材。  

課程目標
Graph theory becomes a common tool of many fields including mathematics, engineering, computer sciences … etc. The goal of this course is to introduce basic knowledge on graph theory. If time is enough, we may introduce some current research on graph theory. 
課程要求
無。 
預期每週課後學習時數
 
Office Hours
 
參考書目
張鎮華、蔡牧村,圖論及其演算法。
D. B. West, Introduction to Graph Theory, Second Edition.
 
指定閱讀
張鎮華、蔡牧村,圖論及其演算法。
D. B. West, Introduction to Graph Theory, Second Edition.

 
評量方式
(僅供參考)
 
No.
項目
百分比
說明
1. 
作業 
30% 
 
2. 
期中考 
35% 
 
3. 
期末考 
35% 
 
 
課程進度
週次
日期
單元主題
第1週
2/21,2/23  完美圖 
第2週
2/28,3/01  完美圖 
第3週
3/06,3/08  完美圖、擬陣 
第4週
3/13,3/15  擬陣 
第5週
3/20,3/22  擬陣 
第6週
3/27,3/29  Ramsey理論 
第7週
4/03,4/05  Ramsey理論 
第8週
4/10,4/12  Ramsey理論、極值圖論 
第9週
4/17,4/19  極值圖論 (期中考) 
第10週
4/24,4/26  極值圖論 
第11週
5/01,5/03  機率方法 
第12週
5/08,5/10  機率方法 
第13週
5/15,5/17  機率方法、NP-完全問題 
第14週
5/22,5/24  NP-完全問題 
第15週
5/29,5/31  NP-完全問題 
第16週
6/05,6/07  代數方法 
第17週
6/12,6/14  代數方法 
第18週
6/21  期末考 (6/21 everning 6:00 ~ )