| 摘要: | 由於實際上的資源分享問題,我們將考慮一些在圖形上控制問題的變形.原本的圖形上的控制問題是找最少數目的點集合,使得圖上的任一點若不在這個點集合裡,那與它相連接的點裡,至少有一點是落在這個點集合裡.而我們考量的資源分配問題與控制問題相似,我們希望找最少數目的點集合,集合裡的每個點給予完整的資源(用3來衡量),這集合裡的點會供給與它最短距離為一的點部分資源(用2來衡量),供給與它最短距離為二的點少部分資源(用1來衡量),與它最短距離超過二的點就得不到它的資源,而圖上任一點都必須得到完整的資源供給(至少是3).我們已有一些初步的結果,包括證明了這樣的問題就算只考慮二部圖也是NP-complete,給出一些特定圖形上這樣的點集合數目最少的確切值.雖然現在有人提出在樹上,如果給定它的最大鄰居數,就會有個polynomial time的演算法.我們期望能找出更好的演算法,並且解決一些人們關心的特殊圖,如一些有k-規則和k-連通的圖.而透過圖形建構的工具, 如笛卡爾乘績等, 又如何去找到最佳的點集合.此外,我們也對類似的控制問題感興趣, 如「k-局部控制」 以及「總體防禦聯盟」等問題. 另外延續之前計劃的工作, 繼續對有關的圖形標號加以研究, 如「L(2,1)標號」以及「圖的整數和數」等問題. 研究期間：9608 ~ 9707 |
