北京師範大學 圖論 60講 Graph Theory 簡體中文 DVD 只於電腦播放


圖論〔GraphTheory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若
幹給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的
某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係
　　。
圖論本身是應用數學的一部份，因此，歷史上圖論曾經被好多位數學家各自獨立地
　　建立過。關於圖論的文字記載最早出現在歐拉1736年的論著中，他所考慮的原始問
　　題有很強的實際背景。
圖論起源於著名的柯尼斯堡七橋問題。在柯尼斯堡的普萊格爾河上有七座橋將河中
的島及島與河岸聯結起來，如下圖所示，A、B、C，D表示陸地。
問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，再回到起點。然
　　而無數次的嘗試都沒有成功。歐拉在1736年解決了這個問題，他用抽象分析法將這
個問題化為第一個圖論問題：即把每一塊陸地用一個點來代替，將每一座橋用聯接
相應的兩個點的一條線來代替，從而相當於得到一個「圖」（如下圖）。歐拉證明
了這個問題沒有解，並且推廣了這個問題，給出了對於一個給定的圖可以某種方式
　　走遍的判定法則。這項工作使歐拉成為圖論〔及拓撲學〕的創始人。
1859年，英國數學家哈密頓發明了一種遊戲：用一個規則的實心十二面體，它的
20個頂點標出世界著名的20個城市，要求遊戲者找一條沿著各邊通過每個頂點剛好
一次的閉迴路，即「繞行世界」。用圖論的語言來說，遊戲的目的是在十二面體的
　　圖中找出一個生成圈。這個問題後來就叫做哈密頓問題。由於運籌學、計算機科學
和編碼理論中的很多問題都可以化為哈密頓問題，從而引起廣泛的注意和研究。
在圖論的歷史中，還有一個最著名的問題——四色猜想。這個猜想說，在一個平面
或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的
　　顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的
邊界，而不僅僅只有一個公共點。四色猜想有一段有趣的歷史。每個地圖可以導出
一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連接。所
以四色猜想是圖論中的一個問題。它對圖的著色理論、平面圖理論、代數拓撲圖論
　　等分支的發展起到推動作用。