Just make a note...
--
Klein's Spanner,
Lipton-Tarjan's Separator,
Miller's Cycle Separator,
Goodrich's Separator Decomposition Tree,
Schnyder's Realizer,
de Fraysseix-Pach-Pollack & Kant's Canonical Ordering,
Chiang-Lin-Lu's (My Teacher!!) Orderly Spanning Tree,
Yannakais' Four Page Embedding,
--
more to come!!
2009/09/07
帽子戲法
網路上看到兩個有趣的帽子問題:]
--
1. 有 10 個人排了一條隊，每人頭上都有一頂黑色或者白色帽子。每個人只可以看到排自己前面的人所穿帽子的顏色，而且他們均不能看到自己帽子的顏色。
現在有一個公証人，他會向每個人問一條問題：「你自己的帽子是甚麼顏色？」他會順序由排最後的人問到排最前的人。每個人只可以回答：「黑色」或「白色」，而每個人回答時，其他人都是可以聽到他的答案的。
這 10 個人可以事先商量怎樣回答，以確保答對的次數最多。問：他們可以確保答對多少次？怎樣可以達到？
2. 監獄裏有 n 個囚犯。有一日，皇上要跟這 n 個囚犯玩一個遊戲。皇上會選出 n 種顏色。獄長會在每一個囚犯頭上戴上一頂帽子，每頂帽子的顏色是這 n 種顏色之一。帽子的顏色並無其他限制，所以可能每個囚犯的帽子顏色都相同，亦有可能每個囚犯的帽子顏色均不同的。
每個囚犯都可以看到其他囚犯的帽子，唯獨是不可以看到自己的帽子。現在，囚犯們要同一時間向獄長交一張紙，上面寫上他們猜測自己帽子的顏色。當然，這樣子就是說囚犯們不會看到其他囚犯的猜測了。
皇上說如果有任何一個囚犯答對了，就釋放所有囚犯；否則，全部囚犯都要處死。這些囚犯可以事先商量怎樣回答，以確保他們一定能夠被釋放？問：他們怎樣達到目的？
--
第二題比較難，不過蠻有趣的!!
--
1. 有 10 個人排了一條隊，每人頭上都有一頂黑色或者白色帽子。每個人只可以看到排自己前面的人所穿帽子的顏色，而且他們均不能看到自己帽子的顏色。
現在有一個公証人，他會向每個人問一條問題：「你自己的帽子是甚麼顏色？」他會順序由排最後的人問到排最前的人。每個人只可以回答：「黑色」或「白色」，而每個人回答時，其他人都是可以聽到他的答案的。
這 10 個人可以事先商量怎樣回答，以確保答對的次數最多。問：他們可以確保答對多少次？怎樣可以達到？
2. 監獄裏有 n 個囚犯。有一日，皇上要跟這 n 個囚犯玩一個遊戲。皇上會選出 n 種顏色。獄長會在每一個囚犯頭上戴上一頂帽子，每頂帽子的顏色是這 n 種顏色之一。帽子的顏色並無其他限制，所以可能每個囚犯的帽子顏色都相同，亦有可能每個囚犯的帽子顏色均不同的。
每個囚犯都可以看到其他囚犯的帽子，唯獨是不可以看到自己的帽子。現在，囚犯們要同一時間向獄長交一張紙，上面寫上他們猜測自己帽子的顏色。當然，這樣子就是說囚犯們不會看到其他囚犯的猜測了。
皇上說如果有任何一個囚犯答對了，就釋放所有囚犯；否則，全部囚犯都要處死。這些囚犯可以事先商量怎樣回答，以確保他們一定能夠被釋放？問：他們怎樣達到目的？
--
第二題比較難，不過蠻有趣的!!
2009/09/05
Encoding unordered tree and SP-graph in optimal length
哈哈，結果跟老師一討論，好像很簡單的 separator 就可以做到 optimal 了，
不管 optimal 是多少XD (好像是在 1.58n 左右？)
SP-graph 就用他的 decomposition tree 的 separator 就可以了，
應該會一對一對應:]
果然簡單的問題早就被做光了XD
--
看到幾個有趣的 blog ，(像是 Lipton 的)
Wordpress 可以用 LaTeX 耶...
好吸引人喔，要不要搬過去呢？
不管 optimal 是多少XD (好像是在 1.58n 左右？)
SP-graph 就用他的 decomposition tree 的 separator 就可以了，
應該會一對一對應:]
果然簡單的問題早就被做光了XD
--
看到幾個有趣的 blog ，(像是 Lipton 的)
Wordpress 可以用 LaTeX 耶...
好吸引人喔，要不要搬過去呢？
2009/09/04
SP-graph succinct encoding
這是學姊最近在做的問題：
在想這個問題的過程，
發現 unlabeled unordered tree 好像還沒有低於 2n+o(n) 的 encoding!
說不定這是一個可以想的方向？
對於一個 n-node 的 SP-graph，
有沒有一個 encoding 的方法能做到 4n+o(n)?
在想這個問題的過程，
發現 unlabeled unordered tree 好像還沒有低於 2n+o(n) 的 encoding!
說不定這是一個可以想的方向？
2009/09/01
ISAAC 2009
ISAAC 2009 Accepted Papers
實驗室上了兩篇！
Tai-Hsin Hsu and Hsueh-I Lu, An Optimal Labeling for Node Connectivity
Tsung-Hao Liu and Hsueh-I Lu, Minimum Cycle Bases of Weighted Outerplanar Graphs
恭喜~~
實驗室上了兩篇！
Tai-Hsin Hsu and Hsueh-I Lu, An Optimal Labeling for Node Connectivity
Tsung-Hao Liu and Hsueh-I Lu, Minimum Cycle Bases of Weighted Outerplanar Graphs
恭喜~~
訂閱：
文章 (Atom)