| 摘要: | 近來關於總體防衛的研究日趨熱絡,這是一個控制問題上的變形.原本的圖形上的控制問題是找最少數目的點集合,稱為控制集,使得圖上的任一點若不在這個控制集裡,那與它相連接的點裡,至少有一點是落在這個控制集裡.而總體防衛還要求在控制集裡的點,它的鄰居要有過半數也在這控制集裡. 由於實際上的資源分享問題,我們也考慮另一種在圖形上控制問題的變形.因為我們考量的資源分配問題與控制問題相似,我們希望找最少數目的點集合,集合裡的每個點給予完整的資源(用3 來衡量),這集合裡的點會供給與它最短距離為一的點部分資源(用2 來衡量),供給與它最短距離為二的點少部分資源(用1 來衡量),與它最短距離超過二的點就得不到它的資源,而圖上任一點都必須得到完整的資源供給(至少是3). 對於這兩類問題我們已有一些初步的結果,尤其是在雙環的網路圖形裡有一些明確的結果.我們希望可以更深入研究,解決所有類型的雙環網路,也將考慮其它較多人關心的網路圖形上有關這兩個問題的探討.此外,我們也想將這兩類問題延伸到方向圖上來研究,以及類似的控制問題, 如“k-局部控制＂等問題. ; 研究期間 9708 ~ 9807 |
