2007/10/23

An Algorithmic Proof

本週圖論作業最後一題,自認寫出一個還滿可愛的證明,貼在下面並附示意圖 XD。

題目:若樹 T 中任一與葉相鄰的點其度(degree)至少為 3,證明 T 中至少存在兩片葉有共同鄰居。

證明:任選一點為起點,在樹 T 中走出一條路徑(path)。一路上不會遇到先前出現過的點,否則會形成迴圈(loop)。因為點數有窮,終究會遇到一片葉子而停止。(遇到的點不是葉子的話,照定義其度數大於 1,而一定能繼續走下去。)路徑上倒數第二點的度數至少為 3,所以又可以從該點走出一條新的路徑。上述過程只有在「新路徑上的第一點為葉子」時才會終止,而且因為點數有窮而一定得終止。此時我們就找到有共同鄰居的兩片葉子。

--
很顯然是個 linear time 的演算法 XD。(其實就是 DFS 的特化版嘛 XD。)

Labels:

Anonymous hcsoso10/24/2007 3:15 pm 說:

那天TA hour出現了一個極為神妙的proof ;]

噢對了,我是顯之你好:P
自從發現都有修圖論之後,潛水了一段時間(笑)

 
Blogger Josh Ko10/24/2007 3:35 pm 說:

Wow, what a surprise! 歡迎歡迎 :)。
有個板或 blog 可以讓我登門回訪嗎?:P

看來我實在該去 TA hour 聽一下,不應偷懶 XD。

 
Anonymous hcsoso10/25/2007 6:50 pm 說:

哎呀沒有,
顯之腦袋寫不出什麼東西(笑)

不過我會常來逛的:]

那個pf阿...
將vertex set V分為:
L leaf set: 所有葉子
N neiborhood set: 所有葉子的鄰居
E else set: 其他

很sloppy的寫:
suppose 葉子沒有共同鄰居;
deg(G,L) = 1;
deg(G,N) >= 3 by 題目,
thus deg(G-L,N) >= 2 by 假設;
deg(G,E) = deg(G-L,E) >= 2 不然就會是葉子

但是我們知道G-L仍然是樹 by Lecture Notes,
所以我們得到一顆所有degree大於2的樹,矛盾:P

 
Blogger Josh Ko10/26/2007 3:31 am 說:

喔,果然有趣,而且看起來比較好描述的樣子 XD。

 

<< 回到主頁