課程名稱 |
圖論一 Graph Theory (Ⅰ) |
開課學期 |
110-1 |
授課對象 |
理學院 數學研究所 |
授課教師 |
戴尚年 |
課號 |
MATH7703 |
課程識別碼 |
221EU3450 |
班次 |
|
學分 |
3.0 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期二8,9(15:30~17:20)星期五5(12:20~13:10) |
上課地點 |
天數102天數102 |
備註 |
本課程以英語授課。 總人數上限:40人 外系人數限制:10人 |
|
|
課程簡介影片 |
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
Fundamentals: graphs, isomorphisms, adjacency matrices
Trees: spanning trees, enumeration
Connectivity: equivalent characterisations - Mader’s Theorem and Menger’s Theorem
Cycles: Eulerian graphs, Hamiltonian graphs, sufficient conditions
Matchings: Hall’s Theorem and other conditions
Planar graphs: Euler’s formula, platonic solids
Graph colouring: applications, bounds on the chromatic number, Four Colour Theorem
Extremal results: Ramsey Theory, Turan’s Theorem |
課程目標 |
Graph theory is a rapidly growing branch of mathematics, perhaps primarily due to its several applications in fields such as computer science. At the same time, the subject shares close connections with other mathematical areas such as analysis, algebra, geometry and probability.
In this introductory course, students will become familiar with graphs and their fundamental properties, learning several interesting classic results in various aspects of graph theory. Students will also be exposed to different proof methods used in combinatorics, laying a foundation for more advanced courses in the area later in their studies. |
課程要求 |
Linear algebra and probability
Homework: 34%
Midterm: 33%
Final exam: 33% |
預期每週課後學習時數 |
|
Office Hours |
|
指定閱讀 |
|
參考書目 |
The course will be self-contained, but useful texts include:
- West, D., “Introduction to Graph Theory”
- Diestel, R., “Graph Theory” |
評量方式 (僅供參考) |
|
|