搞懂圖論 (一)：研究圖論的一個動機

對於圖論這個話題，僅在知乎上就可以找到不少優秀答案。大家的出發點和目的各自不同，有時候為了嚴謹性，不得不將一些概念描述得佶屈聱牙。本系列的目標很明確，儘可能地繞過嚴謹的數學鋪墊，採用直覺的方式儘快將一些概念串聯起來；希望在大家沒入細節之前，給圖論鋪墊一個相對完整的圖景。我爭取：

能畫圖的，絕不寫字。能寫字的，絕不用公式

。

首先，這裡假設感興趣的知友已經瞭解了圖論中一些最最基本的概念，比如什麼是“節點”，什麼是“邊”，什麼是“度”，以及知道如何畫“圖”（如標題配圖）。這些入門內容在網路上早已汗牛充棟，如非必要，這裡就不再贅述了。況且，圖論的基礎術語相當易懂，半個小時就能摸個門兒清了。

第一部分內容主要想闡述我們為什麼要研究圖論，即圖論的動機。本人初次接觸圖論是在學習

圖神經網路

的時候，顯然，這是圖論相當新的一個應用領域。一開篇，往往是類似“XX 方法不能很好地解決 XX 問題，圖神經網路應運而生”這樣的話，彷彿圖論能解決的問題與 XX 方法能解決的問題是割裂的。可事實是，圖是一個高度抽象化了的概念，其強大使之得以描述一切結構。

簡單和複雜

且直接看圖：

圖一、一個圖結構。

倘若我問：這個圖想表示什麼？很多知友可能會很迷惑，甚至不清楚到底在問什麼。這個圖結構怎麼翻來覆去瞧，都是“一眼看得到底”的那種，過多的描述不過是來來回回地重複廢話罷了。沒錯，

這個圖結構是可以透過直覺領會的

，或者說，這就是刻在我們直覺裡的。一個證據就是：哪怕咱讓一個從沒有聽說過圖論（但受過良好教育）的朋友來瞧一眼，就算隔上一整天，他/她也能夠輕鬆地憑著記憶在紙上覆現出來。現在，再看下一個圖結構：

圖二、另一個圖結構。

此時，倘若我再問一遍先前的問題，大家應該會覺得，這個問題已然不似上一個場景中那般空洞、沒有意義了。我相信絕大多數知友僅透過看一眼，並不能知道這圖究竟想表示什麼（包括我自己，如果我不知道自己在畫啥的話）。讓我和這圖死磕一分鐘，即便某一刻我認為自己記住它了，也無法保證在五分鐘之後不忘個一乾二淨。可是，我們整理一下呢？

圖三、結構等價於圖二。

好像。。。嗯，先按下不表，再來看一個圖。同樣，我認為大多數知友依舊無法一眼洞清：

圖四、又一個圖結構。

老規矩，整理一下：

圖五、結構等價於圖四。虛線並不代表特殊的連線，只是為了強調其三維結構。

大家不妨驗證一下圖二和圖三、圖四和圖五是不是完全相同的圖結構。直覺讓我們把一些習以為常的圖結構、節點關係看得異常“簡單”，卻忽視了它們同樣有可能以一種異常“複雜”的形態展示出來。同理，一些看似“複雜”的結構背後也有著能夠被直覺把握的“簡單”。而

圖論則把簡單或複雜的結構用代數的形式統一了起來，使我們不耽於表象。

“近”

那麼，說這些又有什麼意義呢？畢竟這篇文章的主旨並不在討論哲學和人生感悟。我們且看一下，上面這些圖分別可以對應什麼樣的資料吧。

圖六、一維音訊訊號，二維彩色圖片，三維腦成像。來源：網際網路公開圖片。

圖一顯然可以對應一維的音訊訊號，每個節點代表一個取樣點，然後將它們串聯在一根“軸”上。圖三可以對應圖片資料，每個節點就是一個畫素，而節點值可以是 RGB 三元組；此時，若想描述畫素與畫素之間的關係，僅憑橫向串聯是不夠的了，還需加上縱向串聯，因為我們要處理的是一個“面”，而不再是一根“軸”。同理，圖五可以對應三維資料，這裡就不贅述了。

一起回顧一下這三類資料都會用的一個常用操作——

求導

。先以一維為例，對於熟悉訊號處理的知友而言，最簡單的求導方式就四個字：

錯位相減

。如果橫軸單位也很重要的話，比方說資料是一段 44。1 kHz 取樣率的音訊，那麼我們還可以整體除以

秒以保持其物理意義。對於二維影象資料，求導在操作上稍有不同，但本質上依舊類似錯位相減，不過注意了：二維需要考慮兩個方向，所以我們會有兩個分別對應了橫、縱的

3x3 大小

的求導核。

圖七、最簡單的二維求導卷積核。

基於實際需求和不同考量（例如降噪），對離散資料求導的定義可能不盡相同，但是，不論是錯位相減、圖七列出的求導核，還是其他演算法、其他求導核，都遵循了一個共性，即

區域性性

。畢竟，很難想象讓一段音訊序列的最後一個數減去第一個數——這種喪失了局部性的操作能和導數扯上什麼關係。於是，這就引出了本小結的標題，什麼是“近”？一維、二維、三維、線、面、體，我們的日常經驗是被歐式空間主宰的，而歐式空間本身是個度量空間，天然的距離概念可以完美定義“近”。我們在寫下求導核的時候，其實就已經默認了一個特定的圖結構——網格結構，而這種結構正是歐式距離意義下的“近”等價於圖意義下的“近”的直接結果。特別注意這裡的先後順序：

預設圖結構在先，定義求導在後

。

圖論給了我們定義連線的權力，也就給了我們肆意定義結構、定義“近”的權利。

一旦有了這樣的權力，我們便突然發覺：從歐式空間繼承而來的網格結構不過是太倉稊米，對於 99。999。。。 % 的結構而言，剛才說的什麼縱、橫、甚至維度都是沒有意義的。這就打開了一個新世界的大門，我們又該如何在任意的結構中重新定義（推廣）各種曾經熟悉的操作呢？

本系列的側重

當然，僅僅是結構的多樣性就足夠數學家們把玩一輩子了。所以我們在接觸圖論伊始，瞭解到的都是類似於樹、二分圖、全連線、子圖這樣的描述結構的術語，至於節點的具體代表什麼，是一個數字？一個 RGB 畫素？還是一個社交網路中的賬號？數學家們是不屑的。不過我們還是要回到具體問題上，這也是本系列的側重。

額外有一點必須宣告，

以上探討的內容絕不是圖論發展的歷史動機

。但是，從歐式空間引出網格結構，在從網格結構反觀廣義上的圖，個人認為不妨是一個易於理解的切入點。在下一章裡（也可能若干章，如果內容龐雜的話），我想接著探討一下圖論中最終要的一個概念：

拉普拉斯矩陣

，以及緊隨其後的

特徵值、特徵向量

。