平面圖和定向平面圖的存活率.pdf

1、設G是含有n≥2個頂點的連通圖，正整數(shù)k≥1.假設火在圖G的某個頂點v處開始燃燒，消防員選擇k個未燃燒的頂點進行防護，消防員和火在圖G上依次交替移動.一旦某個頂點被消防員防護下來了，就稱這個頂點在接下來的防火過程中一直都是受防護的.在消防員移動后，火繼續(xù)向已燃燒頂點的其他鄰點（未被防護的）蔓延.當火無法再繼續(xù)蔓延時，就稱整個防火過程結(jié)束了.設點v是著火點.在整個防火過程中，稱消防員最多能防護下來的頂點數(shù)為v的存活數(shù)，記為snk(v).當

2、火隨機地在G的某個頂點處燃起時，稱消防員最多能防護下來的頂點數(shù)的平均比例為圖G的k-存活率，記為ρk(G)，公式表示為ρk(G)=∑v∈V(G)snk（v）/n2.
　　假設有向圖D上的某一個頂點v開始起火（規(guī)定火是沿著弧的方向傳播的），消防員選擇一些未被燃燒的頂點進行防護，消防員和火在圖上依次交替移動.類似地，用snk(v)表示v的存活數(shù)，于是有向圖D的k-存活率定義為ρk(D)=∑v∈V(D)snk(v)/n2.
　　本

3、學位論文主要研究了平面圖的存活率和一類定向平面圖的存活率，共分為三章.
　　在第一章，我們介紹了圖的一些基本概念，簡述了存活率的部分研究現(xiàn)狀，并呈現(xiàn)了本文的主要研究結(jié)果.
　　在第二章，我們研究了平面圖G的2-存活率，證明了下面兩個結(jié)果:
　　(1)三角形距離大于等于9的平面圖的2-存活率ρ2(G)＞1/15228;
　　(2)不含弦6-圈的平面圖的2-存活率ρ2(G)＞1/1299.
　　在第三章，我們研