设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投稿
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2022,11(1),288-301
PublishedOnlineJanuary2022inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2022.111036
p4ãþž“¯K
¸¸¸???
1∗
§§§>>>ùùù
1†
§§§uuu°°°
2
,ŸŸŸwwwAAA
1
1
#õ“‰ŒÆêƉÆÆ§#õ¿°7à
2
#õŒÆêƆXÚ‰ÆÆ§#õ¿°7à
ÂvFϵ2021c1224F¶¹^Fϵ2022c114F¶uÙFϵ2022c126F
Á‡
-G´n‡º:ëÏã"b»3ãG,˜:u? -姞“ÀJ˜‡™X»º:?1
o(˜,‡º:o§K3‡L§¥Ñò?uoG)§,»øòu™\o…
vX»:"•ge§»Úž“O/3ãGþ£Ä§†»ØUUYøò§‡L§(
å"©Ì‡?Øn•{a\+Z
n
3k(k≥2)_4f8p4ãþž“¯K"Äk•
Äp4ã3_4f8þž“¯ K§ùÜ©(½p4ã(¿…JÑ(Ž{Ú
TŽ{matlabŠó¶ÙgïÄp4ã3n_4f8þž“¯K,ùÜ©•(½p4
ã(§¿…•Ä:•¹Ç§>•¹Ç±9MVS¯K¶•ïÄp4ã3Œun_4f
8þž“¯K§ùÜ©±:IÒ^SxÑp4㧠U_4f8êrp4ã¿©•ü
a§¿•Äp4ã?¿˜‡º:X»ž§˜‡ž“U››»¿‡^‡"
'…c
ž“¯K§p4ã§_4f8§•¹Ç§>•¹Ç
The Firefighter Problem onCayleyGraph
JinjunHan
1∗
,HongBian
1†
,HaizhengYu
2
,LinaWei
1
1
SchoolofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang
∗1˜Šö"
†ÏÕŠö"
©ÙÚ^:¸?,>ù,u°,ŸwA.p4ãþž“¯K[J].A^êÆ?Ð,2022,11(1):288-301.
DOI:10.12677/aam.2022.111036
¸?
2
CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang
Received:Dec.24
th
,2021;accepted:Jan.14
th
,2022;published:Jan.26
th
,2022
Abstract
Let Gbe aconnectedgraphwithnvertices.Assume thata firebreaks outat avertex
vofG.Afirefighterchoosesasetofkverticesnotyetonfiretoprotect(oncea
vertexhasbeenchosenbythefirefighter,itisconsideredprotectedorsafefromany
furthermovesofthefire).Thefirefighterandthefirealternatelymoveonthegraph.
Theprocessendswhenthefirecannolongerspread.Afterthefirefighter’smove,
thefiremakesitsmovebyspreadingtoallverticeswhichareadjacenttothevertices
onfire,exceptforthosethatareprotected.Inthispaper,wediscussthefirefighter
problemsintheCayleygraphsofadditivegroupofintegersmodulonwiththek-
element(k≥2)inverseclosedsubset.Firstlyweconsiderthefirefighterproblemson
the2-elementinverseclosedsubsetofCayleygraph,whichdeterminesthestructure
ofCayleygraphandputsforwardthestructurealgorithmandthematlablanguageof
thealgorithm.Secondly,westudythefirefighterproblemsonthe3-elementinverse
closedsubsetofCayleygraph, whichalsodeterminesthestructureofCayleygraphand
considerssurvivingrate,edgesurvivingrateandMVSproblem.Finally,wediscuss
the firefighter problemsonthek-elements(k≥4)inverse closedsubsetofCayley graph,
inwhichwedrawtheCayleygraphinorderofpoints,anddividetheCayleygraph
intotwocategoriesaccordingtotheorderoftheinverseclosedsubset.Moreover,
whileanyvertexofCayleygraphisonfire,weconsiderthesufficientandnecessary
conditionsthatafirefightercancontrolthefire.
Keywords
FirefighterProblem,CayleyGraph,InverseClosedSubset,SurvivingRate,
EdgeSurvivingRate
Copyright
c
2022byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
DOI:10.12677/aam.2022.111036289A^êÆ?Ð
¸?
1.Úó
\<ŒManitobaÞ•1253|ÜêƆOŽŒ¬þ,ͶOŽÅnØÆ[HartnellJÑ
ž“¯K(FirefighterProblem)[1].•ïÄã(†ã“»Uåƒm'X,Cai,Wang[2]
JÑã•¹ÇVg.
½Â1[2]G´˜‡kn‡º:ëÏã,v∈V(G).»3v?-åž,k‡ž“•õU
oº:ê¡•º:vk-•¹ê,P•sn
k
(v);»‘Å/3ãG˜‡º:?-åž,k‡ž
“•õUoº:ê²þŠ¡•ãG•¹Ç,P•ρ
k
(G),=
ρ
k
(G) =
P
v ∈V(G)
sn
k
(v)
n
2
.
F.StephenÚM.Gary3[3]¥JMVSVg.
½Â5[3]G´˜‡ã,v´ãG¥?¿˜‡º:,v‰•X»:,^d‡ž“ÏL¤
k•ª››v¤UoãG¥Ø-•Œº:êP•MVS(G,v;d).
‘‘…3©z[4]¥y²,éu?¿êk≥1,A¤kãxk−•¹ÇÑ´
ªu0.Ïd,Ïék−•¹Çî‚Œu0ãa´ék¿Â.lég,/ke¡¯K:=
ãak−•¹ÇŒu,‡~ê?éù˜¯K,‘…½Âe¡üa-‡ã.
½Â3[4]XJ•3~êc,¦ρ
k
(G) ≥c>0,KãG¡•k−Ð.
½Â4[4]XJlim
n→∞
ρ
k
(G) = 1,KãG¡•k−`.
2012c,‘…q3©z[5]¥JÑ>•¹ÇVg.
½Â2[5]G´˜‡kn‡º:m^>ëÏã,uv∈E(G).»3>uv ü‡à
:-åž,ž“æ1˜Úok
1
‡:,¡zÚok
2
‡:üѤUÍe•Œº:
êP•sn(G,uv;(k
1
,k
2
));»‘Å/3ãG˜^>ü‡à:-åž,ž“æ1˜Ú
ok
1
‡:,¡zÚok
2
‡:üÑ•õUoº:ê²þŠ¡•ãG>•¹Ç,P
•ρ(G,e;(k
1
,k
2
)),=
ρ(G,e;(k
1
,k
2
)) =
P
uv ∈E(G)
sn(G,uv;(k
1
,k
2
))
nm
.
ž“¯K3k•ãÚÕãþƒUÐmïÄ,Õã̇•Ä‚fã.p4ã´±‰½+
¥ƒ‰•ãº:,|^“ê¥+f8E˜«ã.XJ+´Ã•+,KéAp4ã•´Ã
•.
½Â6Γ´˜‡+,S´+Γ¥ƒ¤8Ü¿…+Γ¥ü Ø3S¥,±+Γ¥¤
kƒŠ•º:8,÷ve^‡ã¡•p4ã,P•CG(Γ,S):
1)XJ∀x,y∈Γ,kyx
−1
∈S,Kx†yü:ƒmÏLlÞ•yl—•x˜^lë;
2)XJ∀x,y∈Γ,kyx
−1
∈S…xy
−1
∈S,Kx†yü:ƒmÏL˜^>ë.
½Â7G´˜‡+,S´+G¥ƒ¤8Ü¿…+G¥ü Ø3S¥, XJ∀a∈S,
DOI:10.12677/aam.2022.111036290A^êÆ?Ð
¸?
ka
−1
∈S,K¡S•_4.
©lp4ãÑu,?Ø_4f8þp4ãž“¯K.
2.̇(J
2.1.p4ã3_4f8þž“¯K
•xÑp4ã,)ûp4ã3_4f8þž“¯K,·‚kJÑe¡½n.
½n1S={¯a,
¯
b}(a<b…¯a
−1
=
¯
b) ´Z
n
þ_4f8,C
c
d
L«1c‡d•,
n= l∗m(l≤m),ŠâØÓaéAp4ãCG(Z
n
,S)Xe;
1)a= lž,CG(Z
n
,S)´
S
l
k=1
C
k
m
,…∀C
k
i
m
∩C
k
j
m
= (k
i
6= k
j
,k
i
,k
j
= 1,2,···l).
2)a= mž,CG(Z
n
,S)´
S
m
k=1
C
k
l
,…∀C
k
i
l
∩C
k
j
l
= (k
i
6= k
j
,k
i
,k
j
= 1,2,···m).
3)e•3Maxl,¦a= λMaxl(λ∈Z
+
),KCG(Z
n
,S)´
S
l
k=1
C
k
m
,…∀C
k
i
m
∩C
k
j
m
=(k
i
6=
k
j
,k
i
,k
j
= 1,2,···l).
4)e•3Maxm,¦a= λMaxm(λ∈Z
+
),KCG(Z
n
,S)´
S
m
k=1
C
k
l
,…∀C
k
i
l
∩C
k
j
l
= (k
i
6= k
j
,k
i
,k
j
= 1,2,···m).
5)e•3MaxlÚMaxm,¦a= λ
1
Maxl= λ
2
Maxm(λ
1
,λ
2
∈Z
+
),KCG(Z
n
,S)´
S
m
k=1
C
k
l
,
…∀C
k
i
l
∩C
k
j
l
= (k
i
6= k
j
,k
i
,k
j
= 1,2,···m).
6)eaØ÷v±þÊ«œ¹,@oaéAp4ãCG(Z
n
,S)´C
n
.
lþ¡½nŒ±w_4f8S3Z
n
þp4ã´˜‡n•,½ö´˜ƒÓ•
¿…•ŒuØ¿.eZ
n
½,n•/¤p4㆘ƒÓ•¿…•Œu
Ø¿/¤p4ã,éu˜‡»u)up4ã?¿˜‡º:,^˜‡ž“o
(JÑ´ƒÓ,þž“¯K3[3]p®?Ø.•yþã½n,·‚‰ÑXeŽ
{,?‰8S={¯a,
¯
b}(a<b…¯a
−1
=
¯
b),½Z
n
¥ƒ‡ên,TŽ{ÑU¦ÑéA
8S= {¯a,
¯
b}(a<b…¯a
−1
=
¯
b)ep4ã.
CG(Z
n
,S)´Z
n
3_4f8S= {¯a,
¯
b}(a<b…¯a
−1
=
¯
b)þp4ã,
C
CG(Z
n
,S)
´p4ãëÏ©|:ê,C(CG(Z
n
,S))´p4ãëÏ©|ê.
Ñ\n,S{a,b}(en•ÛêKa≤b
n
2
c,en•óêKa≤
n
2
−1)
ÑÑCG(Z
n
,S),C
CG(Z
n
,S)
,C(CG(Z
n
,S))
dia<n(½MaxiÚS0,ia(i∈Z
+
,i<Maxi)
XJMaxia= b,ÑÑS0,ia,b
P0 = 1(1)
ia= i+1
b= Maxi+1
XJ1∗(Maxi+1) = n
DOI:10.12677/aam.2022.111036291A^êÆ?Ð
¸?
ÑÑCG(Z
n
,S) = {0,ia,b};C
CG(Z
n
,S)
= Maxi+1;C(CG(Z
n
,S)) = 1
ÄKˆ£(1),†•3m(m∈Z
+
),¦m∗(Maxi+1) = n
ÑÑCG(Z
n
,S) = {0,ia,b},{1,ia+1,b+1}···{m−1,ia+m−1,b+m−1};
C
CG(Z
n
,S)
= Maxi+1;C(CG(Z
n
,S)) = m
ÄKdMaxia−b+j
1
a<n,(½Maxj
1
(j
1
∈N,j
1
<Maxj
1
,i≤Maxi)
ÚS0,ia,Maxia−b+j
1
a(2)
XJMaxia−b+Maxj
1
a= b,ÑÑS0,ia,Maxia−b+j
1
a,b
P0 = 1(3)
ia= i+1
Maxia−b+j
1
a= Maxi+j
1
+1
b= Maxi+Maxj
1
+1+1
XJ1∗(Maxi+Maxj
1
+1+1) = n
ÑÑC
CG(Z
n
,S)
= {0,ia,Maxia−b+j
1
a,b};
C
CG(Z
n
,S)
= Maxi+Maxj
1
+1+1;C(CG(Z
n
,S)) = 1
ÄKˆ£(3),†•3m(m∈Z
+
),¦m∗(Maxi+Maxj
1
+1+1) = n
ÑÑCG(Z
n
,S) = {0,ia,Maxia−b+j
1
a,b},{1,ia+1,Maxia−b+
j
1
a+1,b+1}···{m−1,ia+m−1,Maxia−b+j
1
a+m−1,b+m−1};
C
CG(Z
n
,S)
= Maxi+Maxj
1
+1+1;C(CG(Z
n
,S)) = m
ÄKˆ£(2),†•3Maxj
p
¦
Maxia−b+Maxj
1
a−b+Maxj
2
a−b+···+Maxj
p
a= b(j
p
∈N,j
p
<
Maxj
p
)
ÑÑS0,ia,Maxia−b+j
1
a,···,Maxia−b+Maxj
1
a−b+···+j
p
a,b
P0 = 1(4)
ia= i+1
Maxia−b+j
1
a= Maxi+j
1
+1
Maxia−b+Maxj
1
a−b+···+j
p
a= Maxi+Maxj
1
+···+j
p
b= Maxi+Maxj
1
+···+Maxj
p
+p+1
XJ1∗(Maxi+Maxj
1
+···+Maxj
p
+p+1) = n
ÑÑC
CG(Z
n
,S)
= {0,ia,Maxia−b+j
1
a,···,Maxia−b+Maxj
1
a−
b+···+j
p
a,b};C
CG(Z
n
,S)
= Maxi+Maxj
1
+···+Maxj
p
+p+1;
DOI:10.12677/aam.2022.111036292A^êÆ?Ð
¸?
C(CG(Z
n
,S)) = 1
ÄKˆ£(4),†•3m(m∈Z
+
),¦m∗(Maxi+Maxj
1
+···+Maxj
p
+p+1) = n
ÑÑCG(Z
n
,S) = {0,ia,Maxia−b+j
1
a,···,Maxia−b+Maxj
1
a−
b+···+j
p
a,b},{1,ia+1,Maxia−b+j
1
a+1,···,Maxia−b+Maxj
1
a
−b+···+j
p
a+1,b+1}···{m−1,ia+m−1,Maxia−b+j
1
a+m−1,···,
Maxia−b+Maxj
1
a−b+···+j
p
a+m−1,b+m−1};
C
CG(Z
n
,S)
= Maxi+Maxj
1
+Maxj
2
+···+Maxj
p
+p+1;
C(CG(Z
n
,S)) = m.
3ù‡Ž{Ä:þ,·‚¢yTŽ{matlabŠó.
CZnXS´Z
n
3_4f8S= {¯a,
¯
b}(a<b…¯a
−1
=
¯
b)þp4ã,CcznXS´p4ãë
Ï©|:ê,CCZnXS´p4ãëÏ©|ê,2L«IÑ\nÚa.
Ñ\n,a,b(en•ÛêKa≤b
n
2
c,en•óêKa≤
n
2
−1)
ÑÑCZnXS,CcznXS,CCZnXS
CZnXS=0;CcznXS=0;CCZnXS=0;
n=2;a=2;b=n-a;c=mod(b,a);
ifc==0;
Max(1)=fix((n-0.001)/a)
end
i=0;
while(c=0)
i=i+1;
Max(i+1)=fix((b+c-0.001)/a);
Max(1)=fix((n-0.001)/a);
c=mod(b+c,a);end
i;%(½I‡^MaxjA.
Max;%Maxi,Maxj.
d=0;%1*(d).
forj=1:1:i+1
d=d+Max(j)+1;
end%OŽ1*(d)uõ.
d;j=1;
while(j*d=n)
j=j+1;
DOI:10.12677/aam.2022.111036293A^êÆ?Ð
¸?
end
j;dj=[0];%(½õ*(d)=n.
fory=1:1:Max(1)
dj=[dj,y*a];
end
b=b+c;
forx=1:1:i
abc=0;%abc•?¿·¶¥mCþ.
forz=1:1:x
abc=abc+Max(z)*a-b;
end
fory=0:1:Max(x+1)
dj=[dj,y*a+abc];
end
end
dj=[dj];der=dj;%der•?¿·¶¥mCþ.
forp=2:1:j
dj=[dj,der+(p-1)];
end
CZnXS=dj,CcznXS=d,CCZnXS=j.
2.2.p4ã3n_4f8þž“¯K
½n2 CG(Z
n
,S)´Z
n
3n_4f8S={¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þp4
ã,d´n,a,b,co‡ê•ŒúÏê.
(1)3n8{
a
d
,
b
d
,
c
d
}¥,e
a
d
,
c
d
´Ûê…|
a
d
−
b
d
|6=1,|
b
d
−
c
d
|6=1,KéACG(Z
n
,S)Ux
•d‡ã1Ø¿.
(2)3n8{
a
d
,
b
d
,
c
d
}¥,e
a
d
,
c
d
´óê…|
a
d
−
b
d
|6=1,|
b
d
−
c
d
|6=1,KéACG(Z
n
,S)Ux
•d‡ã2Ø¿.
(3)3n8{
a
d
,
b
d
,
c
d
}¥,e|
a
d
−
b
d
|= 1,|
b
d
−
c
d
|= 1,KéACG(Z
n
,S)Ux•d‡ã3Ø
¿.
a'_4f8þp4ã(Ž{,·‚N´n_4f8þp4ã(Ž{.ã
1Úã23n_4f8þ(Ž{aqu_4f8,ã33n_4f8þ(Ž{I
‡r_4f8Ž{¥a†•p4ã:ênÚa,b,cùo‡ê•ŒúÏê,ùp·‚Ì
DOI:10.12677/aam.2022.111036294A^êÆ?Ð
¸?
‡•Än_4f8S={¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þž“¯K.Ï•ã1,ã2,
ã3´éAn_4f8Sþp4ã,lÃI½Âùn«ã.e¡·‚xÑ14‡:ùn«
ã,ã1,ã2,ã3,éAS8©O´{
¯
1,
¯
7,
¯
13},{
¯
2,
¯
7,
¯
12},{
¯
6,
¯
7,
¯
8},••Bxã,·‚Pãº:
¯
i
•i(i∈N,i<n).
·K1[6]G´˜‡rKã,e˜‡»3ãG¥-,Kr−1‡ž“Œ±3ü‡žmü
S››ù‡»,-º:•ê8•2.
Figure1.CayleyGraphCG(Z
14
,{
¯
1,
¯
7,
¯
13})
ã1.p4ãCG(Z
14
,{
¯
1,
¯
7,
¯
13})
Figure2.CayleyGraphCG(Z
14
,{
¯
2,
¯
7,
¯
12})
ã2.p4ãCG(Z
14
,{
¯
2,
¯
7,
¯
12})
·‚Œ±wn_4f8S={¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þp4ã´nKã,
d·K1,·‚Œ±ј‡»3n_4f8Sþp4ã¥-,2‡ž“Œ±3ü‡žmü
S››ù‡»,-º:•ê8•2,e¡·‚•Ä˜‡»3n_4f8Sþp4ã¥-
,1‡ž“››œ¹.
½n3CG(Z
n
,S)´Z
n
3n_4f8S={¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þp4
ã,én>6,kMVS(CG(Z
n
,S),v;1) ≥n−6.
DOI:10.12677/aam.2022.111036295A^êÆ?Ð
¸?
Figure3.CayleyGraphCG(Z
14
,{
¯
6,
¯
7,
¯
8}
ã3.p4ãCG(Z
14
,{
¯
6,
¯
7,
¯
8}
y²:d´n, a, b,co‡ê•ŒúÏê, ed= 1, n= 8ž, kMVS(CG(Z
8
,S),v;1) =
3 >8−6 = 2,n>8ž,n= 14†nÕŒJ˜,éã1,ã2,ã3,Œ±ïáaqþã¥
o¡“»p¦»Ã{øò™X»Ù{º:,Ï•ã1,ã2,ã3,äkD45,Ïd••Ä˜‡
:X»œ¹.b½ã1,þ0:X»,¤k››»•{„äGãã4.ed6=1,én>6,w,˜
‡»•Uu)3CG(Z
n
,S),‡ëÏ©|þ,XJëÏ©|:êu6,(Øw,¤á.XJŒ
u6,?Ø•{Ód= 1,nþén>6,MVS(CG(Z
n
,S),v;1) ≥n−6.
Figure4.Atreechartthatcontrolsafireat0
ã4.››0:X»äGã
½n4CG(Z
n
,S)´Z
n
3n_4f8S= {¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þp4
ã,KCG(Z
n
,S)´1−`.
y²:d½n3 Œ•,
n(n−6)
n
2
≤ρ(CG(Z
n
,S))≤1,lim
n→∞
n(n−6)
n
2
=lim
n→∞
1−
6
n
=1,¤
±lim
n→∞
ρ(CG(Z
n
,S)) = 1.
½n5CG(Z
n
,S)´Z
n
3n_4f8S= {¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þp4
ã,KCG(Z
n
,S)´1−Ð.
DOI:10.12677/aam.2022.111036296A^êÆ?Ð
¸?
y²:d½n4,Ï•ρ(CG(Z
n
,S)) ≥
n(n−6)
n
2
= 1−
6
n
,n>6,‡¦•3~êc¦
ρ(CG(Z
n
,S)) ≥c>0,•In= 8,lc=
1
4
.
½n6CG(Z
n
,S)´Z
n
3n_4f8S={¯a,
¯
b,¯c}(¯a
−1
=¯c,
¯
b
−1
=
¯
b,a<b<c)þp4
ã,én>8kρ(CG(Z
n
,S),e;(1,1)) ≥1−
8
n
.
y²:aqu½n3 y²Œ±ïá››˜^>X»z‡žmü ^˜‡ž“›
›»¤k•{äGã,Œ±Ñp4ã?¿˜^>X»,•õŒ±-8‡:,¤
±ρ(CG(Z
n
,S),e;(1,1)) =
P
uv∈E(G)
sn(CG(Z
n
,S),uv;1)
nm
≥
3
2
n(n−8)
3
2
nn
= 1−
8
n
.
2.3.p4ã3Œun_4f8þž“¯K
3Œun_4f8þ,·‚réAp4ãU_4f8ê©•ÛêÚóêü«,é
Ap4ãx{U:IÒ^S•x•˜«,~Xã5,k20‡:,éAS8´{(
¯
1,
¯
19),(
¯
2,
¯
18)};ã
6,k40‡:,éAS8´{(
¯
1,
¯
39),(
¯
2,
¯
38),
¯
20},Ó•xã•B,·‚Pãº:
¯
i•i(i∈N,i<
n),,•Qãe¡½n,½Â“»pþÝ´¤“»pž“<ê.
Figure5.CayleyGraphCG(Z
20
,{(
¯
1,
¯
19),(
¯
2,
¯
18)})
ã5.p4ãCG(Z
20
,{(
¯
1,
¯
19),(
¯
2,
¯
18)})
½n7CG(Z
n
,S)´Z
n
3Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
)}(¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þp4ã,XJp4ã?¿˜‡º:X»,@o ˜‡ž“I‡ïá
ü¡þÝ•Max{a
1
,a
2
,···,a
i
}“»p5››»Ø¬øòÙ{™X»º:.
y²:Ï•Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
)}(¯a
j
−1
=
¯
b
j
,j=1,2,···,i)þ
p4ã,ÑŒ±x•ã5,/ª,Šâp4ãD45,·‚••Ä˜‡º:X»œ¹,b0
X»,dã5,»•Ul0ü>øò,ab´p4ã˜^>,d(a,b)=|a−b|´:a:bål,
Ï•p4ã¥?¿ü:a,båluuMaxd(a,b)=Max{a
1
,a
2
,···,a
i
},ÏdXJïá˜
¡þÝ•Max{a
1
,a
2
,···,a
i
}“»pž,˜‡†“»pƒX»º:´aØÑù¡p,l0
pX»:¥m¤kX»:•aØÑù¡p,q»´l0ü>øò,l7Lïá,˜¡þ
Ý•Maxd(a,b) = Max{a
1
,a
2
,···,a
i
}“»pâv±››»Ø¬øòÙ{™X»º:.
½n8CG(Z
n
,S)´Z
n
3Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
),
¯
n
2
}(
¯
n
2
−1
=
¯
n
2
,¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þp4ã,XJp4ã?¿˜‡º:X»,@o˜‡ž“
I‡ïáo¡þÝ•Max{a
1
,a
2
,···,a
i
}“»p5››»Ø¬øòÙ{™X»º:.
y²:aqu½n7y²,Šâã6,‡y²½n8,•Iy‡ïáo¡“»p5››»Ø¬ø
òÙ{™X»º:.•,b0X»,Ï•0X»¬—0ü>Ú
n
2
ü>X»,Ïd·‚kï
DOI:10.12677/aam.2022.111036297A^êÆ?Ð
¸?
á0þ>(e>)ž“»p,?ïá
n
2
e>(þ>)“»p,,Šâ
n
2
e>(þ>)“»p5
û½0þ>(e>)•ª“»p,e5ïá0e>(þ>)ž“»p,ƒïá
n
2
þ>(e>)
“»p,•Šâ
n
2
þ>(e>)“»p5û½0e>(þ>)•ª“»p,Ïd‡ïáo¡“»p
5››»Ø¬øòÙ{™X»º:.
þã½n‰Ñ››»o(J,´´Äé?¿Œun_4f8Sþ?¿‡º:p4
ã3p4ã?¿˜‡º:X»žÑU^˜‡ž“5››»„´™•,e¡SNÒ•Äù
¯K.
Figure6.CayleyGraphCG(Z
40
,{(
¯
1,
¯
39),(
¯
2,
¯
38),
¯
20})
ã6.p4ãCG(Z
40
,{(
¯
1,
¯
39),(
¯
2,
¯
38),
¯
20})
½n9CG(Z
n
,S)´Z
n
3?¿Œun_4f8S ={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
)}
(¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þp4ã,ep4ã?¿˜‡º:X»,˜‡ž“U
››»ØDÙ{™X»º:…=Max{a
1
,a
2
,···,a
i
}≤
1+
√
3n−8
3
.
y²:⇒ep4ã?¿˜‡º:X», ˜‡ž“U››»ØDÙ{™X»º:,KŠ
â½n7,ù‡ž “‡ïáü¡þÝ•Max{a
1
,a
2
,···,a
i
}“»p,¤±Up4ãþX
»:ê\±ž“‰•“»p:ê´uup4ão:ên,,Ï•¤Œun_
4f8´?¿,Ïd·‚•ÄS87L´3½Max{a
1
,a
2
,···,a
i
}e¤¹ƒ•õS8,
ù?¿Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
)}(¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)
þp4ãÑUd˜‡ž“››»ØDÙ{™X»º:.e¡·‚•Äp4ãþ
DOI:10.12677/aam.2022.111036298A^êÆ?Ð
¸?
X»:‡ê,Úƒc˜Šâp4ãD45,·‚••Ä0:X»œ¹,t´žmü ,
m= Max{a
1
,a
2
,···,a
i
}, d´¤“»pž“‡ê, 3t= 1ž, 1‡:X», d= 1;t= 2ž,
2m+1‡:X», d= 2; t= 3ž, 4m+1‡:X», d= 3; ···;t= m−1ž, 2(m−2)m+1‡:X»,
d= m−1;t= mž, 2(m−2)m+1+m+1 ‡:X», d= m;t= m+1ž, 2(m−2)m+1+m+1+m
‡:X»,d=m+ 1;t=m+2ž,2(m−2)m+1 +m+1 + m+ m‡:X»,d=m+ 2;···
;t= 2m−1ž, 2(m−2)m+1+1+m
2
‡:X»,d= 2m−1;t= 2mž,2(m−2)m+1+1+m
2
+1
‡:X»,d=2m,ù·‚ïáü¡“»p,nþk2(m−2)m+ 1+1+ m
2
+1 +2m≤n,
=3m
2
−2m+3 ≤n,lm≤
1+
√
3n−8
3
,•=Max{a
1
,a
2
,···,a
i
}≤
1+
√
3n−8
3
.
⇐m=Max{a
1
,a
2
,···,a
i
},rMax{a
1
,a
2
,···,a
i
}≤
1+
√
3n−8
3
ü>²•n3m
2
−
2m+3≤n,‡y˜‡»u)3p4ã?˜‡º:,˜‡ž“U››»ØDÙ{™X»
º:,•y3½Max{a
1
,a
2
,···,a
i
}e¤¹ƒ•õS8éAp4ãþ˜‡ž“U›
›»ØDÙ{™X»º:,ùé?¿S8,˜‡ž“ÑU ››»ØDÙ{™X»º
:,•=y3½Max{a
1
,a
2
,···,a
i
}e¤¹ƒ•õS8þp4ãX»:ê\±ž“‰
•“»p:ê´uup4ão:ên,Šâþ>y²,3m
2
−2m+3 ≤n,l3Œ
un_4f8S= {(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
)}(¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þ,˜‡»u
)3p4ã?˜‡º:,˜‡ž“U››»ØDÙ{™X»º:.
½n10CG(Z
n
,S)´Z
n
3Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
),
¯
n
2
}(
¯
n
2
−1
=
¯
n
2
,¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þp4ã,ep4ã?¿˜‡º:X »,˜‡ž“U
››»ØDÙ{™X»º:…=Max{a
1
,a
2
,···,a
i
}≤
5+
√
12n−47
12
.
y²:⇒·‚÷^½n8Ú½n9y²¥VgÚÎÒ,e˜‡»u)3p4ã?˜‡º
:,˜‡ž“U››»ØDÙ{™X»º:,KŠâ½n8,ù‡ž“‡ïáo¡þÝ
•Max{a
1
,a
2
,···,a
i
}“»p,Šâ½n8y²,¢Sþ1¡ p››1˜¡p,1o¡p›
›1n¡p,•=1¡p0¥m-:'1˜¡p0¥m-:‡êõm,1o¡p

n
2
¥m-:'1n¡p
n
2
¥m-:‡êõm,Ïd•I¦Ñ1¡p0¥m-
:‡êÚ1o¡p
n
2
¥m-:‡ê,f
i
(i=1,2)´1i¡p0¥m¤k-:
‡ê,f
i
(i=3,4)´1i¡p
n
2
¥m¤k-:‡ê,@ot=1ž,f
2
=0,f
4
=0,d=1;t=2
ž,f
2
=0,f
4
=0,d=2;t=3ž,f
2
=m,f
4
=m,d=3;t=4ž,f
2
=2m,f
4
=2m,d=4;
···;t=mž,f
2
=(m−2)m,f
4
=(m−2)m,d=m;···t=2m−1ž,f
2
=(2m−3)m),f
4
=
(2m−3)m,d=2m−1;t=2mž,f
2
=(2m−3)m+1),f
4
=(2m−2)m,d=2m;t=2m+ 1ž,
f
2
=(2m−3)m+1),f
4
=(2m−1)m,d=2m+1;···t=4m−1ž,f
2
=(2m−3)m+1),f
4
=
(4m−3)m,d=4m−1;t=4mž,f
2
=(2m−3)m+1),f
4
=(4m−3)m+1,d=4m;l
f
1
=f
2
−m=(2m−4)m+ 1,f
3
=f
4
−m=(4m−4)m+ 1,ù·‚ïáo¡“»p,
nþkf
1
+ f
2
+ f
3
+ f
4
+ 2 +4m≤n=12m
2
−10m+ 6≤n,•=m≤
5+
√
12n−47
12
,ÏdMax
{a
1
,a
2
,···,a
i
}≤
5+
√
12n−47
12
.
⇐aqu½n9 y²,Œ±p4ã?¿˜‡º:X»,Max{a
1
,a
2
,···,a
i
}≤
5+
√
12n−47
12
ž,˜‡ž“U››»ØDÙ{™X»º:.
m= Max{a
1
,a
2
,···,a
i
},l½n9Ú½n10Œ•,XJŒun_4f8Sþp4ã 
DOI:10.12677/aam.2022.111036299A^êÆ?Ð
¸?
?¿˜‡º:X»,@o˜‡ž“¿ØU››?¿Œun_4f8Sþp4ã¦»ØUø
òÙ{™X»º:,Ïdõ‡ž“››»´ék7‡.d½n9Ú½n10y²,·‚
•Œ±éõ‡ž“5››p4ãþ?¿˜‡:X»¿‡^‡,ÑnÚmƒm'X,,
Šâ½n9Ú½n10·‚UÑü^íØ.
íØ1CG(Z
n
,S)´Z
n
3Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
)}(¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þp4ã,ep4ãþ?¿˜:vX»,K¤1˜¡þÝ•m
“»pþ1˜‡º:´÷X:v^ž••m©Oê,±(v+ 1)(modn)‰•11‡ Oêº:
1((m−2)m+2)‡º:,¤1¡þÝ•m“»pþ1˜‡º:´÷X:v_ž••m
©Oê,±(v−1)(modn)‰•11‡Oêº:1(2m(m−1)+2)‡º:.
íØ2CG(Z
n
,S)´Z
n
3Œun_4f8S={(¯a
1
,
¯
b
1
),(¯a
2
,
¯
b
2
),···,(¯a
i
,
¯
b
i
),
¯
n
2
}(
¯
n
2
−1
=
¯
n
2
,¯a
j
−1
=
¯
b
j
,a
j
<b
j
,j=1,2,···,i)þp4ã,ep4ãþ?¿˜:vX»,K¤1˜
¡þÝ•m“»pþ1˜‡º:´÷X:v^ž••m©Oê,±(v+1)(modn)‰•
11 ‡Oêº:1((2m−4)m+ 2) ‡º:,¤1¡þÝ•m“»pþ1˜‡º:
´÷X:((v+
n
2
)modn)^ž••m©Oê,±(v+
n
2
+ 1)(modn) ‰•11 ‡Oêº:
1(2m(m−1) +2)‡º:,¤1n¡þÝ•m“»pþ1˜‡º:´÷X:v_ž••
m©Oê,±(v−1)(modn)‰•11‡Oêº:1((4m−4)m+2)‡º:,¤1o¡þÝ•m
“»pþ1˜‡º:´÷X:(v+
n
2
)(modn)_ ž••m©Oê,±(v+
n
2
−1)(modn)‰
•11‡Oêº:1((4m−3)m+2)‡º:.
Ä7‘8
I[g,‰ÆÄ7‘8(11761070,61662079);2021c#õ‘Æg£«g,Ä7éÜ‘
8(2021D01C078);2020c#õ“‰ŒÆ˜6;’!˜6‘§‘8]Ï.
ë•©z
[1]Hartnell,B. (1995) Firefighter!An Application of Domination. Presentationatthe25thMani-
tobaConferenceonCombinatorialMathematicsandComputing, University ofManitoba, Win-
nipeg,Canada.
[2]Cai,L.andWang,W.(2009)TheSurvivingRateofaGraphfortheFirefighterProblem.
SIAMJournalonDiscreteMathematics,23,1814-1826.
https://doi.org/10.1137/070700395
[3]Stephen,F.andGary,M.(2009)TheFirefighterProblem:ASurveyofResults,Directions
andQuestions.AustralasianJournalofCombinatorics,43,57-77.
[4]Wang,W.,Finbow,S.andWang,P.(2010)TheSurvivingRateofAllInfectedNetwork.
TheoreticalComputerScience,411,3651-3660.
https://doi.org/10.1016/j.tcs.2010.06.009
DOI:10.12677/aam.2022.111036300A^êÆ?Ð
¸?
[5]Kong,J.,Wang,W.andZhu,X.(2012)TheSurvivingRateofPlanarGraphs.Theoretical
ComputerScience,416,65-70.
https://doi.org/10.1016/j.tcs.2011.10.002
[6]Moeller,S.A.andWang,P.(2002)FireControlonGraphs.JournalofCombinatorialMathe-
maticsandCombinatorialComputing,41,19-34.
DOI:10.12677/aam.2022.111036301A^êÆ?Ð

版权所有：汉斯出版社 (Hans Publishers) Copyright © 2021 Hans Publishers Inc. All rights reserved.