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

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

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

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