文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 1. Introduction
Slides for a Course Based on the Text
Combinatorial Optimization
by Cook, Cunningham, Pulleyblank and Schrijver
(c) Spring 2007, Juan Su-tzu Juan 1
Introduction
Q: What binatorial Optimization?
A: “What is a best arrangement?”
(c) Spring 2007, Juan Su-tzu Juan 2
Introduction
教學目標:
以GRAPH為工具,學習一般組合學上遇到求解最佳化問題
時的研究解決方法。
課程範圍:
組合學上遇到求解最佳化問題時的常見解決方法之研究。
授課方式:
以投影片於課堂上教學與討論,同學們輪流上台報告與練
習。
(c) Spring 2007, Juan Su-tzu Juan 3
Introduction
課程進度及綱要:
1. Introduction
2. Mathematical Preliminaries
3. Domination Problem in Tree
4. The Domination Problems on Interval Graphs
5. The Domatic Number Problem on Interval Graphs
6. pleteness
7. Applications of . Duality :
The Weighted Domination Problem on Strongly Chordal Graphs
8. Applications of L. P. Duality : The Independent Set on Chordal Graphs
9. Domatic Number Problem
10. More Class of Graphs
11. Minimum Spanning Trees
12. Shortest Paths 1
13. Shortest Paths 2 將根據上課情形調整進度與方向
14. Maximum Flow Problem
15. Minimum-Cost Flow Problem
(c) Spring 2007, Juan Su-tzu Juan 4
Introduction
參考書籍:
1. William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander
Schrijver, Combinatorial Optimization, Wiley-Interscience, 1997.
2. Eugene Lawler, Combinatorial Optimization: Networks and Matroids,
Dover Publications, 2001
3. B. H. Korte, Jens Vygen, Bernhard Korte, Combinatorial Optimization:
Theory and Algorithms (Algorithms binatorics), Springer-Verlag, 2002.
4. Christos H. Papadimitriou, h Steiglitz, Combinatorial Optimization :
Algorithms plexity, Dover Publications, 1998
5. Jon Lee, D. G. Crighton, A First Course binatorial Optimization,
(華通代理), 2004.
6. Laurence A. Wolsey, e L. Nemhauser, Integer binatorial
Optimization, Wiley - Interscience, 1999.
7. 相關論文
評分方式:
作業30% + 平時成績10% + 期中考20% + 期末報告40%