圖的弱羅馬控制.pdf

1、基于Ian Stewart[11]發(fā)表的一篇論文(Defend the Roman Empirel，scientific Amer-ican，Dec．1999，pp．136-138)的意圖，M．A．Henning和S．T．Hedetniemi[1]提出了防御羅馬帝國的新策略使最高統(tǒng)治者既節(jié)約了給養(yǎng)軍團的基本花費又能防御羅馬帝國．用圖論的術語，設G=(V，E)是一個圖，f：V |→{0，1，2}是一個定義在圖G的頂點集V上的函數(shù)．對f來說

2、一個f(u)=0的頂點u被稱為未防御點，如果它不與任何帶有正權的頂點相鄰．函數(shù)f被稱為弱羅馬控制函數(shù)(簡稱WRDF)，如果對每一個f(u)=0的頂點u，都與一個f(υ)>0的頂點υ相鄰，并且函數(shù)f'：V|→{0，1，2}，使得，f'(u)=1，f'(υ)=f(υ)-1且．f'(w)=f(w)， w∈V-{u，υ}，沒有未防御點．函數(shù)，的權記為W(F)=∑<,υ∈v>f(u)．圖G的弱羅馬控制函數(shù)的最小權稱為弱羅馬控制數(shù)，記為，γ<,r>