基礎圖論
Basic Graph Theory
學期
106-2
學分
2
學分
當期課號
6602
永久課號
CGE1002
開課單位
共同教育委員會
授課教師
陳秋媛
校區
光復
類別
其他通識
上課時間表
| 節 | 週四 |
|---|---|
9 17:30–18:20 | 基礎圖論 SC206 2 節連堂 |
A 18:30–19:20 |
* 根據陽明交大上課時間表所列
概述
「圖論」在資訊、通訊、運輸、管理等許多領域中,都有重要的應用,「圖」是許多問題的數學模型,本課程的目的在於認識及學習 1. 「圖論」的基本定義以及「圖」如何做為許多問題的數學模型 2. 歷史上的重要「圖論」定理 3. 「圖論」在現今世界的重要應用 並培養解決問題的能力、以及數學論證的能力 ===== 本課程設定為通識課程,非理工背景的同學也歡迎選修這門課,先備能力只需要高中數學 ===== 本課程不接受應數系同學選修
先修科目
高中數學
教學方式
課程特色: 1. 課堂中,將介紹老師搜集到的「圖論在現今世界的應用」 2. 透過「小組上台報告」,讓同學們能接觸到「圖論在現今世界的應用」, 未來也有機會將「圖論」應用到自己的研究或工作中 3. 搭配「課堂活動、紙本作業」,讓同學們能「做中學」 ===== (i) 會點名,會經常缺課者切勿修本課程!我很在意學生是否盡力學習,因此會經常缺課者、或無法自動自發努力者,請勿修本課程! (ii) 人數上限為40人(恕無法增加修課人數),老師保有最終決盅! (iii) 請注意: 實際進度有可能改變!
評分方式
課堂參與及作業佔20%,小組上台報告佔20%,期中考1佔20分,期中考2佔20分,期末考佔20分
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | 課程介紹;無向圖的基本定義;度(degree); |
| 第 2 週 | 有向圖的基本定義;交易問題;穩定婚姻問題;【HW1】 |
| 第 3 週 | 圖的同構(isomorphism);路徑相關;子圖; |
| 第 4 週 | 圖在電腦裡的表示法;尤拉迴路(一筆畫);中國郵差問題;【HW2】 |
| 第 5 週 | 漢彌爾頓圈及路徑;漢彌爾頓圈及路徑--充份條件或必要條件; |
| 第 6 週 | 民族掃墓節【不上課】 |
| 第 7 週 | 【期中考1】 |
| 第 8 週 | 二分圖(bipartite graphs)的定義;二分圖的刻劃;樹(tree)的定義及刻劃;樹葉(leaf)及更多的樹的刻劃; |
| 第 9 週 | 擴張樹(spanning tree);建構擴張樹、BFS、DFS演算法;Dijkstra演算法、Kruskal演算法、Prim演算法;【HW3】 |
| 第 10 週 | 毛毛蟲、圖的優美標號;圖的著色(coloring);貪婪著色演算法(greedy coloring);著色多項式(chromatic polynomial);【HW4】 |
| 第 11 週 | 圖的獨立數(independence number);圖的控制數(domination number);圖的點團數(clique number); |
| 第 12 週 | 【期中考2】 |
| 第 13 週 | 圖的配對(matching)與相異代表系(system of distinct representatives);最大配對與二分圖的配對; |
| 第 14 週 | 圖的連通度(connectivity);圖的區塊(block);【HW5】 |
| 第 15 週 | 【小組上台報告】 |
| 第 16 週 | 平面圖及尤拉公式;平面圖的刻劃;平面圖的5色定理及4色定理;【HW6】 |
| 第 17 週 | 有向圖的尤拉迴路(一筆畫)及漢彌爾頓圈及路徑;最大流問題; |
| 第 18 週 | 【期末考】 |
教科書
Introductory Combinatorics, 5th edition, Richard A. Brualdi, Prentice Hall 2010.
Office Hours
- 地點
- SA345
- 時間
- 3GH
- 聯絡方式
- cychen@mail.nctu.edu.tw