hypercube與star networks的相關性質

這幾天收到徐力行老師寄給我的論文，我覺得這篇論文正是我需要的，裡面有好幾個結果可能在我的證明上需要用到，原本我還在想可能需要自己證明，動手做了幾個 case，覺得有點難，想不到徐老師已經證明出來了，真是太好了，有機會真的該好好學習一下其中的證明技巧。

司布林 / Xuite日誌 / 回應(0) / 引用(0) / 好文轉寄

2007-10-11 15:00Vertex Fault Tolerance for Multiple Spanning Paths in Hypercube

個人研究

這是我們今年投到組合數學研討會的論文，其中證明 Q_n 的 spanning disjoint paths 的點容錯。令 F_b 與 F_w 代表 Q_n 裡面黑色壞點與白色壞點的集合，令 K_b 與 K_w 代表 Q_n 裡面一些好的端點的集合，我們證明 Q_n - F_b - F_w 之後，K_b 與 K_w 裡面的點任意配對、每一對點都可以找到一條 spanning disjoint paths，只是必須符合幾個條件：|F_b| + |F_w| + |K_b| + |K_w| <= n, 4|F_b| + 2|K_b| = 4|F_w| + 2|K_w| <= n+1。這個結果就可以推到若 |F_b| = |F_w| <= (n-1)/4 的話，Q_n - F_b - F_w 是 Hamiltonian laceable。這個數字應該會比前一篇論文的結果大一倍左右。雖然這裡同樣用數學歸納法證明，但是複雜很多，很難寫得清楚，這是最麻煩的地方，不過還是應該努力寫清楚投稿到 Journal 才對。加油！

恩典與憐憫 / Xuite日誌 / 回應(1) / 引用(0) / 好文轉寄

2007-10-11 14:38這學期整理的連結網路論文

未分類

這學期的連結網路課程中也需要報告論文，前陣子我找了一些相關的連結網路的論文給同學選擇，雖然我沒有將這些論文做分類，但我想應該還是值得參考，所以將這些論文先放上來給大家參考。

2006-05-11 08:30網路上的發表應該有證明非抄襲的功用

雜談

上個月底我學長找到我這個 blog來，討論了一點點問題，後來學長警覺到網路是公開的地方，在這裡討論正在研究的問題比較危險，因為可能被一些作類似問題的人看到，文章可能被別人搶去，因此應該要用帳號、限定範圍的討論比較安全。

2006-05-11 08:20Qn 中給兩對點能切得開嗎？

問題

昨天一位同學提到一個與證明相關的問題，與 hypercube的對稱性有關，我一直相不出再怎麼證明，我對 hypercube的對稱性實在了解太少了。我將問題重新定義為：在 Q_n中任給兩個黑點 s_1, s₂與兩個白點 t₁, t₂，將 Q_n適當地切割成四個 Q_n-2，能否保證一定存在一種切法使得 s₁, t₁ 這兩個點與 s₂, t₂ 一定不在同一個 Q_n-2 裡面？

恩典與憐憫 / Xuite日誌 / 回應(3) / 引用(0) / 好文轉寄

2006-05-11 08:09Star 圖形上相鄰點容錯性質

關於 star

第23屆組合數學研討會中我們還投了另一篇論文 - Adjacent Vertices Fault Tolerance Hamiltonian Laceability of Star Graphs，討論 star 圖形中壞掉 f 對相鄰點之後，是否仍為 Hamiltonian laceable、hyper-Hamiltonian laceable 等性質，我們證明出 S_n 最多壞掉 n-3 對相鄰點後仍為 Hamiltonian graph，壞掉最多 n - 4 對相鄰點之後，仍為 Hamiltonian laceable 與 hyper-Hamiltonian laceable，這論文裡面當初學生寫的時候沒有討論邊容錯。

2006-05-11 07:53The Longest Ring Embedding in Faulty Hypercube

最長cycle與路徑

The Longest Ring Embedding in Faulty Hypercube，這也是投到 23 屆組合數學研討會的論文，討論 hypercube Qn 裡面任意壞掉 f 個點(至少要包含兩個黑點與兩個白點)，至少可以找到長度為 2ⁿ - 2f + 4 的 cycle，其中 f <= n - 1。

2006-05-11 07:45Adjacent Vertices Fault-Tolerance Fanability of Qn

fanable

Adjacent Vertices Fault-Tolerance Fanability of Hypercube,這是我們投到 23 屆組合數學研討會的一篇論文，證明在 Q_n 裡面壞掉 f 對相鄰的點、再壞到 e 條邊之後，仍為 (n-f-e)^*-fanable，其中 f + e <= n - 2, e >= 1，所以 k^*-fanable 的圖形 G 的條件是，G 為 bipartite graph，給任一個黑色起點 s 與一個白色終點 t₀、k 個黑色終點 t₁, t₂, ... , t_(k-1)，從 s 可以找出 k 條 spanning disjoint paths 到這 k 個終點。

2005-12-28 17:31star的超可蕾絲

關於 star

這是徐力行教授研究群所作的，證明 pancake P_n 中任兩點間可以找到 n - 1 條 spanning disjoint paths，而 star Sn 中任兩個不同顏色的點之間可以找到 n-1 條 spanning disjoint paths。The super connectivity of the pancake graphs and the super laceability of the star

2005-12-28 17:26star的漢米爾頓可蕾絲

關於 star

這是比較早一點的論文，徐力行教授他們作的，證明 star networks Sn 中壞掉 n-3 條邊後是 Hamiltonian laceable、strongly Hamiltonian laceable，壞 n-4 條邊是 hyper Hamiltonian laceable。Hyper hamiltonian laceability on edge fault star graph, Information Sciences, Volume 165, Issues 1-2, 3 September 2004, Pages 59-71