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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(11),4056-4064
PublishedOnlineNovemb er2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.1011431
²¡4·8
2
‚fãž“¯K
000ƒƒƒ•••
1∗
§§§>>>ùùù
1†
§§§uuu°°°
2
§§§ŸŸŸwwwAAA
1
1
#õ“‰ŒÆêƉÆÆ§#õ¿°7à
2
#õŒÆêƆXÚ‰ÆÆ§#õ¿°7à
ÂvFϵ2021c1023F¶¹^Fϵ2021c1113F¶uÙFϵ2021c1129F
Á‡
ž“¯K(FirefighterProblem)´˜‡lÑÄDÂ.§†¼œ››!‚óDÂ!Ü
“»¢S¯K—ƒƒ'§§•@´dͶOŽÅnØÆ[Hartnell31995c1253|Üê
ƆOŽŒ¬þÄgJÑ"-G=(V(G),E(G))´n(n≥2)‡º:ëÏã"b»3ãG
¥?¿˜‡º:v?-姞“KÀJ™X»º:o(˜,‡º:o§K3‡L
§¥Ñò?uoG)§,»øòv™\o…vX»:"•ge§»Úž“
O/3ãGþ£Ä,†»ØUUYøò§‡L§(姞“?Ö´¦•¼Í:ê•
õ"-sn(v)L«ãG¥º:vŠ•»:ž˜‡ž“¤Uo•õº:ê"ãG•
¹Çρ(G)½Â•
P
v∈V(G)
sn(v )
n
2
§=»‘Å/3ãG˜‡º:-垧˜‡ž“•õUo
º:ê²þŠ"©ÄkïÄk•²¡4·8
2
‚fã•¹Ç§©Û‚fã¥:•¹êCz
5Æ¿‰Ñk•4·8
2
‚fã•¹Ç(ƒŠ¶ly²éuÕ²¡4·8
2
‚fã§z‡£Ü
¦^˜‡ž“²Lk•goŒ±››»øò"
'…c
ž“¯K§•¹ê§•¹Ç§²¡4·8
2
‚fã
TheFirefighterProblemofPlane4·8
2
Grids
∗1˜Šö"
†ÏÕŠö"
©ÙÚ^:0ƒ•,>ù,u°,ŸwA.²¡4·8
2
‚fãž“¯K[J].A^êÆ?Ð,2021,10(11):
4056-4064.DOI:10.12677/aam.2021.1011431
0ƒ•
ZhiyaoXing
1∗
,HongBian
1†
,HaizhengYu
2
,LinaWei
1
1
SchoolofMathematicalSciences,XinjiangNormalUniversity,UrumqiXinjiang
2
CollegeofMathematicsandSystemSciences,XinjiangUniversity,UrumqiXinjiang
Received:Oct.23
rd
,2021;accepted:Nov.13
th
,2021;published:Nov.29
th
,2021
Abstract
Firefighter Problem canbeviewed asadiscretedynamicpropagationmodel,whichis
closelyrelatedtothepropagationofviruses,rumoursorepidemics.FirefighterProb-
lemwasintroducedbyHartnellatthe25thManitobaConferenceonCombinatorial
MathematicsandComputing.LetGbe aconnectedgraphwithn(n≥2)vertices.As-
sumethatafirebreaksoutatavertexvofG,afirefighter (ordefender)choosesaset
ofverticesnotyetonfiretoprotect;onceavertexhasbeen chosenby thefirefighter,
it isconsideredprotectedorsafe fromany further movesofthe fire.The process ends
when the firecanno longerspread.Letsn(v)denote the maximum number ofvertices
inGthatthefirefightercansavewhenafirebreaksoutatvertexv,whichcanbe
referredtoasthesurvivingnumberforv.Thesurvivingrateρ(G)ofgraphGisde-
finedtobetheaveragepercentageofvertices thatcanbesaved whenafirerandomly
breaksoutatonevertexofgraph,i.e.,
P
v∈V(G)
sn(v )
n
2
.Inthispaper,wefirstlystudythe
survivingrateoffinite4·8
2
grids,andpresenttheexactvalueofthesurvivingrate
offinite4·8
2
grids.Moreover,weprovethatwhenfirebreaksoutatanyvertexin
infinite4 ·8
2
grids,usingonefirefighterineachturncancontrolthespreadofafire
afteralimitedamountofprotection.
Keywords
FirefightersProblem,SurvivingNumber,SurvivingRate,Plane4·8
2
GridsGraph
Copyright
c
2021byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
DOI:10.12677/aam.2021.10114314057A^êÆ?Ð
0ƒ•
1.Úó
#)¡ö(COVID-19)Œ612•@•´y“šÆ¤þ¡•ˆ9)·¯K,§3
6Ï-.ˆ/<aèxÚ²L.§å•™k½Ø,®×„3IS!øò.–2020c4
3F,¥(¾~•1,116,643~,Ù¥•)59,158~k(Šâ-.¤L&E).Ž8c,Ñ
„vkéù«#;¾äNA†Ô.ž“¯K(FirefighterProblem)´˜‡lÑÄ
DÂ.,†¼œ››!‚óDÂ!Ü“»¢S¯K—ƒƒ',§•@´dͶOŽÅnØ
Æ[Hartnell31995c1253|ÜêƆOŽŒ¬þÄgJÑ[1].b3žmt=0ž•,
ãG= (V(G),E(G))¥?¿˜‡º:vŠ•»:,éuz˜‡ü žm(i,i+1],i≥0,˜‡ž“
o˜‡™-:(ù‡:˜o,K3‡L§¥Ñò?uoG),,»øòv
™\o…vkX»:.•ge,»Úž“O/3ãGþ£Ä,†»ØUUYøò,
‡L§(å.•,ãG¥º:kn«G,©O´Xº:!oº:ÚQvkX
•vkoº:,vkX:¡•¼Í:.du3‡L§¥,•kž“kZýüÑ,
»¿vkæüÑ,§•´øò§:,¤±ž“¯K•Œ±w¤´˜‡<|ÜiZ.D
Ú61¾.Ñ´b+Nƒm´ƒp·,,‡NƒmƒpéX¿…Œ±r;¾D‰*d.
,,•C61¾Æ[Áãò˜m&E••¹3¦‚.¥.Ïd,ž“¯K3,«¿ÂþŒ±
w¤vk£•#);¾D Â..¯¢þ,du3y¢)¹¥k¼¢´k•¿…¼¢
+n<•´k•,Ïd,z˜Ú•#Nk•‡vka/<«¼¢.@o˜‡ég,¯KÒ
´XÛ«¦•a/<êˆ•º
gHartnellJÑž“¯K,Nõû)VgÚ¯KƒUJÑ.2009c‘…<[2]Çk
Ú\ã•¹ÇVg,¿éä!Œ²¡ãÚMãAÏãaïÄü<“»¯K.-sn(v)
L«3ãG¥:vŠ•»:˜‡ž“3‡oL§(åŒ±o:•õº:ê,
¡•:v•¹ê.dd,ãG•¹êsn(G)½Â•»‘Å/3ãG¥?¿˜‡º:
už,˜‡ž“•õŒ±oº:ê,=sn(G)=
P
v ∈V(G)
sn(v).ãG•¹Ç½ÂXe:
ρ(G) =
sn(V(G))
n
2
,L«˜‡ž“•õŒ±o²þº:ê.
k´ê,k-ž“¯KÒ´‡¦ž“z˜Úok‡™\“o…vkX:,†
»Ø2øò‡L§(å(=e˜‡ž“ÀJ˜‡º:?1“o,Kz˜ÚI‡k‡ž“).
aq/,^sn
k
(v)L«ãG¥º:vŠ•»:ž^k‡ž“•õŒ±oº:ê.ãG
k-•¹êsn
k
(G)½Â •‘Å/ÀJG¥,‡:•»:,@ok‡ž“•õŒ±o
º:ê,=sn
k
(G)=
P
v ∈V(G)
sn
k
(v),ãGk-•¹½Â•:ρ
k
(G)=
sn
k
(V(G))
n
2
.w,,k-ž“¯
K´ž“¯Kí2.
3ØÓãaž“¯KƒUïÄ.31995cHartnell<3©z[1]Ò®²y²éuÜ
ãž“¯K´NP-¯K.NgÚRaff32008c[3]y²,XJŒ^ž“êþ3žmt¥´
±Ï5Cz,¿…z‡žm±Ï²þž“‡êŒu
3
2
,@oéu‘Õ‚fã¥,?¿k•
‡º:m©-»/ÑŒ±››.2010cFinbow<[4]&ÄXeAÏã•¹Ç,X:²¡
ã!Œ•'Œ²¡ã,عK
4
minorfªãÚd-òzã,¿y²Xe(J:
1)A¤kãk-•¹Ç?¿ªu0.
2)éuŒ•–´9²¡ãG,kρ(G) ≥
2
35
.
DOI:10.12677/aam.2021.10114314058A^êÆ?Ð
0ƒ•
3)éuعK
4
minorfªã,kρ
2
(G) ≥
1
16
.
4)éud-òzãG,kρ
2d−1
(G) ≥
2
5d
.
5)éu²¡ãG,kρ
5
(G) ≥
2
15
.
32017cAdjiashvili<[5]ïÄêž“¯KÚ]•“»››¯K,¿y²é
uäž“¯Kk˜‡PTASŽ{.
©Ì‡ïÄ²¡4·8
2
‚fãž“¯K.ÄkïÄk•²¡4·8
2
‚fã•¹Ç,©
Û‚fã¥:•¹êCz5Æ¿‰Ñk•4 ·8
2
‚fã•¹Ç(ƒŠ,ly²éuÕ
²¡4·8
2
‚fã,z‡£Ü¦^˜‡ž“²Lk•goŒ±››»øò.
2.̇(J
2.1.k•4·8
2
‚fã
2000c,ShrockÚWu3©z[6]‰Ñ²¡4 ·8
2
‚fG
t
(n,m))¤êê8Úì?~ê
OŽúª.!¥Äu²¡4 ·8
2
‚fã•Ä3k•œ¹e?¿˜‡:Š•å©»:¿…z‡
£Ü•^˜‡ž“oÙ¦:.G
t
(n,m)¥mL«•/ê,nL«z•/
‡ê,ŠâãEŒ±wÑz˜l>/‡ê•n+ 1.-lL«:ê,Œ±'X
ªl=3m+4.N´wÑùa‚fã´d˜l>/Êb|¤,㥕kݽönÝ:,¿…Ê
ba.†8‚fãaq,Êb•ªXã1¤«:
Figure1.ThegridgraphG
t
(4,1)
ã1.G
t
(4,1)‚fã
Ún2.1éuk•²¡4 ·8
2
‚f,'ÐoüÑÒ´ž“o:/¤˜‡•Œ
C.
y²Ï••Ä´k•‚fã,¤±ã´k>..Šâ• r“»p©•ÀÜ!ÜÜ!H
Ü!Ü.•ª8´^“»pÚ‚fã>.-Ü/¤˜‡•ŒC.
3t=0žb»u3ãG¥?¿˜‡:v;t= 1žž“ÀJv?˜:o¦ž
“3»C ˜;t=2ž»øò:vvk oÚvk-:.˜˜ž“3Ü·
˜þ•(ùž“é› ›»øò´k/.UYþãL§,†ž“o:|¤“
»p†‚fã>.-Ü3˜å/¤˜‡•ŒC,@o»òØ2øò.Xã2¥,:>êiL
«3žmt=0,1,2,···,9éù‡:¤?1öŠ.ã¥ùÚ:L«»øò:(Ù¥IÒ•0
ùÚ:•»:),7Ú:L«ž“o:.
Ï•²¡4 ·8
2
‚fãäké¡5,¤±ž“o:/¤•Œž,Œ±uy3½:
DOI:10.12677/aam.2021.10114314059A^êÆ?Ð
0ƒ•
êžk:äkƒÓ•¹ê¿…kaqoüÑ.~X,:v
i
2
,v
i+1
2
,···,v
i+j
2
Ñ3Ó˜
,¿…§‚•¹ê•g•sn(v
i
2
),sn(v
i+1
2
),···,sn(v
i+j
2
),@oŒ±ªsn(v
i
2
)=sn(v
i+1
2
)
=···=sn(v
i+j
2
).
Šâ²¡4·8
2
‚fãÊb•ªÚE,Œ±½Ân«ØÓ:8,¿…±ey²L§Ñ¦
^ù«:8©a.
V
2
1
={v∈V
2
|v˜‡Ý:Ú˜‡nÝ:,½öÑ´Ý:}.
V
3
1
={v∈V
3
|vÝ:ÚnÝ:}.
V
3
2
={v∈V
3
|vÑ´nÝ:},ùpV
2
L«3G
t
(n,m)¥Ýê•2:8,V
3
äkaq
½Â:8.
Äky²G
t
(n,3)•¹Ç¿…3G
t
(n,3)¥•[Qãù‡oL§.
½n2.2 éuG
t
(n,3),Kρ(G
t
(n,3)) =
324n
2
+784n+684
(18n+26)
2
.
y²-11 :ê•n,Kk14,7,10:ê•
n
2
+1,Ù{:êц11 ƒÓ,
V(G
t
(n,3)) = 18n+26(n≥3).
œ/1 e»:´V
1
2
¥:.
XJv
1
1
∈V
1
2
´»:.3ž•t=1ov
2
1
;t=2ov
1
3
,dž»ÒØ2øò.ddŒ±
sn(v
1
1
) = 18n+24.†v
1
1
kaqoüÑÚƒÓ•¹ê:k:v
1
2
,v
n
2
+1
2
,v
1
3
,v
n
2
+1
3
,v
1
5
,v
n
2
+1
5
,v
1
6
,
v
n
2
+1
6
,v
1
8
,v
n
2
+1
8
,v
1
9
,v
n
2
+1
9
,v
1
11
,v
n
2
+1
11
,v
1
12
,v
n
2
+1
12
;v
2
1
,···,v
n
1
;v
1
13
,···,v
n
13
.
œ/2 e»:´V
1
3
¥:.
XJv
2
2
∈V
1
3
´»:.3ž•t= 1ov
2
3
;t= 2ov
4
1
;t=3ov
1
2
,dž»Ø2øò.d
dŒ±sn(v
2
2
)=18n+22.†:v
2
2
kaqoüÑÚƒÓ•¹ê:k:v
3
2
,v
4
2
,···,v
n
2
2
;v
2
12
,
v
3
12
,···,v
n
2
12
;v
1
7
,v
n
7
.
œ/3 e»:´V
2
3
¥:.
fœ/3.1XJv
2
3
∈V
2
3
´»:.3ž•t=1ov
2
2
m©ïᘇÜÜ“»p;t=2
ov
4
4
¦·ò•ÜÜ“»p•Ý;t=3ov
2
6
m©ïᘇHÜY²••“»p;t=4
ov
1
6
¦·ò•HÜ“»p•Ý¿…†‚fãÀÜ>.-Ü;t= 5ov
1
1
m©ïᘇ
Ü“»p¿…†‚fãÀÜ>.-Ü.–dùØÓ•• “»pÚ‚f ã>.*dÑpƒ-
Ü•ª/¤•Œ¦»ÊŽøò,v
2
3
•¹êLˆªsn(v
2
3
) = 18n+18.†:v
2
3
kaqoüÑÚ
ƒÓ•¹ê:k:v
n
2
3
;v
2
4
,v
3
4
,···,v
n−1
4
;v
2
11
,v
n
2
11
;v
2
10
,v
3
10
,···,v
n−1
10
;v
2
5
,v
n
2
5
,v
2
6
,v
n
2
6
,v
2
7
,v
n−1
7
,v
2
8
,
v
n
2
8
,v
2
9
,v
n
2
9
.
fœ/3.2XJv
3
3
∈V
2
3
´»:.3ž•t=1ov
4
4
m©ïᘇÜÜ“»p;t=2
ov
6
4
m©ïᘇÀÜ“»p;t=3ov
3
6
¦·ò•ÜÜ“»p•Ý¿…†ÀÜ“»p-
Ü;t=4ov
2
2
¦·ò•ÜÜ“»p•Ý¿…†‚fãÜ>.-Ü;t= 5o:v
4
3
¦
·ò•ÀÜ“»p•Ý;t=6ov
8
1
¦ÀÜ“»p†‚fãÜ>.-Ü.•ù
“»p†‚fã>.*d-Ü¿…/¤•Œ,v
3
3
•¹êLˆªsn(v
3
3
) = 18n+16.†:v
3
3
ka
DOI:10.12677/aam.2021.10114314060A^êÆ?Ð
0ƒ•
qoüÑÚƒÓ•¹ê:k:v
4
3
,v
5
3
,···,v
n
2
−1
3
;v
3
11
,v
4
11
,···,v
n
2
−1
11
.
fœ/3.3XJv
3
5
∈V
2
3
´»:.3ž•t=1ov
3
6
m©ïᘇHÜ“»p;t=2
ov
6
4
m©ïᘇÀÜ“»p;t=3ov
2
5
m©ïᘇÜÜ“»p;t=4ov
2
4
¦·ò
•ÜÜ“»p•Ý;t= 5ov
6
1
¦·ò•ÀÜ“»p•Ý¿…†‚fãÜ>.-Ü;
t=6ov
1
1
¦ÜÜ“»p†‚fãÜ>.ƒ-Ü.•ù“»p† ‚fã>.*d-
Ü/¤˜‡•Œ¿…{Ž»øò,v
3
5
•¹êLˆªsn(v
3
5
) = 18n+14.†:v
3
5
kaqoüÑ
ÚƒÓ•¹ê:k:v
4
5
,v
5
5
,···,v
n
2
−1
5
;v
3
9
,v
4
9
,···,v
n
2
−1
9
;v
3
7
,v
n−2
7
.
fœ/3.4XJv
3
6
∈V
2
3
´»:.3ž•t=1ov
3
5
m©ïᘇÜ“»p;t=2
ov
3
7
m©ïᘇÜÜ“»p;t= 3ov
3
9
¦·ò•ÜÜ“»p•Ý;t= 4ov
4
5
m©ï
ᘇÀÜ“»p;t=5ov
8
7
¦·ò•ÀÜ“»p•Ý;t=6ov
8
10
?·ò•À
Ü“»p•Ý;t=7ov
4
12
m©ïᘇHÜ“»p¿…†ÜÜ“»p-Ü;t= 8ov
3
12
¦
·ò•HÜ“»p•Ý;t=9ov
3
10
¦·ò•ÜÜ“»p•Ý¿…†HÜ“»p
-Ü.•ù“»p†‚fã>.*d-Ü/¤˜‡•Œ¿…{Ž»øò.v
3
6
•¹êLˆ
ªsn(v
3
6
)=18n+11.†:v
3
6
kaqoüÑÚƒÓ•¹ê:k:v
4
6
,v
5
6
,···,v
n
2
−1
6
;v
4
7
,v
5
7
,···,
v
n−3
7
;v
3
8
,v
4
8
,···,v
n
2
−1
8
.
Figure2.Thegraphofsubcase3.4
ã2.fœ/3.4«¿ã
nÜþãínL§, Œ±•¹ê•sn(v) = 18n+24, sn(v) = 18n+22, sn(v) = 18n+18,
sn(v)=18n+ 16,sn(v)=18n+ 14,sn(v)=18n+ 11:éA‡êLˆª•g•4n+ 20,
2n+6,4n+14,2n−4,2n−2,4n−8.rù‡ê?1¦Ú,•Œ±G
t
(n,3)•¹Ç.O
ŽL§LˆªXe:
sn(G
t
(n,3)) = (4n+20)(18n+24)+(2n+6)(18n+22)
+(4n+14)(18n+18)+(2n−4)(18n+16)
+(2n−2)(18n+14)+(4n−8)(18n+11)
= 324n
2
+784n+684
DOI:10.12677/aam.2021.10114314061A^êÆ?Ð
0ƒ•
¤±,ρ(G
t
(n,3)) =
324n
2
+784n+684
(18n+26)
2
(n≥3).
éum=1!2,Œ±Šâþãm= 3œ¹?1aqíny²L§Xe(J.
½n2.3 éuG
t
(n,1),Kρ(G
t
(n,1)) =
100n
2
+228n+172
(10n+14)
2
.
y²3G
t
(n,1)‚fã¥:‡êV(G
t
(n,1))=10n+14.¿…Œ±•¹ê•sn(v)=
10n+ 12,sn(v)=10n+ 10,sn(v)=10n+ 6,sn(v)=10n+4:éA‡êÏ‘Lˆª•g
•4n+12,2n+2,2n+4,2n−4.•ãG
t
(n,1)•¹êXeOŽLˆª:
sn(G
t
(n,1)) = (4n+12)(10n+12)+(2n+2)(10n+10)
+(2n+4)(10n+6)+(2n−4)(10n+4)
= 100n
2
+228n+172
¤±,ρ(G
t
(n,1)) =
100n
2
+228n+172
(10n+14)
2
(n≥2).
½n2.4 éuG
t
(n,2),Kρ(G
t
(n,2)) =
196n
2
+468n+316
(14n+20)
2
.
y²3G
t
(n,2)‚fã:‡êV(G
t
(n,2)) = 14n+20.Œ±• ¹ê•sn(v) = 14n+18,
sn(v) = 14+16,sn(v) = 14n+12,sn(v) = 14n+10,sn(v) = 14n+8:éA‡êÏ‘Lˆª
•g•4n+16,2n+4,4n+8,2n−4,2n−4.•Œ±ãG
t
(n,2)•¹êXeOŽínL§:
sn(G
t
(n,2)) = (4n+16)(14n+18)+(2n+4)(14n+16)
+(4n+8)(14n+12)+(2n−4)(14n+10)
+(2n−4)(14n+8) = 196n
2
+468n+316
¤±,ρ(G
t
(n,2)) =
196n
2
+468n+316
(14n+20)
2
(n≥3).
m=4ž,Œ±G
t
(n,4)º:êV(G
t
(n,4))=22n+32,¿…㥤k:éA•¹
ê«aê†þãm= 3œ¹ƒÓ.ÏLo(Úí2,éu?¿k•mÚn,Œ±ãG
t
(n,m)
º:êÚm,nƒm'XLˆªV(G
t
(n,m)) = 4(m+1)(n+1)+2(m+n+2), ùpm,n∈N
+
.
¿…Œ±3‚fãG
t
(n,m)¥:(1)• ¹ê•sn(v)=(V(G
t
(n,m)) −2):ê4(n+m+ 2);
(2)•¹ê•sn(v)=(V(G
t
(n,m)) −4):ê2(m+n);(3)•¹ê•sn(v)=(V(G
t
(n,m)) −8)
:ê4n+6m−4;(4)•¹ê•sn(v) = (V(G
t
(n,m))−10):ê2n−4;(5)•¹ê•sn(v) =
(V(G
t
(n,m))−12):ê2(m+n)−8;(6)•¹ê•sn(v) = (V(G
t
(n,m))−15):3ã¥äk
Xe ˜A:ù: u˜‡Ý/«•¥,ù‡Ý/«•>.þ:Ú« •p¡:Ñ´ÎÜ
:,…ù‡Ý/«•>.þ:‚fã>.þÝê•2:ålÑ´5.ùpål´•ü :
ƒm•á´•Ý.
2.2.Õ²¡4·8
2
‚f
Õãž“¯K̇ïÄ3‰½ž“ê8cJe´ÄU3k•žmSò»› ›4,½
öž“XÛ“o¦•¼Íº:ê•õ.éuÕ²¡4·8
2
‚fã,'5-:´XJz‡
£Ü•¦^˜‡ž“@oéu?¿˜‡»:´ÄŒ±››»øò.ŠâÚn2.1ogŽ
UÄŒ±é˜‡'ÐoüѦž“/¤˜‡•Œ.e¡½n2.6y²ù‡ßŽ¿
…‰Ñ››»‡L§¦^£ÜêÚ-:‡êe..-v
j
i
L«²¡4·8
2
‚fã¥?¿˜
:,:v
j
i
‹I9Ù:IP•ªXã3¤«.
DOI:10.12677/aam.2021.10114314062A^êÆ?Ð
0ƒ•
Figure3.Thecoordinateofv
j
i
anditsneighbourhood
ã3.v
j
i
:‹I9Ù:«¿ã
½n2.5 éuÕ²¡4·8
2
‚fãXJz‡£Ü¦^˜‡ž“,@o319‡£Ü(åù‡
»ÒØ2øò,…-:‡ê••15.
y²3Õ²¡4·8
2
‚fã¥,•knÝ:•3ã¥.¦^oüÑXe:3žmt= 0,b
²¡4·8
2
‚fã¥?˜:v
j
i
•»:;t= 1˜˜ž“3v
j+1
i
;t= 2ž“˜3v
j−1
i−2
;t= 3ž
“˜3v
j−3
i
¿…·ò•“»p•Ý;t=4ž“˜3v
j+1
i+3
{Ž»øò;t=5˜˜ž“
3v
j−1
i+5
m©ïᘇÀÜ“»p;t= 6˜˜ž“3v
j−4
i+5
·ò•ÀÜ“»p•Ý;t= 7˜˜
ž“3v
j−6
i+3
¿…m©ï˜‡HÜ“»p;t= 8˜˜ž“3v
j−6
i
·ò•HÜ“»p•Ý;
t=9˜˜ž“3v
j−4
i−2
·ò•ÜÜ“»p•Ý¿…†HÜ“»pƒ-Ü.•ªù“»p*
dƒ-Ü/¤˜‡•Œ¦»Ø2DÂ.Xã2¤«,˜˜ž“3ù: ˜þŒ±:
•¹ê•sn(v) = V(G
t
(n,m))−15.
lÕ²¡4·8
2
‚fã(,Œ±wÑdul>/Êb•ª)˜•/,ù
•/þX»:3k•go£Ü¦£c¡®²-:C ˜,ÏdŒ±~
-:CX«•.¤±F"˜˜ž“Œ±¦ŒU£»:C ˜þ,?/¤˜‡
•Œ¦»Ø2øò.»ÊŽøòž,þã¦^oüѦ-«•••¹9‡l>/,
„Œ±wù‡-«• •¡˜ž“‡ê•9,¿…ù‡-«•o-:‡ê•
•15,Xã2¤«.
Ä7‘8
I[g,‰ÆÄ7‘8(11761070,61662079);2021c#õ‘Æg£«g,Ä7éÜ‘
8(2021D01C078);2020c#õ“‰ŒÆ˜6;’!˜6‘§‘8]Ï.
ë•©z
[1]Hartnell,B.L.(1995)Firefighter!AnApplicationofDomination.Presentationatthe25th
ManitobaConferenceonCombinatorialMathematicsandComputing, University ofManitoba,
Winnipeg,Canada.
DOI:10.12677/aam.2021.10114314063A^êÆ?Ð
0ƒ•
[2]Cai,L.Z.andWang,W.F. (2009)TheSurvivingRateofaGraphfor theFirefighterProblem.
DiscreteMathematics,23,1814-1826.https://doi.org/10.1137/070700395
[3]Ng,K.L.andRaff,P.(2008)AGeneralizationoftheFirefighterProblemonZ×Z.Discrete
AppliedMathematicsandCombinatorialComputing,156,730-745.
[4]Wang,W.,Finbow,S.andWang,P.(2010)OntheSurvivingRateofaGraph.Theoretical
ComputerScience,411,3651-3660.https://doi.org/10.1016/j.tcs.2010.06.009
[5]Adjiashvili,D.,Baggio,A.andZenklusen,R.(2017)FirefightingonTreesbeyondIntegrality
Graphs.ProceedingsoftheTwenty-EighthAnnualACM-SIAMSymposiumonDiscreteAlgo-
rithms(SODA2017),Barcelona,16-19January2017,2364-2383.
https://doi.org/10.1137/1.9781611974782.156
[6]Shorck,R.andWu,F.Y.(2000)SpanningTreesonGraphsandLatticesindDimensions.
JournalofPhysicsA:MathematicalandGeneral,33,3881-3902.
https://doi.org/10.1088/0305-4470/33/21/303
DOI:10.12677/aam.2021.10114314064A^êÆ?Ð

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