課程資訊
課程名稱
圖論演算法
GRAPH ALGORITHMS 
開課學期
93-2 
授課對象
理學院  數學系  
授課教師
張鎮華 
課號
MATH7707 
課程識別碼
221 U4070 
班次
 
學分
全/半年
半年 
必/選修
選修 
上課時間
星期二3,4(10:20~12:10)星期四5(12:20~13:10) 
上課地點
新數102 
備註
 
 
課程簡介影片
 
核心能力關聯
核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

I.Contents:
˙Representations of graphs (adjacency matrix, adjacency list, sequential adjacency list etc).
˙Paths (including Eulerian tour, de Bruijn sequence, shortest path).
˙Trees (including minimum spanning tree, optimum branching, matroid, Huffman tree).
˙Depth first search (including applications to 2-connected component, strongly connected component, testing graph planarity etc)
˙Maximum flow (including Ford-Fulkerson’s algorithm, Diric’s algorithm, applications maximum flow theory such as connectivity and bipartite matching).
˙NP-completeness (including Cook’s theorem, SAT problem, transformations between NP-complete problems).
˙Others (some topics in current journals).
II.Course prerequisite:
None.
III. Reference material (textbook):
1.S. Even, Graph Algorithms, 1979. (textbook)
2.R. K. Ahuja, T. L. Magnanti andJ. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall International, London, 1993.
3.G. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, New York, 1993.
4.W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998.
5.T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithm, Second Edition, The MIT Press, Cambridge, 2002.
6.A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
7.M. C. Golumbie, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
8.J. A. McHugh, Algorithmic Graph Theory, Prentice-Hall, London, 1990.
9.K. Thulasiraman and M. N. S. Swamy, Graphs: Theory and Algorithms, John Wiley & Sons, Inc., New York, 1992.
IV.Grading scheme:
50% for the midterm exam and 50% for the final exam.
V.Others:
Office: Room 305, Old Mathematics Building
Email: gjchang@math.ntu.edu.tw
http://www.math.ntu.edu.tw/~gjchang/ 

課程目標
 
課程要求
 
預期每週課後學習時數
 
Office Hours
 
參考書目
 
指定閱讀
 
評量方式
(僅供參考)
   
課程進度
週次
日期
單元主題
無資料