ㄧ個連結網路(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)。我們也提出一個演算法可以找到廣義超立方體的最大引導子
圖。
