Quod Erat Demonstrandum

2008/03/30

從握手到不動點(一)

Filed under: Junior Form Mathematics,Pure Mathematics,Teaching — johnmayhk @ 4:52 下午

從握手到不動點(一)

上年,應同學的邀請,我講了一個所謂的數學講座。今年,趁數學周將至,讓我在此也講一些數學。因我希望中一至中七的同學也能看明白,我會盡量詳盡(長氣)地說。

(一)握手定理(Handshaking lemma)

在空間中隨便點一些點,如下

隨意在點與點之間連起線段,如下

這樣,我們得出一個簡單的圖(graph)。對於圖中的每一點,我們可以定義該點的度數(degree),就是有多少條線由該點引出。參考上圖,因有 2 條線段由 A 點引出,故A 點的度數是 2。把上圖每點的度數寫出來,情況如下:

把上圖所有點的度數加起,就是上圖的總度數,即 0 + 1 + 1 + 2+ 3 + 1 + 2 = 10,得到一個偶數(even number)。小習題,試計算下圖的總度數。

答案是16,也是偶數。現在問:能否畫出一個圖,其總度數是奇數(odd number)?告訴你:不能。這就是所謂的『握手引理』(Hand-Shaking Lemma):圖的總度數一定是偶數。(換一個講法:奇度數的點之數目必然是偶數。)

這個定理的證明相當簡單,想像圖中的點代表某宴會的出席者,他們在會中彼此握手。如果 A 君和 B 君握手,我們便把對應的 A 點和 B 點連起。所以 A 點的度數,就是 A 君握手的次數。由於 A 君和 B 君握手的同時,B 君和 A 君也在握手,所以數算會中的總握手次數時,必然是算了兩次(double counting),亦即是說,會中的總握手次數必然是偶數,即圖的總度數是偶數。

要欣賞數學之美,其中一個方向是:一些有趣而不直觀的結果,原來可以從一些看來不起眼,非常簡單的原理得到。如此簡單的握手定理,可以推論一個有趣的結果:Sperner 引理。

(二)Sperner 引理

考慮一個大三角形 △V_1V_2V_3,在三條邊上隨意加點,見下圖。

現在為那些點標號,規則是,

V_1V_2 上的點,只能標號 1 或 2;
V_2V_3 上的點,只能標號 2 或 3;
V_3V_1 上的點,只能標號 3 或 1。

比如,我們可以有:

好了,現在大三角形內也隨意加點,亦隨意地為那些點標上 1,2 或 3 的其中一個號碼。同時,頂點 V_1, V_2, V_3 也分別標上 1,2 及 3 三個號碼,見下:

這時,我們可以利用大三角形內的點作頂點,把大三角形劃分為細小的三角形(這過程有稱為三角化 triangulation),見下:

頗亂的圖啊!但原來圖中是隱含『玄機』:就是無論你如何標上號碼,總會出現以『123』為頂點的小三角形,見下:

"必然存在以『123』為頂點的小三角形"此之謂 Sperner 引理也。為何會出現這個現象?原來是握手定理。

考慮已細分為若干小三角形的圖,在每個小三角形面上加上一個紅點,見下:

在大三角形外,也補加一個紅點(即上圖的 A 點)。現在把紅點按以下規定連起:若兩相鄰小三角形的公共邊的頂點是『12』,則連起該兩個三角形上的紅點。另外,外點 A 也連到鄰近的紅點,如果 A 和該紅點以頂點是『12』的線段分隔,見下圖。

紅色部分,形成了下面的一個圖(graph)

圖中,除 A 點外,紅點的度數只能夠是 0,1 或 2。特別看看 B 點,其度數是 1。看看再上一個圖,B 點是落在以『123』為頂點的小三角形中。不難想出,度數是 1 的點,必然落在以『123』為頂點的小三角形中。換句話說,要證明存在以『123』為頂點的小三角形,即要證明存在度數為 1 的點。

如何證明?看看 A 點,其度數是 3,是奇數。其實,無論如何標號,A 點的度數一定是奇數。因為,在線段 V_1V_2 中,以『12』為端點的線段(姑且稱它做"『12』線段")之數目必然是奇數。為何?我們只要想想,在線段 V_1V_2 上每加多一點,則『12』線段之數目有何改變?我們只能出現以下兩種情況:

(情況A) 該點加在某條『12』線段中,即

這樣,無論加上去的(藍色)點的標號是 1 或 2,我們也沒有增加線段 V_1V_2 上『12』線段之數目。

(情況B) 該點加在某條頂點標號相同的線段(即『11』線段或『22』線段)中,如果加上去的(藍色)點的標號和線段開端的標號相同,見下圖,則我們也沒有增加線段 V_1V_2 上『12』線段之數目。

如果加上去的(藍色)點的標號和線段開端的標號不同,見下圖,則我們增加了兩條『12』線段,即線段 V_1V_2 上『12』線段之數目增加了兩條。

總結上述兩個情況:在線段 V_1V_2 上每加多一點,『12』線段之數目或無增加,或增加兩條。但一開始,未加點的時候,線段 V_1V_2 其實是一條『12』線段,即『12』線段的數目是1;那麼,無論怎麼加點,『12』線段的數目必然是奇數。

好了,握手定理出場!由剛剛的討論,下圖(是之前出現過的紅色圖)中, A 點的度數是奇數。

如果圖中沒有一點的度數是 1,則圖的總度數也是奇數(因為除 A 點外,其他點的度數是 0 或 2),這就有違握手定理所指:圖的總度數必是偶數這個事實。亦即是說,度數是 1 的點必然存在;亦即是說,『123』小三角形也必然存在。

想多了解 Sperner 引理,請參考:
http://en.wikipedia.org/wiki/Sperner’s_lemma

好了,我們已經過了兩大關:由握手到 Sperner,還有第三關,我們就看到一個非常漂亮的不動點定理,不過都是下次再談。

P.S. 好想問初中的同學,上面一篇,你看得明嗎?

4 則迴響 »

  1. I don’t wanna understand what that is…
    Sorry for occupying your time, but I couldn’t find anyone better than you… Anyway, I hope you weren’t late…
    Oh, I don’t have the celebration in CUHK… just at home, that’s all…

    迴響 由 Ed — 2008/04/02 @ 7:52 下午 | 回覆

  2. i could just understand the handshaking lemma- –

    迴響 由 SP Loa — 2008/04/02 @ 11:53 下午 | 回覆

  3. 多謝大家的回應,你們的意見總比我自說自話好!

    迴響 由 johnmayhk — 2008/04/05 @ 9:12 上午 | 回覆

  4. 看了多少youtube影片都沒弄懂,看一次你解說就懂,專業啊!!!!!!!!!

    迴響 由 catq — 2016/05/20 @ 4:22 上午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: