基礎圖論

This is an introductory course on graph theory. Basic concepts, essential topics and theorems, and applications in other areas (including optimization) will be discussed. Students are expected to build a foundational understanding of graph theory, and learn how to model and solve problems from other subjects using it.

High school mathematics. Basic mathematical maturity (e.g., prior exposure to mathematical proofs) is preferred.

Topics to be discussed depend on the interest of the class.

Use e3 system.

10% attendance, 30% quizzes/oral presentation, 30% midterm, 30% final

• Fundamental Concepts

  Definition and examples of graphs, isomorphism and subgraphs, paths and cycles, bipartite and Eulerian graphs, degree sequences

• Trees and Distance

  Basic properties of trees, spanning trees and their enumeration, minimum spanning trees and shortest path algorithms

• Matchings and Factors

  Bipartite graph matching, Hall's and Konig's theorem, bipartite matching algorithms, intro to general graph matching

• Connectivity and Paths

  Vertex and edge connectivity, block decomposition, ear decomposition, Menger's theorem

• Coloring of Graphs

  Vertex coloring and Brooks' theorem, edge coloring and Vizing's theorem

• Planar Graphs

  Planar graphs, plane graphs and their duals, Euler's formula, Kuratowski's theorem, coloring of planar graphs

• Additional Topics

  Possible topics include: Flows in graphs, Hamiltonian cycles, digraphs, graph polynomials, graph spectra, extremal graph theory, Ramsey theory

  備註：Topics to be discussed depend on the interest of the class.

Introduction to Graph Theory, 2nd edition, D. B. West, Prentice Hall (Main textbook) Graph Theory with Applications, J. A. Bondy and U. S. R. Murty, North-Holland (A more concise textbook of similar level for reference) Graph Theory, 6th edition, Reinhard Diestel, Springer (More advanced reference)

地點

SA341

時間

Send an e-mail to me to make appointment.

聯絡方式

e3 or chyuen@math.nctu.edu.tw