廣義超立方體圖之最大引導子圖

MUSTIR > College of Management > Department of Information Management > Research Projects in School > Item 987654321/113

Please use this identifier to cite or link to this item: http://120.105.36.38/ir/handle/987654321/113

Title:	廣義超立方體圖之最大引導子圖
Authors:	陳玉專
Contributors:	資訊管理系
Keywords:	最大引導子圖、超立方體、雙扭立方體、交叉立方體、梅氏立方體、
Date:	2008-12
Issue Date:	2010-03-23 15:37:32 (UTC+8)
Abstract:	ㄧ個連結網路(interconnection network)的拓譜結構(topological structure)可以用一個圖型G = (V,E )來表示，其中V 代表圖型G 的節點(vertex)集合、E 代表圖型G 的鏈結(edge)集合。圖型的節點子集合以V′表示，我們定義G[V′]是在圖型G 中節點V′引導出的子圖(subgraph)，G[V′]是包含節點V′以及在節點V′中任兩節點間所組成的所有鏈結(edge)圖型。ㄧ個圖型的m-引導子圖是經由給定m 個節點所引導出的圖形。一個圖型G 的最大引導子圖我們以 G V (G) m max 表示，其定義為 ( ) { ( )} V V m V G G V E m ′ ⊆ ′ = = ′ ′ , max [ ] max ] V G[V ( ) 。令maxm(G)是最大引導子圖中包含的鏈結數目。圖型G 的最大引導子圖對於網路容錯(fault tolerance)與頻寬 (bandwidth) 之估算有其應用。令m 是一個正整數，其中且，我們定義 (G) m max Σ − = = 1 0 2 r i V m li 0 1 −1 > > > r l l L l Σ − = = + i 1 0 ( )2 2 r i g m li li 。2003 年Abdel-Ghaffar 證明了在n-維超立方體(hypercubes)Qn 中，當n ≥1 且0 ≤ m ≤ 2n 時，maxm(Qn) = g(m)。在那之後，遞迴環狀圖(recursive circulant graphs)的最大引導子圖也在2005 年由 X. Yang 等人提出。我們以遞迴的方式對n ≥ 0 的廣義超立方體(generalized hypercubes) GQn 做一個定義。所有超立方體，雙扭立方體、交叉立方體與梅氏立方體都是廣義超立方體的特例。在本研究中，我們證明當n ≥ 3 且0 ≤ m ≤ 2n 時， maxm(GQn) = g(m)。我們也提出一個演算法可以找到廣義超立方體的最大引導子圖。
Appears in Collections:	[Department of Information Management] Research Projects in School

Files in This Item:

File	Description	Size	Format
97年校內專題成果報告書-資管系陳玉專.pdf		396Kb	Adobe PDF	2473	View/Open

Loading...