Course No.：S070105ZJ003
Course Category：Professional Basic Course
Period/Credits：40/2
Prerequisites：Advanced Mathematics, Linear Algebra.
Aims & Requirements：
This course systematically introduces basic concepts, methods and theorems in graph theory, along with important problems in this area, typical network algorithms and their broad applications.
This course is intended as a basic course for graduate students of mathematics, operational research and system sciences, while can also be an elective for students from areas like physics, chemistry, biology and life science, computer science and technology, electronic science and technology, communication and information science, network engineering, complex networks and systems, resources and environment, logistics and transportation, management science and engineering, automatic control.
This course can help students lay the foundation both for theoretical research and further applications.
Primary Coverage：
Chapter 1 Basic Concepts
Concepts of Graph; Shortest Path Problem; Tree and its Basic Properties; Spanning Tree and Minimum Spanning Tree; Center and Median; Matrix Representation of Graph.
Chapter 2 Connectivity
Cut; Connectivity; Properties of 2-Connected Graph; Menger Theorem; Design of Reliable Communication Networks.
Chapter 3 Matching Theory
Matching and Maximum Matching; Perfect Matching; Matching of Bipartite Graph; Algorithms for Maximum Matching and Maximum Weighted Matching of Bipartite Graph.
Chapter 4 Eulerian Graph and Hamiltonian Graph
Eulerian Graph; Chinese Postman Problem; Hamilton Graph; TSP.
Chapter 5 Dominant Set, Independent Set, Coverage Set
Dominant Set; Independent Set; Coverage Set; Algorithms for Finding Them.
Chapter 6 Coloring Theory
Edge Coloring; Vertex Coloring; Chromatic Polynomial; Algorithms for Edge Coloring and Vertex Coloring.
Chapter 7 Planar Graph
Concepts; Euler’s Formula and its Application; Decision of Planar Graph; Dual of Planar Graph.
Chapter 8 Directed Graph
Concepts; Directed Path and Cycle; Connectivity of Directed Graph and Strong Connectivity of Undirected Graph; Tournament; Root Tree and its Application.
References：
[1] J.A. Bondy, and U.S.R. Murty, Graph Theory with Applications, The Macmillan Press LTD. 1976.
[2] D.B. West, Introduction to Graph Theory (second edition), Prentice-Hall, Inc., 2001.
[3] G. Chartrand, and Ping Zhang, Introduction to Graph Theory, McGraw-Hill Companies, Inc. 2005.
[4] D. Reinhard, Graph Theory (second edition), Springer-Verlag, New York, (2000)43-67.
[5] W.T. Tutte, Graph Theory, Cambridge University Press, (2001) 32-114.
Author：Suixiang Gao (School of Mathematical Sciences, GUCAS)
Date：June, 2010
