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

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

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

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