圖論是數學的一個分支，它以圖為研究對象。通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係。
數學遊戲，作為一種運用數學知識的大眾化的智力娛樂活動，因其趣味性，往往容易激發人們的數學熱情與興趣，因而對普及數學而言是非常有益的。
另一方面，從歷史角度看，數學遊戲還曾對數學的發展起到過重要而積極的作用。特別是，它曾直接導致過新的數學分支圖論的創立(遊戲的發明者則是哈密頓)。
01
哈密頓（1805～1865），愛爾蘭數學家，數學史上諸多早熟的天才之一。他於1805年出生在都柏林。當他大約1周歲時，父母把他交給一位叔父撫養並進行教育。這位叔父是個語言學家，在他的培養下，天賦超群的哈密頓3歲時就能順利地讀英文；5歲就能讀能譯拉丁文、希臘文和希伯來文；8歲時又掌握了義大利文和法文；不到10歲就學阿拉伯文和梵文。14歲時他用波斯文寫信給當時正在訪問都柏林的波斯大使。15歲那年，一件偶然的事件改變了他的興趣與生活道路。當時，一個美國青年科爾布恩在都柏林表演了他的快如閃電的計算能力。「後來很長一段時間」，哈密頓後來寫道，「我喜歡心算很長的算術運算，開平方和開立方，以及每一件與數的性質有關的東西。」最後，他決心終身從事數學。他宣稱：「再沒有比研究科學更能提高人的心靈，更能把一個人提高到眾人之上的了。誰不願意享有阿基米得的名聲……呢？」
1823年，這位神童進入都柏林的三一學院。21歲時，他提交了一篇重要的有關光學的論文。1826年，尚未大學畢業的哈密頓當選三一學院天文學教授職位。1835年，哈密頓獲爵士稱號，兩年後又當選為愛爾蘭皇家科學院主席。
事業上的成功卻沒有給他帶來個人生活的幸福。他於1833年結婚，妻子「極為羞怯，又極為纖弱」。在這一不幸的婚姻中，哈密頓夫人難以勝任家務且常常生病，結果導致悲慘的哈密頓食無定時，酗酒到危險的程度。當他去世後，人們看到他的工作房間因長期無人打掃而變得如豬圈一般：房間裡堆滿了像小山一樣的紙張，而紙堆中竟然夾雜著大量的盤碟與剩下的飯菜。
02發明週遊世界遊戲，播下了圖論誕生與發展的種子。
哈密頓在數學方面主要研究代數，其最重要的貢獻是在1843年發現了四元數。把他與圖論聯繫在一起的是他提出的一個趣味問題：從正十二面體（共有20個頂點）的一個頂點出發，沿著邊行進，把20個頂點無遺漏地全部通過，每一頂點只許過一次而回到原處。問這種走法是否存在。將這一問題略加轉化，哈密頓於1857年發明了著名的週遊世界遊戲，並以25英鎊把這個遊戲賣給一家公司。後來，這一遊戲還進入了市場。
遊戲的道具由一個木製的正十二面體構成，正十二面體的每個稜角上標有一個當時非常有名的城市。遊戲目的是環繞世界旅行，其要求是尋找一個環遊路線，使得：沿正十二面體的稜，從一個「城市」出發，經過每個城市恰好一次，最後回到原出發點，並且經過的稜不許重複。
為了容易記住哪些城市已被遊覽過，在每個稜角上放一個釘子，再用一根線繞在那些旅遊過的城市（釘子）上，由此就獲得旅程的一個直觀表示。後來，人們發現這個道具不好用，因而誕生了與正十二面體等價的平面木板狀版本。可惜，這個遊戲的商業運作是失敗的，玩具商沒有從這一遊戲中賺到錢。但在數學史上，哈密頓週遊世界的遊戲和歐拉的七橋問題是兩例標誌性建築，播下了圖論誕生與發展的種子。
如下圖給出了這遊戲的一種正確玩法。
讓我們對照一下歐拉與哈密頓研究的問題。歐拉要求在一個圖中尋找滿足「從一個頂點出發，沿邊行進，無遺漏走遍所有的邊，每一邊只許經過一次回到出發點」的路線，這樣的路線後來在圖論中被稱為歐拉迴路。而具有歐拉迴路的圖稱為歐拉圖。與之表面相似，實際完全不同的哈密頓問題則要求在一個圖中尋找滿足「從一個頂點出發，沿邊行進，無遺漏地通過全部頂點，每一頂點只許過一次而回到出發點」的路線，這樣的路線後來在圖論中被稱為哈密頓圈，而具有哈密頓圈的圖稱為哈密頓圖或說圖是哈密頓的。
歐拉問題與哈密頓問題已經成為現在圖論的重要組成部分。令人感到驚奇的是，對歐拉問題，我們已經有了簡單、漂亮的結果：一個連通圖存在歐拉迴路若且唯若它的所有頂點都是偶頂點。然而對哈密頓問題即「一個給定的連通圖是否存在哈密頓迴路」，至今仍然是圖論中一個尚未解決的著名難題。數學家們經過努力得到了一些存在哈密頓迴路的必要條件與充分條件，但至今還沒有得到充要條件。
歐拉七橋問題與哈密頓週遊世界遊戲是兩例標誌性建築，它們播下了圖論誕生與發展的種子。這門一開始以遊戲形式出現，而且此後也一直沒有完全失去這一特點的數學分支，在20世紀得到迅速發展，已經成為十分有用的重要數學分支。
圖論以圖為研究對象。所謂圖，就是一些點與某些點之間的連線（稱為邊）的集合。這裡，我們僅介紹其中幾個簡單的名詞。
如果e=uv是圖的邊，則稱u和v是鄰接的頂點，頂點u和v互稱為鄰點。一個點的相鄰點的個數稱為這個點的次數（或度）。如果一個圖中，每一個頂點都可以通過邊到達任何其他頂點，我們就稱這個圖是連通圖。
如果一個圖可以畫在平面上使得其中各條連線彼此不相交，那麼這個圖叫做平面圖。當然，有些圖（如下面的左圖）初看起來不是平面圖，但經過適當的移動（將AB邊拉出來，從外面走），就可以變成沒有相交連線的平面圖，這種圖稱為可平面化圖，或者稱為可以嵌入到平面的圖。兩個圖的點數相同，邊數相同，點與邊的關係也相同，稱為兩個同構圖。
還有的圖無論怎麼做都不能變成平面圖，這種圖稱為不可平面化的圖。最典型的不可平面化的圖一個稱為K5，一個稱為K3，3，如下圖所示。
1930年，波蘭數學家庫拉託夫斯基得出一個著名結論：圖G可平面化若且唯若G不包含K5或K3，3的剖分圖。所謂剖分圖，就是在原圖的邊上任意添加一些頂點所得到的圖。
03四色問題
圖論中最著名和最具啟發性的問題之一是四色問題:「平面上繪製的任何地圖，其區域都可能被塗上四種顏色，以至於任何兩個邊界相同的區域都有不同的顏色，這是真的嗎?」
這個問題最早是由弗朗西斯·格思裡在1852年提出的，它的第一個書面記錄是在同年德·摩根寫給漢密爾頓的一封信中。提出了許多不正確的證明，包括Cayley、Kempe等人的證明。
四色問題曾在近代圖論發展中起過重要作用，那麼這個地圖染色問題是如何與圖論聯繫起來的呢？為建立起圖論與地圖著色問題之間的聯繫，數學家引入了對偶圖的概念。
四色猜想是一個區域的染色問題，它可以看做是圖的面染色。對此問題可以換一種角度考慮：在地圖的每一個區域內取一點，為了形象，不妨設想這點是區域的首都，然後將有公共邊界國家的首都用線聯結，由此得到一個由點與線構成的新圖。每張地圖都有的這個與之關聯的圖稱為其對偶圖。圖中的點稱為頂點，圖中的線稱為邊。圖中有邊相連的兩點稱為相鄰點。顯然，一地圖中兩個頂點是相鄰點若且唯若它們所對應的區域有公共邊界。
地圖的對偶圖具有一個特點：其邊除了可能在頂點上相交外，都無其他交點。用我們上面剛引入的術語來說，就是每張地圖的對偶圖都是平面圖。反之，每個連通的平面圖都是某個地圖的對偶圖。於是，在經過這種轉化後，地圖中的面著色問題等價於平面圖中的頂點著色問題，而「有公共邊界的國家著不同的顏色」變為「每條邊的兩個端點著不同的顏色」。而四色猜想在其對偶圖中等價於：對一個平面圖上的頂點染色，使相鄰兩頂點顏色相異，至多用四種顏色就夠了。如果把平面圖頂點染色所需要的最少顏色數稱為平面圖的色數，則四色猜想也等價於說：每個平面圖的色數至多是4。
在引入對偶圖後，我們還可以做另一種轉換。考慮對所得的平面圖進行邊染色。即讓一個圖的每邊染一種顏色，並使有公共頂點的邊（稱為相鄰邊）有不同的顏色，這樣的染色稱為邊染色。同樣的，如果把平面圖邊染色所需要的最少顏色數稱為邊色數，則四色猜想等價於：每個平面圖的邊色數至多是4。
這樣，四色問題被帶進了圖論領域，並轉化為圖論的著色問題。
04圖論和應用非常廣泛，充滿活力
雖然組成圖的頂點和邊看似十分簡單，我們卻可以用之模擬生活中很多的活動，包括人際關係，路線問題，通訊系統，計算機問題。通過圖論，我們可以把頂點當做一個人，而連接兩個頂點的邊表示兩個人是朋友，我們可以通過圖論證明出拉姆西難題：在隨意湊齊的六個人中，一定能找到彼此認識或者彼此不認識的三個人。通過圖論，我們若將邊加上重量，我們就可以用此模擬優化問題，這些問題在計算機中被稱作貨郎擔問題，是計算機學科中經典的NP問題，正被無數數學和計算機學科中的精英研究著。
這就是圖論的魅力了，你感受到了嗎？
圖論是近年來發展十分迅速的一個應用數學分支。當前，圖論在自身理論研究取得重大進展的同時，也成為解決數學其它領域問題的重要手段，作用日益凸顯。此外，作為網絡建模的基本理論與方法。
今天，圖論已廣泛應用在計算機科學、運籌學、控制論、資訊理論等學科中，成為對現實世界進行抽象的一個強有力的數學工具。數學問題的提出與解決，推動了數學的發展。我們今天學習歐拉的成果不應是單純把它作為數學遊戲看待，重要的是應該知道他是怎樣把一個實際問題抽象為數學模型，然後用數學的方法研究它，再用來解決實際問題。這樣循環往復，螺旋上升，永無止境。