解答d我完全看不懂 囧 我想到是另外一種方法 但是這樣換來換去好像不對...
這題我用拆邊黏點法答案差很多耶 是我計算錯嗎? 拆邊黏點有沒有需要特別注意的地方?
矩陣的rank? 還有OS的round robin? 我問老師他說那是指循環賽的意思
不過那rank是代表什麼阿? 不太懂為何會跟圖論扯上關係
diameter 看不懂第二小題 沒頭緒
這種圖用拆邊黏點法也不好算 是不是一定要像解答
考慮對邊有無同色來著色比較好?
以上勞請大家解答囉~ 謝謝: )
訂閱：
張貼留言 (Atom)
6 則留言:
1. player 1可以是在full binary tree的左子樹或右子樹, 所以有兩種選擇, 選完以後player 2就只能擺在另一邊; 假設player 1位於左子樹, 那左邊總共有16個leaf的位置可以讓它選, 所以要再乘上16, player 2位於右子樹亦同理, 等他們都選完之後, 剩下的30個人就由剩下的30個位置做排列, 最後因為每個player和他在第一輪所遇到的對手互換位置視為相同, 所以要再除掉第一輪這16個pair彼此的兩兩互換, 所以總共是 (2*16*16*30!)/2^16
2. 你到倒數第二步算出來的都是對的, 只有整理到最後一步時有計算錯誤
3. 這裡的rank跟矩陣沒有關係, 比較是排名的意思
4. (a) 任兩點間的距離指的就是最短路徑, 而圖上任兩點距離中取最長的那一段, 那一段的距離長度就是diameter, 所以看問題中那個圖, 因為每個點到圖上任一點都只需走不超過三步就會到, 且存在有兩點間的距離是3步, 所以diameter就是3
(b) 在圖上隨便抓一點出來討論, 你可以把它想成是在建一棵BFS tree那樣, 因為在level 1最多會有δ個node, 在level 2最多會有δ(δ-1)個node, level 3同理node數最多也不會超過δ(δ-1)(δ-1)個, ...依此類推至和root距離最遠的點所在的level(也就是說這棵BFS tree最深只會找到level d), 該level上的node數最多也不會超過δ((δ-1)^(d-1))個, 所以1 + δ(δ-1) +...+ δ((δ-1)^(d-1))即為圖上點數的upperbound
5. 要用拆邊黏點也是可以, 只是有時候分case來討論會更有效率一點, 像這題這樣討論就還滿快的, 所以有時候在做題目之前稍為用經驗來判斷一下是否可以討論, 這樣寫起來可能會更有效率
不好意思
(b)想請問
關於diameter
不是定義兩點間的最短距離?
然後我們要選圖中最長那一個
這樣的話為何只需要考慮到root?
假設自root分開左右子樹各取一點
這樣就會到2d啦?
diameter指的不是取某兩點間的最長路徑, 而是說先把圖上所有pair的最短路徑找出來, 然後再從這些最短路徑中取出最長的那一段, 那一段的長度就是diameter, 也就是說, 圖上的任兩點之間都有長度不超過d的路徑可達, 所以你所擔心的那一件事情不會發生, 即使是左右子樹各取一點, 他們之間必存在著長度不超過d的path
diameter意思我懂了
而不用管其他點距離是因為
root是我們自己令的任一點V
所以只要root符合
我不用去管是不是這棵樹上的每一點
都需要符合最短path不超過d
是這意思囉?
我有點不太了解你所擔心的"其它點的距離"指的是甚麼, 其實 d 在這裡的作用主要就只是在bound那顆樹的高度而已, 也就是說不管你取哪一點當root, 樹的高度最多也不會超過 d, 原因就如同我先前寫的, 因為 d 為 diameter這是題目定義的, 所以圖上的任兩點之間的距離都不可能會超過 d
恩 那我大概了解了 謝謝助教:)
張貼留言