摘要

前幾天參加了一個公司的面試，其中被問到了一個題。面試官在紙上畫了一個圖形（具體圖形見下文），問我能不能一筆畫出這個圖形，要求每條邊必須只走一次，并且畫的過程中筆不能離開紙。當時我沒有試著去畫 ，而是憑著自己圖論方面的知識在幾秒鐘之內告訴面試官不可能做到，然后簡單說了一下理由。面試結束后我翻閱了圖論相關的資料，發現當時自己雖然給出了正確答案，但理由并不完全正確。昨天我花了幾個小時仔細研究了一下相關的理論，總結了一下這類問題的類型和解法，寫成此文，分享給大家。

問題的提出

當時面試官給我出的問題是這樣的：對于下面這個圖形，讓我一筆畫出，要求每條邊必須只走一次，并且畫的過程中筆不能離開紙。

面試時我給出的回答是不可能做到，面試結束后我也從數學上證明了這個這個回答。當然有興趣的朋友可以試著畫畫看。

這個問題其實就是我們小時候會玩到的一筆畫游戲。這類問題看似簡單直觀，但是仔細研究下來卻蘊含了很多東西，而且涉及了圖論中一個非常重要的研究課題——歐拉跡。而且這類問題可以擴展出很多東西，例如任意給一個圖可不可以完成一筆畫且最后回到起始點？再如到底什么樣的圖可以一筆畫出來？什么樣的圖一筆畫不出來？如果一個圖可以一筆畫出來，那么應該如何畫？有沒有對一切可一筆畫圖形的通用解法？

下面我們將這個問題抽象成一般問題，然后從圖論角度尋找上述疑問的答案。

圖論中的一些概念

因為在下文論述過程中需要用到一些圖論的基本概念，為了照顧在這方面不熟悉的朋友，我先將要用到的定義和概念列出來，如果您對圖論的基本內容已經了然于胸，可以跳過這一節。另外如不做特殊說明，下文所有的“圖”都默認指“無向圖”，本文的討論不涉及“有向圖”。

簡單圖——一個簡單圖可表示為G=(V, E)，其中V是頂點集合，其中每個元素是圖的一個頂點；E是邊集合，其中每一個的元素是一個頂點對(a, b)，其中a和b均屬于V，這個頂點對表示頂點a和b間有一條邊相連。

多重圖——簡單圖不允許同一組頂點對在E中出現兩次，即一對頂點間最多只有一條邊。如果在簡單圖的基礎上允許任一組頂點對間有任意條邊，則簡單圖變為多重圖。

一般圖——如果在多重圖的基礎上允許自關聯邊，即允許(a, a)這樣的頂點對出現在E中，則這種圖叫一般圖。（我們后續所有討論的對象都是一般圖，如不做特殊說明，下文所有的“圖”均指一般圖）

頂點的度——一個頂點的度是這個頂點所連接的邊的條數。

連通圖——如果一個圖任意兩個頂點之間都存在由邊組成的通路，則這種圖叫連通圖。（我們后續所有討論的對象都是連通圖，如不做特殊說明，下文所有的“圖”均指無向一般連通圖）

途徑——在一個圖G中，{x1, x2}, {x2, x3}, …, {xm-1, xm}叫做G的一個途徑，如果x1和xm為同一頂點，則說這個途徑是閉的，否則說這個途徑是開的。

跡——如果一個途徑中沒有重復的邊，則這個途徑叫做“跡”。

歐拉跡——如果圖G的一個跡包含了G所有的邊，則這個跡叫做“歐拉跡”。

一筆畫問題的抽象

有了上面的定義，我們就可以用數學語言描述一筆畫問題了：

所謂一筆畫問題，就是給定一個無向一般連通圖，這個圖存在歐拉跡的充分必要條件是什么？如果存在歐拉跡，如何求歐拉跡？

這個問題很龐大，我們化整為零，分幾步去討論。另外，為了避免枯燥無味，我將不會從絕對嚴格的數理層面去做推理和證明，而是用一些直觀的啟發式方法，盡量讓每位朋友都能讀懂。

問題一：圖G存在歐拉跡的必要條件是什么？

首先，我們來推導G存在歐拉跡的必要條件。雖然滿足必要條件不能充分證明G一定存在歐拉跡，但是不滿足必要條件就一定不存在歐拉跡。所以搞清這個問題，可以用來幫助我們判斷出顯然不能一筆畫出的圖。

歐拉跡分為開歐拉跡和閉歐拉跡，我們先討論開歐拉跡的情況。

現已知圖G存在開歐拉跡（等價于存在一筆畫畫法，并且這種畫法在完成時不會回到起始頂點），那么可以推導出什么？

現在我們這樣想：設{x1, x2}, {x2, x3}, …, {xm-1, xm}是G的一條開歐拉跡，那么{x1, x2, …, xm}是這條歐拉跡所經過的頂點的序列。需要注意，這里除了x1和xm一定不是同一頂點，其它很多頂點可能是相同的。因為歐拉跡只要求每個邊出現且僅出現一次，但不限制同一頂點出現幾次。例如下圖：

其中{a, b}, {b, c}, {c, a}, {a, d}, {d, e}, {e, c}是一個開歐拉跡，頂點序列為{a, b, c, a,d, e, c}。

現在我們這么考慮這個問題，對于某一頂點x，I(x)表示歐拉跡中進入x的次數，即走整個歐拉跡過程中從x以外的頂點進入x頂點的次數，O(x)，表示離開x的次數，即當前在x頂點，然后離開x到其它頂點的次數。

我們順著開歐拉跡走，對于所有頂點此時I(x)和O(x)均為0，當前筆觸在x1處。

當從x1走到x2，O(x1)變為1，而I(x2)變為1。我們可以想象，除起始頂點和終止頂點外，其它頂點當走完這個歐拉跡時，I(x)一定等于O(x)，因為對于這些頂點，一次進入必然對應著一次離開。而起始頂點的不同在于，它多一次離開（第一步），所以I(x1)+1=O(x1)，同理，終止頂點多一次進入（最后一步），I(xm)=O(xm)+1。

我們還體會到這樣一個事實：對于任意頂點，每一個進入和每一個離開都消耗此頂點的一個度。因為歐拉跡不允許重復邊，所以每一次進入和離開一定是走以前沒有走過的邊，因此頂點x的度為I(x)+O(x)。這樣可以得出結論：如果G存在一個開歐拉跡，那么起始頂點和終止頂點的度數為奇數，而其它頂點的度數為偶數。

再來考慮G存在閉歐拉跡的情況。根據上述思路，如果歐拉跡時閉的，則起始頂點和終止頂點為一個頂點，而這個頂點剛好多一個進入（最后），多一個離開（開始），這么一加，這個頂點的度也一定為偶數，其它頂點的度的推理與開歐拉跡相同。所以可以得出結論：如果G存在一個閉歐拉跡，那么G所有頂點的度均為偶數。

綜上可以得出，一個圖G存在歐拉跡的必要條件是所有頂點的度數均為偶數或恰好有兩個頂點度數為奇數。從邏輯上說，如果一個命題成立，則其逆否命題也成立，我們可以得到推論：如果一個圖G不是所有頂點都具有偶數度，也不是恰好有兩個頂點為奇數度，則G一定不存在歐拉跡。

現在我們再來看看最初的那個面試題：那個圖有四個頂點的度為3，所以根據上述分析，那個圖一定不存在歐拉跡，即不可能一筆畫出。

問題二：圖G存在歐拉跡的充分條件是什么？

上圖我們只證明了條件的必要性，這只能告訴我們如何判斷一個圖不存在歐拉跡，那么如果一個圖所有頂點都是偶數度或恰好有兩個頂點是奇數度，那么是否可以確定這個圖存在歐拉跡呢？也就是說，問題一中的條件是否是充分的？

不賣關子，我很高興的告訴大家，那個條件確實是充分的。也就是說，一個無向一般連通圖G存在歐拉跡的充分必要條件是G中所有頂點均具有偶數度或恰好有兩個頂點具有奇數度。但是這個定理的數理證明十分復雜，我實在沒有興趣在這里證明，因為我相信大家一定沒有興趣看一堆公式。因此，我放棄對充分性進行數理證明。這個證明過程可以在機械工業出版社的《組合數學》（Richard A. Brualdi著）一書的第302-303頁找到，有興趣的朋友請參看。

問題三：如果圖G存在歐拉跡，如何求解？

知道了判斷歐拉跡存在性的充要條件，下面一個問題自然就是如果G存在歐拉跡，如何找出？

這個算法相當簡單：

1、設頂點集合W，邊集合F，均初始化為空集。

2、選擇一個奇數度點（開歐拉跡）或任意頂點（閉歐拉跡）賦值給x，并將x放入W。

3、如果所有邊都已進入F則終止，否則進入4。

4、選擇x連接的一條不存在于F中的邊(x, y)，將(x, y)放入F，將y放入W（如果y不存在于W的話），然后讓x=y。

5、回到3。

算法十分直觀，就不多做解釋，關于算法的正確性證明，有興趣的朋友請參考上文提到《組合數學》一書中的第301頁。

總結

下面總結一下一筆畫問題相關的幾個定理，記住這些，一筆畫問題應該就難不倒你了。

1、一個無向一般連通圖G可以一筆畫出的充分必要條件是G中所有頂點均具有偶數度或恰好有兩個頂點具有奇數度。

2、一個無向一般連通圖G可以一筆畫出且終止點不是起始點的充分必要條件是G中恰好有兩個頂點具有奇數度。

3、一個無向一般連通圖G可以一步畫出且最后回到初始點的充分必要條件是G中所有頂點均具有偶數度。

4、如果一個無向一般連通圖G不是所有頂點都具有偶數度，也不是恰好有兩個頂點為奇數度，則G一定不存在歐拉跡。

擴展閱讀

其實對一筆畫問題的最早研究可以追溯到歐拉（Leonhard Paul Euler）在1736年發表的一篇關于哥德堡七橋問題的論文。那篇論文中歐拉解決了著名的哥德堡七橋問題，并且開創了一個全新的數學分支——圖論與拓撲學。有興趣的朋友可以尋找相關材料閱讀。?

from:?張洋

總結

以上是生活随笔為你收集整理的对一道面试题的总结与扩展思考（关于一笔画问题的数学分析）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。