尋找萬用型金字塔網路的彩虹連結

CCUR > College of Business > Department of Information Management & Graduate Institute of Information Management > Thesis > Item 987654321/24509

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/24509

Title:	尋找萬用型金字塔網路的彩虹連結 On Finding a Rainbow Connection in a Versatile Pyramid Network
Authors:	吳則建
Contributors:	資訊管理學系
Keywords:	圖論 graph theory 彩虹連結數 rainbow connection number 彩虹連結 rainbow connection 萬用型金字塔 Recursive Transpose-Connected Cycles pyramid network
Date:	2012
Issue Date:	2013-03-16 14:40:25 (UTC+8)
Abstract:	對一網路圖中所有邊分別賦予一數字，而一種數字代表一種顏色，並且使得任兩點間存在著彩虹路徑，而於彩虹路徑內各邊所使用的顏色皆不同。若一網路圖中任意兩點之間存在著彩虹路徑，則此網路圖即為彩虹連結圖，而所使用顏色的最少數量稱為彩虹連結數。彩虹連結概念是由Chartrand等學者於2008年所提出，係針對給定的圖形架構尋求一種對於節點的圖色法，讓任一對節點間存在一條彩虹路徑。由於不同的網路拓樸之連接特性未必相同，因此我們對於擇定的網路拓樸，先了解其圖形特性，然後研究出圖形之彩虹連結相關結果。文獻顯示有多位學者針對不同的圖形進行彩虹連結相關研究。然而對於新興的網路拓樸之研究成果相對較少被提出。據我們所知，至目前為止，萬用型金字塔網路之彩虹連結相關問題還未曾有人提出具體成果。本論文以萬用型金字塔網路為研究對象圖形，對於以四循環為網路架構基礎的萬用型金字塔網路提出一彩虹著色方法，因此，本研究得到一個以四循環為架構基礎的萬用型金字塔網路之彩虹連結數上限值。 Edge coloring of a graph is a function from its edge set to the set of natural numbers. A path in an edge colored graph with no two edges sharing the same color is called a rainbow path. An edge-colored graph is rainbow connected if any two vertices are connected by a rainbow path. Rainbow connection number is the minimum number of colors needed to color the edges of graph. The concept of rainbow connection was introduced by Chartrand et al. in 2008. The rainbow connection problem is to find a vertex coloring for a given graph so that each pair of vertices of the graph having at least a rainbow path. As the characteristics and type of different network topologies are not the same, so we first devote ourselves to study a specify network topology. Then we find results of rainbow connection for the given graph. Some results of rainbow connection for graphs were shown by the published papers, while the results for new network topologies were lack of discussion. As far as we know, the rainbow connection on Recursive Transpose-Connected Cycles pyramid networks is unknown We consider the problem for Recursive Transpose-Connected Cycles pyramid networks, finally we propose a rainbow coloring for the RTCC pyramid networks based on 4-cycles. Then an upper bound of rainbow connection number is established for our studied interconnection networks.
Appears in Collections:	[Department of Information Management & Graduate Institute of Information Management] Thesis

Files in This Item:

File	Description	Size	Format
http___thesis.lib.pccu.edu.tw_cgi-bin_cdrfb3_gsweb.cgi_ccd=xKzZv1&o=e2&dbid=I%2B327%20.pdf		2312Kb	Adobe PDF	818	View/Open

View Licence

Loading...