摘要

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

問題的提出

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

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

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

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

圖論中的一些概念

因?yàn)樵谙挛恼撌鲞^程中需要用到一些圖論的基本概念，為了照顧在這方面不熟悉的朋友，我先將要用到的定義和概念列出來，如果您對圖論的基本內(nèi)容已經(jīng)了然于胸，可以跳過這一節(jié)。另外如不做特殊說明，下文所有的“圖”都默認(rèn)指“無向圖”，本文的討論不涉及“有向圖”。

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

多重圖——簡單圖不允許同一組頂點(diǎn)對在E中出現(xiàn)兩次，即一對頂點(diǎn)間最多只有一條邊。如果在簡單圖的基礎(chǔ)上允許任一組頂點(diǎn)對間有任意條邊，則簡單圖變?yōu)槎嘀貓D。

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

頂點(diǎn)的度——一個頂點(diǎn)的度是這個頂點(diǎn)所連接的邊的條數(shù)。

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

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

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

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

一筆畫問題的抽象

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

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

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

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

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

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

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

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

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

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

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

當(dāng)從x1走到x2，O(x1)變?yōu)?，而I(x2)變?yōu)?。我們可以想象，除起始頂點(diǎn)和終止頂點(diǎn)外，其它頂點(diǎn)當(dāng)走完這個歐拉跡時，I(x)一定等于O(x)，因?yàn)閷τ谶@些頂點(diǎn)，一次進(jìn)入必然對應(yīng)著一次離開。而起始頂點(diǎn)的不同在于，它多一次離開（第一步），所以I(x1)+1=O(x1)，同理，終止頂點(diǎn)多一次進(jìn)入（最后一步），I(xm)=O(xm)+1。

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

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

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

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

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

上圖我們只證明了條件的必要性，這只能告訴我們?nèi)绾闻袛嘁粋€圖不存在歐拉跡，那么如果一個圖所有頂點(diǎn)都是偶數(shù)度或恰好有兩個頂點(diǎn)是奇數(shù)度，那么是否可以確定這個圖存在歐拉跡呢？也就是說，問題一中的條件是否是充分的？

不賣關(guān)子，我很高興的告訴大家，那個條件確實(shí)是充分的。也就是說，一個無向一般連通圖G存在歐拉跡的充分必要條件是G中所有頂點(diǎn)均具有偶數(shù)度或恰好有兩個頂點(diǎn)具有奇數(shù)度。但是這個定理的數(shù)理證明十分復(fù)雜，我實(shí)在沒有興趣在這里證明，因?yàn)槲蚁嘈糯蠹乙欢]有興趣看一堆公式。因此，我放棄對充分性進(jìn)行數(shù)理證明。這個證明過程可以在機(jī)械工業(yè)出版社的《組合數(shù)學(xué)》（Richard A. Brualdi著）一書的第302-303頁找到，有興趣的朋友請參看。

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

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

這個算法相當(dāng)簡單：

1、設(shè)頂點(diǎn)集合W，邊集合F，均初始化為空集。

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

3、如果所有邊都已進(jìn)入F則終止，否則進(jìn)入4。

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

5、回到3。

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

總結(jié)

下面總結(jié)一下一筆畫問題相關(guān)的幾個定理，記住這些，一筆畫問題應(yīng)該就難不倒你了。

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

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

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

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

擴(kuò)展閱讀

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

from:?張洋

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。