關(guān)于特殊圖的pebbling數(shù)的研究.pdf

1、圖的pebbling數(shù)問題起源于組合數(shù)論和群論，最初是由Lagarias和Saks提出來(lái)的，由Chung第一次引入到文章中的。圖的pebbling問題是一個(gè)資源運(yùn)送模型，由在一個(gè)簡(jiǎn)單的連通圖的點(diǎn)上的pebble分配開始，pebbling移動(dòng)是指從一個(gè)頂點(diǎn)移走兩個(gè)pebble而把其中一個(gè)移到與其相鄰的一個(gè)頂點(diǎn)上。我們可以把pebble看做是燃料罐，則在移動(dòng)過(guò)程中的pebble損失可以看做為運(yùn)輸費(fèi)用。圖G的pebbling數(shù)f(G)是指最小

2、的正整數(shù)n，使得n個(gè)pebble無(wú)論如何放置在G上，總可以通過(guò)一系列的pebbling移動(dòng)把一個(gè)pebble移到任意一個(gè)頂點(diǎn)上。
　　 本文針對(duì)圖的pebbling問題進(jìn)行了研究，首先介紹了圖的pebbling的研究背景及意義，發(fā)展和現(xiàn)狀。其次，在前人研究的基礎(chǔ)下，本文重點(diǎn)研究了齒輪圖Dn，4及其更一般的情況Dn，2m的pebbling問題。求出了齒輪圖Dn，4的pebbling數(shù)，進(jìn)而求出了更一般的情況圖Dn,2m的pebbl