消防員問題圖的存活率研究.pdf

1、消防員問題(Firefighter Problem)是由著名計算機理論學(xué)家Hartnell在第25屆組合數(shù)學(xué)與計算大會上提出的.設(shè)G是一個有n個頂點的連通圖，k是正整數(shù).假設(shè)火在圖G的某一點v處燃起，消防員選擇k個未著火的頂點進行保護（一旦某個頂點被保護，則在整個過程中都將處于被保護狀態(tài)），然后火蔓延到v的未加保護且沒著火的鄰點.依次下去，火和消防員交替地在圖G上移動，直到火不能繼續(xù)蔓延，整個過程結(jié)束，消防員的任務(wù)是使最后獲救的點數(shù)最多

2、.消防員問題是一個離散的動態(tài)傳播模型，與疫情控制，謠言傳播，森林防火等實際問題密切相關(guān).
　　存活數(shù)snk（v）表示當火在v處燃起時k個消防員最多能保護的頂點數(shù).當火隨機地在圖G的一個頂點燃起時，k個消防員最多能保護的頂點數(shù)的平均值稱為圖G的存活率，記為ρk(G)，即ρk(G)=∑v∈v(G) snk（v）/n2.
　　圖的存活率是研究圖的結(jié)構(gòu)和圖的防火能力的一個重要參數(shù)，它是由Cai和Wang首次提出的.Wang等人運用概

3、率方法證明了:給定正整數(shù)七，對任意正數(shù)ε，幾乎所有圖的k-存活率都小于ε.因此，研究存活率大于某個常數(shù)的圖類具有十分重要的意義.給定一個圖G，如果存在常數(shù)c，使得ρk(G)≥c＞0，則稱圖G為k-好的.Kong等人以及Esperet等人分別獨立證明了平面圖是4-好的，并且Esperet等人進一步猜想平面圖是2-好的.
　　本文主要研究了幾類重要圖類的存活率，全文共分6章.第二章和第三章主要圍繞Esperet猜想展開，第四章和第五章

4、分別研究平面定向圖和1-平面圖的存活率，最后一章研究了一類平面圖的邊存活率.
　　在第一章，我們先給出與本文有關(guān)的一些概念和符號，簡述了相關(guān)領(lǐng)域的研究背景和研究現(xiàn)狀，同時也給出了本文的主要研究結(jié)果和證明方法.
　　在第二章，我們研究了平面圖G的3-存活率，證明了:若G是一個平面圖，則存在一個常數(shù)c使得ρ3(G)＞c，其中c=1/54019981，即平面圖是3-好的，改進了已有的結(jié)果.
　　在第三章，我們研究了不含6-圈

5、平面圖的2-存活率，證明了:如果G是不含6-圈的非平凡平面圖，則ρ2(G)＞1/85，即不含6-圈平面圖是2-好的，部分解決了Esperet猜想.
　　在第四章，我們探討了有向圖的存活率，證明了:如果→G是一個平面定向圖，那么ρ2（→G）＞1/40;如果→G是一個不含4-圈平面定向圖，那么ρ（→G）＞1/51.
　　在第五章，我們主要研究了1-平面圖的存活率，證明了:如果G是1-平面圖，那么ρ6(G)＞1/163，即1-平面