对一道面试题的总结与扩展思考(关于一笔画问题的数学分析)
摘要
前幾天參加了一個公司的面試,其中被問到了一個題。面試官在紙上畫了一個圖形(具體圖形見下文),問我能不能一筆畫出這個圖形,要求每條邊必須只走一次,并且畫的過程中筆不能離開紙。當(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Nginx模块开发入门
- 下一篇: 算法时间复杂度分析基础