本文關(guān)鍵詞：平面圖的存活率

  更多相關(guān)文章： 防火問題 存活率 邊存活率 圈 平面圖

【摘要】：設(shè)G是含有n≥2個頂點和m≥1條邊的連通圖,正整數(shù)k≥1.假設(shè)火在圖G的某一個頂點v處開始燃燒,消防員選擇一些頂點開始保護(hù).在每一步中,消防員選擇k個未燃燒的頂點進(jìn)行保護(hù),然后,火向已燃燒頂點的鄰點(未被保護(hù)的)蔓延.設(shè)snk(v)表示當(dāng)v為火源時,整個防火過程中消防員最多可救下的頂點數(shù).可救下的頂點的平均比率稱為G的j-存活率,記為ρk(G),即假設(shè)火在圖G的某一條邊uv的兩個端點(相鄰的兩個頂點)處開始燃燒,消防員選擇G中的一些頂點開始保護(hù).在第一步中,消防員選擇k個未燃燒的頂點進(jìn)行保護(hù),在接下去的每一步中,消防員選擇l個未燃燒的頂點進(jìn)行保護(hù).在每一步的最后,火向已燃燒頂點的鄰點(未被保護(hù)的)蔓延.依次下去,火和消防員交替地在圖G上移動.當(dāng)火無法再蔓延時,整個防火過程結(jié)束.設(shè)sn'(k,l)(uv)表示當(dāng)uv為火源時,整個防火過程中消防員最多可以救下的頂點數(shù).圖G的(k,l)-邊存活率,ρ(k,l)'(G)定義為本論文主要研究了平面圖的存活率和邊存活率,共分為三章.第一章介紹圖的一些基本概念,簡述存活率的部分研究結(jié)果,并給出了本文的主要結(jié)果.第二章研究平面圖的2-存活率,證明了下面一些結(jié)果：(1)無5-圈平面圖的2-存活率ρ2(G)1/363；(2)無7-圈平面圖的2-存活率ρ2(G)1/783；(3)無6-圈平面圖的2-存活率p2(G)1/41.第三章研究平面圖的邊存活率,設(shè)G是最小度δ(G)≥3的平面圖,證明了下面一些結(jié)果：(1)ρ'(5,2)(G)11/3753；(2)若G不含3-圈,則ρ'(4,2)(G)≥1/24;(3)若G不含3,4-圈,則ρ'(3,2)(G)≥1/6.
【關(guān)鍵詞】：防火問題 存活率 邊存活率 圈 平面圖
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-5
• ABSTRACT5-8
• 1 緒論8-14
• 1.1 研究背景8-12
• 1.2 基本概念12-14
• 2 平面圖的2-存活率14-51
• 2.1 預(yù)備引理14-18
• 2.2 無5-圈平面圖的2-存活率18-26
• 2.3 無7-圈平面圖的2-存活率26-39
• 2.4 無6-圈平面圖的2-存活率39-51
• 3 平面圖的邊存活率51-61
• 3.1 預(yù)備引理51-53
• 3.2 平面圖的(5,2)-邊存活率53-58
• 3.3 無3-圈平面圖的(4,2)-邊存活率58-59
• 3.4 無3,4-圈平面圖的(3,2)-邊存活率59-61
• 參考文獻(xiàn)61-64
• 在學(xué)期間的研究成果及發(fā)表的論文64-65
• 致謝65-67
• 浙江師范大學(xué)學(xué)位論文誠信承諾書67

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 石琳;;調(diào)和平衡圖直徑與頂點數(shù)的關(guān)系[J];內(nèi)蒙古大學(xué)學(xué)報(自然科學(xué)版);1992年01期

2 蔡茂誠;圖的路連通問題[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);1994年03期

3 施永兵;關(guān)于UC圖[J];自然雜志;1984年12期

4 郭玉端;關(guān)于頂點子集凝聚度的若干定理(續(xù))[J];福州大學(xué)學(xué)報(自然科學(xué)版);1992年02期

5 鄭漢鼎;樹的序列表示法及其在數(shù)樹上的應(yīng)用[J];科學(xué)通報;1981年20期

6 李萃萃;;波蘭表達(dá)式構(gòu)成圖及頂點數(shù)的探討[J];韶關(guān)學(xué)院學(xué)報;2010年12期

7 蘇鳳婷;唐高華;黃立強;;樹圖中進(jìn)攻性聯(lián)盟的頂點數(shù)上界[J];廣西科學(xué);2008年04期

8 王應(yīng)前;K方圖的若干性質(zhì)[J];安慶師范學(xué)院學(xué)報(自然科學(xué)版);1996年04期

9 劉象武,何宇新;兩類滿足A(H)=3的圖[J];數(shù)學(xué)雜志;1989年04期

10 賴在抗;;L—冪和樹的一類全序子集[J];新疆大學(xué)學(xué)報(自然科學(xué)版);1982年02期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 焦繼業(yè);低功耗高性能移動圖形頂點處理器設(shè)計關(guān)鍵技術(shù)研究[D];西安電子科技大學(xué);2013年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前4條

1 丁鑫;基于BSP模型的分布式圖計算系統(tǒng)性能優(yōu)化研究[D];復(fù)旦大學(xué);2014年

2 伍婷婷;平面圖的存活率[D];浙江師范大學(xué);2015年

3 屠九如;樹的密度與平均頂點數(shù)[D];上海交通大學(xué);2013年

4 趙福生;基于Web服務(wù)的路徑計算實用算法的設(shè)計與實現(xiàn)[D];華東師范大學(xué);2012年

，

本文編號：539325