最優圓石分配圖

Abstract

最優圓石分配圖 研 究 生: 史 青 林 指導教授: 傅 恆 霖 國立交通大學應用數學系 摘 要 給一個圖G, 我們將p個圓石放在圖G中的點。 一步圓石移動(pebbling move)定義為從G中的一點v拿兩個圓石然後放一個到與v相鄰的點。一個G的分配方法(distributing configuration)δ是一個將G 中的點對映到非負整數的函數,δ(v)表示在v點中所分配的圓石數。 令α是一個將G 中的點對映到非負整數的函數。 一個G 的α-圓石分配(α-pebbling)是一個分配方法且滿足對於任一G中被選定的點v, 我們都可以經由一序列的圓石移動後將α(v)個圓石移到點v。 如果對每一個G中的點v, α(v)=l, l是一個正整數, 我們稱這樣 的α-圓石分配為G的l -圓石分配(l-pebbling)。 G 的最優α-圓石分配數(optimalα-pebbling number)定義為一個最小的整數p 使得存在一個G 的α-圓石分配只需要使用p 個圓石。 G 的最優l-圓石分配數(optimal l-pebbling number)是一個G 的最優α-圓石分配數且α滿足對每一個G中的點v, α(v)=l, l是一個正整數。 我們定義G 的最優圓石分配數(optimal pebbling number)為G 的最優1-圓石分配數。 此外, 我們也定義G 的圓石分配數(pebbling number)為最小的整數p 使得任一個在G中使用p個圓石的分配方法都是G 的1-圓石分配。 本篇論文主要是在研究圖的最優圓石分配數。 第一章我們介紹本篇論文的研究背景以及所使用的一些基本定義。 為了整篇論文的完整性, 我們在第二章介紹有關研究圓石分配數目前已知的結果。 接著在第三章我們找出路徑圖(path)的最優α-圓石分配數, 此結果可推得毛毛蟲(caterpillar) 的最優圓石分配數。 在第四章, 我們找出完全m-元樹(complete m-ary tree)的最優圓石分配數。 在第五章, 我們研究多維體圖(hypercube)的最優圓石分配數的上界。 最後, 在第六章我們給本篇論文做一個結論。

\documentstyle [12pt]{report} \topmargin=0in \oddsidemargin=0.3truein \evensidemargin=0.25truein \textwidth=6truein \textheight=8.7truein \Large \begin{document} \begin{center} {\bf Optimally Pebbling Graphs}\\ \vspace{2.0cm} \normalsize Student: Chin-Lin Shiue \hspace{\fill} Advisor: Hung-Lin Fu\\ \vspace{1.0cm} \baselineskip=30pt Department of Applied Mathematics\\ National Chiao Tung University\\ \vspace{1.0cm} \large {\bf Abstract}\\ \end{center} \normalsize \baselineskip=25pt \ \ \ \ Let $G$ be a simple graph. Suppose $p$ pebbles are distributed onto the vertices of $G$; then a pebbling move consists of removing two pebbles from one vertex $v\in V(G)$ and then placing one pebble at an adjacent vertex of $v$. A distributing configuration of $G$, $\delta$, is a mapping from $V(G)$ into the set of non-negative integers such that $\sum_{v\in V(G)}\delta(v)=p$, where $\delta(v)$ is the number of pebbles placed on $v$ for each vertex $v\in V(G)$. Let $\alpha$ be a mapping from $V(G)$ into the set of non-negative integers. An $\alpha$-pebbling of $G$ is a distributing configuration of $G$ such that whenever we choose a vertex $v\in V(G)$, we can move $\alpha(v)$ pebbles to the vertex $v$ by a sequence of pebbling moves. An $\l$-pebbling of $G$ is an $\alpha$-pebbling of $G$ such that $\alpha(v)=l$ for each $v \in V(G)$ where $l$ is a positive integer. The optimal $\alpha$-pebbling number of $G$, $f'_\alpha(G)$, is the least integer $p$ such that there exists an $\alpha$-pebbling of $G$ which uses $p$ pebbles. The optimal $l$-pebbling number of a graph $G$, $f'_l(G)$, is the least integer $p$ such that there exists an $\l$-pebbling of $G$ which uses $p$ pebbles. We define the optimal pebbling number $f'(G)$ of a graph $G$ as the optimal $1$-pebbling number of $G$. On the other hand, the pebbling number $f(G)$ of a graph $G$ is defined as the minimum number of pebbles $p$ such that each distributing configuration of $G$ using $p$ pebbles is a $1$-pebbling of $G$.\\ In this thesis, we mainly study the optimal pebbling number of a graph. In Chapter 1, we introduce the background of this study and give some basic definitions. For completeness, we also introduce the known results on the pebbling number of a graph in Chapter 2. In Chapter 3, we study the optimal $\alpha$-pebbling number of the path. As a consequence, we obtain the optimal pebbling number of the caterpillar. In Chapter 4, we find the optimal pebbling number of the complete $m$-ary tree. In Chapter 5, we give an upper bound for the optimal pebbling number of the hypercube. Finally, in Chapter 6, we give a remark to conclude this thesis.\\ \end{document}