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

文化大學機構典藏 CCUR > 商學院 > 資訊管理學系暨資訊管理研究所 > 博碩士論文 > Item 987654321/24509

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://irlib.pccu.edu.tw/handle/987654321/24509

题名:	尋找萬用型金字塔網路的彩虹連結 On Finding a Rainbow Connection in a Versatile Pyramid Network
作者:	吳則建
贡献者:	資訊管理學系
关键词:	圖論 graph theory 彩虹連結數 rainbow connection number 彩虹連結 rainbow connection 萬用型金字塔 Recursive Transpose-Connected Cycles pyramid network
日期:	2012
上传时间:	2013-03-16 14:40:25 (UTC+8)
摘要:	對一網路圖中所有邊分別賦予一數字，而一種數字代表一種顏色，並且使得任兩點間存在著彩虹路徑，而於彩虹路徑內各邊所使用的顏色皆不同。若一網路圖中任意兩點之間存在著彩虹路徑，則此網路圖即為彩虹連結圖，而所使用顏色的最少數量稱為彩虹連結數。彩虹連結概念是由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.
显示于类别:	[資訊管理學系暨資訊管理研究所 ] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
http___thesis.lib.pccu.edu.tw_cgi-bin_cdrfb3_gsweb.cgi_ccd=xKzZv1&o=e2&dbid=I%2B327%20.pdf		2312Kb	Adobe PDF	818	检视/开启

检视Licence

在CCUR中所有的数据项都受到原著作权保护.

数据加载中.....