圖Dn,G的pebbling數(shù)研究.pdf

1、圖論起源于十八世紀(jì)，是一門(mén)相對(duì)古老的學(xué)科。自二十世紀(jì)以來(lái)，得到了迅速的發(fā)展和廣泛的應(yīng)用。圖論作為數(shù)學(xué)的一個(gè)分支，涉及許多學(xué)科，比如，化學(xué)、物理學(xué)、網(wǎng)絡(luò)理論、計(jì)算機(jī)科學(xué)以及控制論等領(lǐng)域。圖的pebbling數(shù)問(wèn)題是由Chung最先將其引入到文獻(xiàn)當(dāng)中。在過(guò)去的二十多年中，pebbling數(shù)一直作為圖論中的熱門(mén)問(wèn)題受到眾多數(shù)學(xué)家的關(guān)注，同時(shí)也被應(yīng)用于資源運(yùn)輸，網(wǎng)絡(luò)優(yōu)化配置等領(lǐng)域。
　　一個(gè)簡(jiǎn)單連通圖上的pebbling移動(dòng)是指:從一個(gè)頂

2、點(diǎn)同時(shí)移走兩個(gè)pebble，消耗掉其中一個(gè)pebble，另一個(gè)移到與其相鄰的頂點(diǎn)上。圖G的pebbling數(shù)是最小的正整數(shù)f(G)，滿足按照f(shuō)(G)個(gè)pebble的任何一種分配方式開(kāi)始，總可以通過(guò)一系列的pebbling移動(dòng)把一個(gè)pebble移動(dòng)到圖G的任意目標(biāo)頂點(diǎn)上。pebbling移動(dòng)可以理解為，在交通運(yùn)輸?shù)倪^(guò)程中，運(yùn)送的貨物為其中的一個(gè)pebble，資源損耗既為另一個(gè)pebble.本文研究了關(guān)于圖Dn,G的pebbling數(shù)問(wèn)題。

3、圖Dn，G指的是只有一個(gè)公共頂點(diǎn)的n個(gè)圖G的并圖。主要結(jié)果如下:
　　1)介紹了圖論的背景及pebbling數(shù)的基本概念和已有結(jié)論;基于鴿巢原理，得到了關(guān)于圖Dn，Cm的pebbling移動(dòng)時(shí)的一個(gè)充分條件。
　　2)利用分類討論的思想方法，計(jì)算出了奇圈的并圖Dn，C2m+1的pebbling數(shù);運(yùn)用數(shù)學(xué)歸納法推廣并證明了鴿巢原理的衍生引理，同時(shí)得到了一個(gè)關(guān)于圖Dn，Cm的pebbling移動(dòng)的結(jié)論。
　　3)計(jì)算出了