An Algorithmic Proof
本週圖論作業最後一題，自認寫出一個還滿可愛的證明，貼在下面並附示意圖 XD。
題目：若樹 T 中任一與葉相鄰的點其度（degree）至少為 3，證明 T 中至少存在兩片葉有共同鄰居。
證明：任選一點為起點，在樹 T 中走出一條路徑（path）。一路上不會遇到先前出現過的點，否則會形成迴圈（loop）。因為點數有窮，終究會遇到一片葉子而停止。（遇到的點不是葉子的話，照定義其度數大於 1，而一定能繼續走下去。）路徑上倒數第二點的度數至少為 3，所以又可以從該點走出一條新的路徑。上述過程只有在「新路徑上的第一點為葉子」時才會終止，而且因為點數有窮而一定得終止。此時我們就找到有共同鄰居的兩片葉子。
--
很顯然是個 linear time 的演算法 XD。（其實就是 DFS 的特化版嘛 XD。）
Labels: Graph Theory
那天TA hour出現了一個極為神妙的proof ;]
噢對了，我是顯之你好:P
自從發現都有修圖論之後，潛水了一段時間(笑)
Wow, what a surprise! 歡迎歡迎 :)。
有個板或 blog 可以讓我登門回訪嗎？:P
看來我實在該去 TA hour 聽一下，不應偷懶 XD。
哎呀沒有，
顯之腦袋寫不出什麼東西(笑)
不過我會常來逛的:]
那個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
喔，果然有趣，而且看起來比較好描述的樣子 XD。
<< 回到主頁