圖的弱羅馬控制.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)軍團(tuán)的基本花費(fèi)又能防御羅馬帝國．用圖論的術(shù)語，設(shè)G=(V，E)是一個(gè)圖，f：V |→{0，1，2}是一個(gè)定義在圖G的頂點(diǎn)集V上的函數(shù)．對f來說

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