圖形理論導論
Elementary graph theory
| 節 | 週一 |
|---|---|
3 10:10–11:00 | 圖形理論導論 ED117（光復） 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
介紹圖形理論中常見的問題、定理以及應用。課程著重在常見問題與其相關基礎定理的介紹,在各章節中也會介紹章節主題在各領域的應用範例。此外也會透過程式作業,讓同學練習圖形理論相關的程式設計,使同學具有圖形理論的基礎知識與實作能力。
離散數學、計算機概論與程式設計
無備註
基礎圖論課程目前規劃先以線上教學、實體考試為主。底下是課程群組的連結,請欲選修同學透過連結申請加入群組,方能參與線上課程。加選結束後會再剔除未選修同學。 https://teams.microsoft.com/l/team/19%3aQ3wET2_9cNce45zOBb9kOrfzj5Ur7KAoTTTN_7zoZ8k1%40thread.tacv2/conversations?groupId=4e5b538d-ff49-4222-b46f-c31973ecf6f5&tenantId=80a9abdb-7cef-443c-b040-3f8e75e9232e Slides with blackboard All materials and course information will be available on E3. 課程助教:李庭緯,劉祐誠, 林廷昕,郭家佑,鄭宇軒:59281 程式作業助教:楊秉宇,王昱宸,吳柏橙
1. Program assignment: 50% 2. Test: 50%
1. Graph models, terminology, and proofs
1.1 Tournaments 1.2 Introduction to Graph Models and Terminology 1.3 Matrix Representation 1.4 Proof Techniques 1.5 Degree Sequence 1.6 Tournaments Revisited
- 講授：
- 6 hrs
2. Graph routes
2.1 Eulerian Circuits 2.2 Hamiltonian Cycles 2.3 Shortest Paths
- 講授：
- 9 hrs
3. Trees
3.1 Spanning Trees 3.2 Tree Properties 3.3 Rooted Trees 3.4 Additional Applications
- 講授：
- 6 hrs
4. Connectivity and flow
4.1 Connectivity Measures 4.2 Connectivity and Paths 4.3 Network Flow
- 講授：
- 9 hrs
5. Matching
5.1 Matching in Bipartite Graphs 5.2 Matching in General Graphs 5.3 Stable Matching
- 講授：
- 9 hrs
6. Graph coloring
6.1 Four Color Theorem 6.2 Vertex Coloring 6.3 Edge Coloring
- 講授：
- 6 hrs
7. Planarity
7.1 Kuratowski's Theorem
- 講授：
- 3 hrs
| 週次 | 主題 |
|---|---|
| 第 1 週 | 2023-09-11(一) |
| 第 2 週 | 2023-09-18(一) |
| 第 3 週 | 2023-09-25(一) |
| 第 4 週 | 2023-10-02(一) |
| 第 5 週 | 2023-10-09(一) |
| 第 6 週 | 2023-10-16(一) |
| 第 7 週 | 2023-10-23(一) |
| 第 8 週 | 2023-10-30(一) |
| 第 9 週 | 2023-11-06(一) |
| 第 10 週 | 2023-11-13(一) |
| 第 11 週 | 2023-11-20(一) |
| 第 12 週 | 2023-11-27(一) |
| 第 13 週 | 2023-12-04(一) |
| 第 14 週 | 2023-12-11(一) |
| 第 15 週 | 2023-12-18(一) |
| 第 16 週 | 2023-12-25(一) |
1. "Graph theory: An introduction to proofs, algorithms, and applications", Karin R. Saoub, CRC press , 1st Ed., 2021 2. "Graph Theory and Its Applications" by Jonathan L. Gross and Jay Yellen, Second Edition. Publisher: Chapman & Hall/CRC
- 地點
- EC441
- 時間
- M 7,8
- 聯絡方式
- 31364 ylli@cs.nctu.edu.tw