基礎圖論
Fundamental Graph Theory
| 節 | 週一 | 週三 |
|---|---|---|
3 10:10–11:00 | 基礎圖論 SC206 2 節連堂 | |
4 11:10–12:00 | ||
5 13:20–14:10 | 基礎圖論 SC206 2 節連堂 | |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
「圖論」在資訊、通訊、運輸、管理等許多領域中,都有重要的應用,「圖」是許多問題的數學模型,本課程的目的在於認識及學習 : 1. 「圖論」的基本定義以及「圖」如何做為許多問題的數學模型 2. 重要的「圖論」定理 3. 「圖論」的應用 ===== 本課程可視為應用數學系"離散數學"的接續課程 "離散數學"以學習計數的技巧為主(鴿籠原理,容斥原理,遞迴關係,...等等); "基礎圖論"則是學習圖論為主; "離散數學"和 "基礎圖論"那一門課先修都可以 ===== 課程將介紹以下概念: 基本定義(vertex, edge), 度(degree) 圖的同構(isomorphism) Walk及path相關 子圖(subgraph) 圖的表示法(graph representation) 尤拉迴路(一筆畫), 中國郵差問題 漢彌爾頓圈及路徑 二分圖(bipartite graphs) 樹(tree), 樹的等價敘述, 樹的性質 寬先(BFS),深先(DFS)搜尋 Dijkstra演算法 擴張樹(spanning tree), Kruskal及Prim演算法 圖的著色(coloring), 貪婪著色法, 著色多項式 平面圖的尤拉公式, 平面圖的刻劃, 五色定理 獨立集 (independent set), 控制集 (dominating set), 點團 (clique) 配對與SDR, 二分圖的配對(matching) Connectivity, blocks Digraphs, core allocation, stable marriages, network flow 等
高中數學
應用數學系大學部同學優先, 老師保有最終決定權 (已轉資工系的同學請考慮改選資工系圖型理論) 會點名, 無法自動自發努力者, 切勿修本課程! 實際進度及配分有可能改變!
上課出席、課堂參與、作業、佔20%,期末上台報告佔5%,期中考1佔25分,期中考2佔25分,期末考佔25分.
| 週次 | 主題 |
|---|---|
| 第 1 週 | 簡介, vertex, edge, degree, degree sequence, isomorphism |
| 第 2 週 | walk, trail, path, cycle, connected, subgraph, graph representation, eulerian trail, Chinese postman problem |
| 第 3 週 | *HW1 hamiltonian cycles and paths, bipartite graphs |
| 第 4 週 | *HW2 學習使用電腦軟體畫圖 trees |
| 第 5 週 | 學習使用電腦軟體畫圖 spanning trees |
| 第 6 週 | algorithms for trees midterm 1 |
| 第 7 週 | algorithms for trees, graph coloring |
| 第 8 週 | *HW3 graph coloring, planar graphs |
| 第 9 週 | *HW4 planar graphs, parameters in graphs (independence number, clique number, domination number, etc) |
| 第 10 週 | perfect graphs, SDR, matching |
| 第 11 週 | matching midterm 2 |
| 第 12 週 | connectivity, digraphs |
| 第 13 週 | *HW5 digraphs, trading problem, network flow |
| 第 14 週 | *HW6 network flow |
| 第 15 週 | matching algorithms 期末上台報告 |
| 第 16 週 | 期末上台報告 final |
Introductory Combinatorics, 5th edition, Richard A. Brualdi, Prentice Hall 2010.
- 地點
- SA345
- 時間
- 開學後確定
- 聯絡方式
- cychen"at" nycu.nctu.edu.tw