文集簡介

這個文集是John Adrian Bondy的Graph Theory An Advanced Course一書的筆記，包括內(nèi)容梳理與習(xí)題解答，當(dāng)然也會加入一些筆者個人認(rèn)為比較有趣的內(nèi)容，但主體仍然大部分來自于本書。在之后可能會出現(xiàn)的其他文集中，筆者會介紹一些圖論學(xué)科與其他學(xué)科交叉的內(nèi)容或一些有意思的結(jié)論，包括為人津津樂道的“六度分隔理論”（小世界理論）等。

祝大家和筆者自己學(xué)習(xí)愉快！

圖論的起源

圖論是一門比較古老的數(shù)學(xué)分支，普遍認(rèn)為圖論起源于十分有名的哥尼斯堡(Konigsberg)七橋問題，哥尼斯堡位于如今的俄羅斯飛地加里寧格勒州，歷史上它曾經(jīng)屬于普魯士公國，聞名于世的七橋問題也誕生在這個時期。

問題的背景相當(dāng)簡單，是一個經(jīng)典的“一筆畫”問題：

這種一筆畫問題在圖論中被稱作“連繪圖”問題，當(dāng)時有許多人對這個問題感到好奇并嘗試將其解決但始終無果，這個問題最終被當(dāng)時訪問哥尼斯堡的大數(shù)學(xué)家歐拉(Euler)解決。1736年，歐拉向圣彼得堡科學(xué)院提交了論文《哥尼斯堡七橋》，在徹底解決了這個問題的同時開創(chuàng)了一個對后世產(chǎn)生了深遠(yuǎn)影響的數(shù)學(xué)學(xué)科——圖論(Graph Theory)，這一學(xué)科對后來的數(shù)學(xué)研究乃至計算機(jī)科學(xué)的發(fā)展產(chǎn)生了巨大的作用。歐拉不愧是偉大的數(shù)學(xué)天才，和他同一個星座筆者感到十分榮幸。

那么話說回來，歐拉是怎么解決這個問題的呢？他將地圖中的每一個地區(qū)抽象為一個點(node)，而將“兩地之間有橋連接”這種事實抽象為兩個點之間有邊(edge)連接，那么原本的七橋問題就可以換一種表述方式：“是否能找到一條路徑將每條邊經(jīng)過且僅經(jīng)過一次，并回到出發(fā)點？”，這樣的路徑在之后的圖論研究中被稱作歐拉回路(Euler circuit)，關(guān)于歐拉回路的性質(zhì)以及相關(guān)算法將在文集的后續(xù)筆記中介紹，歐拉通過七橋問題給出了一筆畫問題（對無向圖而言）有解的必要條件，即該圖聯(lián)通，且所有節(jié)點度數(shù)都是偶數(shù)。之后這個條件也被證明是一個無向圖存在歐拉回路（或者說是該圖的一筆畫問題有解）的充要條件。

?

?

本文用word編寫，故而書寫公式及排版方面很不方便，因此這篇就只水這么一點內(nèi)容，下篇筆記將開始介紹圖論這一學(xué)科中經(jīng)典的研究對象與概念，隨機(jī)更新，但應(yīng)該不會晚于5月15日，彼時篇幅也將加長。

圖片來自網(wǎng)絡(luò)，侵刪。