圖論

Abstract

課程首頁

本課程是由交通大學應用數學系提供。

圖的模式(Graph Model)是指我們把所要探討或研究的問題以圖的形式來描述；例如七橋問題中的四個區域分別以四個點來代表，而七條橋則分別代表連接某兩個點的邊；如此一來，我們可以得到一個圖，它有四個點及七條邊；七橋問題因此被轉換成研究可否在上述圖中找到由某一點出發；再經過全部邊而回到出發點的一筆劃問題。另外，四色定理的証明不但加深對圖基本結構的研究更帶動了計算機科學的蓬勃發展；近代網路的設計更是有向圖發展的最佳舞台。

課程目標/概述 圖的模式(Graph Model)是指我們把所要探討或研究的問題以圖的形式來描述；例如七橋問題中的四個區域分別以四個點來代表，而七條橋則分別代表連接某兩個點的邊；如此一來，我們可以得到一個圖，它有四個點及七條邊；七橋問題因此被轉換成研究可否在上述圖中找到由某一點出發；再經過全部邊而回到出發點的一筆劃問題。另外，四色定理的証明不但加深對圖基本結構的研究更帶動了計算機科學的蓬勃發展；近代網路的設計更是有向圖發展的最佳舞台。

課程章節

章節

內容

第一章 圖的基本性質

第二章 尤拉迴路，哈米爾頓圈

第三章 圖的連通性

第四章 圖的著色

第五章 拓樸圖論介紹

課程書目

D. B. West, Introduction to Graph Theory. Van Lint and Wilson, A course in Combinatorics. Yusheng Li and Wenan Zang, Introduction to Graph Ramsey Theory.

評分標準

項目 百分比

期中考 50%

期末考 50%

授課對象：研究所學生

預備知識：微積分