토러스 T(4k,2l)는 8kl개의 노드로 구성된 연결망으로 각 노드의 주소는 (a,b)로 표현된다(1≤k,l, 0≤a≤4k-1, 0≤b≤2l-1, a,b=정수). 노드 주소 (a,b)에서 a는 X축 좌표, b는 Y축 좌표를 나타낸다. T(4k,2l)의 노드 (a,b)에 인접한 두 노드 U와 V를 연결하는 에지는 다음과 같다. (a,b)-((a+1)%4k,b), (a,b)-((a-1+4k)%4k,b), (a,b)-(a,(b+1)%2l), (a,b)-(a,(b-1+2l)%2l). 심벌 ‘%’는 나머지 연산자이다.
3차원 하이퍼큐브 Q3는 8개의 노드로 구성되었으며, 노드 주소는 3개의 이진비트스트링으로 표현되며, 주소에서 1비트가 다른 두 노드 사이에 에지가 발생한다.
하이퍼-토러스 연결망 QT(m,n)은 Q3를 기본 모듈로삼는 m×n 토러스 연결망이다(1≤m,n). QT(m,n)의 에지는 외부에지와 내부에지로 구성된다. 내부에지는 Q3를 구성하는 에지이고, 외부에지는 모듈과 모듈을 연결하는 에지이다. 각 모듈의 주소는 (x,y), 각 노드의 주소는 (x,y,q)로 나타낸다. x는 X축 좌표, y는 Y축 좌표, q는 기본 모듈 Q3에 있는 노드 주소를 나타낸다. 외부에지는 다음과 같다.
① 세로 에지: ((x,y,101), (x,(y+1)%n,001))과 ((x,y,001), (x,(y-1+n)%n,101)). ② 가로 에지: ((x,y,111), ((x+1)%m,y,011))과 ((x,y,011), ((x-1+m)%m,y,111)). ③ 사선 에지: ((x,y,110), ((x+1)%m,(y+1)%n,010))과 ((x,y,010), ((x-1+m)%m,(y-1+n)%n, 110)). ④ 역사선 에지: ((x,y,000), ((x-1)%m,(y+1+n)%n,100))과 ((x,y,100), ((x+1+m)%m,(y-1)%n,000)).
임의의 한 연결망을 G라고 할 때, G의 노드 집합을 V(G), 에지 집합을 L(G), 경로 집합을 P(G)로 표현하겠다. 연결망 G(V,L)를 G'(V',L')로 임베딩 하는 함수 (Φ,ρ)은 V(G)의 노드들을 V'(G')의 노드들로 사상하고, L(G)의 에지들을 P(G')의 경로들로 사상하는 것을 말한다. 즉, Φ: V→V'이고, ρ: L→P(G')이다. 임베딩의 비용을 나타내는 척도로 연장율과 밀집율과 확장율이 있다. 연장율은 G의 한 에지가 G'에 사상되었을 때 경로 길이를 나타내고, 밀집율은 G'의 한 에지가 임베딩을 위해 사용된 횟수를 나타내며, 확장율은 G의 노드의 개수에 대한 G'의 노드의 개수의 비율이다.
메쉬 구조 4×2는 Q3의 서브연결망임을 그림 1과 2에 의해 쉽게 알 수 있다. 그러므로 다음과 같은 보조정리를 구할 수 있다.
보조정리 1 메쉬 구조 4×2는 Q3에 연장율 1, 확장율 1, 밀집율 1로 임베딩 가능하다.
임베딩을 위해 Q3의 노드 주소를 그림 3과 같이 정수로 나타내겠다.
증명을 위해 토러스 T(4k,2l)의 노드 (a,b)의 노드 주소를 다음과 같이 정의하겠다. 노드 이다. 주소에서 b가 짝수이면 q=a%4이고, b가 홀수이면 q=(a%4)+4이다. 라고 하자. 그러면 동일한 주소 (x,y)를 갖는 노드의 개수는 8개 가 되고, 이 8개의 노드로 구성되는 연결망은 4×2 메쉬구조가 된다. 그리고 토러스 T(4k,2l)를 구성하는 4×2 메쉬의 개수는 k×l이다. 본 논문에서 사용하는 라우팅 경로(routing path)의 표현은 다음과 같다. 예를 들어 임의의 3개 노드 {(x,y,4), (x,y,5), (x,y,6)}에서 노드 (x,y,4)에서 출발하여 노드 (x,y,5)를 경유하고, 도착 노드가 (x,y,6)인 경우 라우팅 경로는 (x,y,4)-(x,y,5)-(xx,y,6)로 표현하였다. 즉 노드와 노드 사이의 하이픈(-)은 2개 노드를 연결하는 에지를 나타낸다. 위의 라우팅 경로에서 (x,y,4)-(x,y,5)은 노드 (x,y,4)과 (x,y,5)를 연결하는 한 에지를 의미한다.
정리 1 토러스 T(4k,2l)는 QT(m,n)에 연장율 5, 밀집율 4, 확장율 1에 임베딩 가능하다(k=m, l=n).
증명 토러스 T(4k,2l)의 노드 (a,b)=(x,y,q)는 QT(m,n)의 노드에 다음과 같이 임베딩한다.
Φ(a,b)=(x,y,q), b가 짝수이면 q=a%4이고, b가 홀수이면 q=(a%4)+4이다. 위의 임베딩 기법을 이용하면 T(4k,2l)의 각 4×2 메쉬는 QT(m,n)의 기본 모듈인 Q3에 각각 임베딩 된다. 4×2 메쉬 내부의 에지가 Q3의 내부 에지에 임베딩 되는 경우는 보조정리 1에 의해 연장율 1, 밀집율 1, 확장율 1임을 알 수 있으므로 본 증명에서는 4×2 메쉬와 4×2 메쉬를 연결하는 에지의 임베딩만을 증명한다. 노드 V와 인접한 노드 W의 조건식에 따라 다음의 2가지 경우로 나누어 증명하겠다.
경우 1) V=(a,b)와 W=(a,(b+1)%2l)가 인접한 경우: Φ(V)=(x,y,(a%4)+4)이고, Φ(W)= (x,(y+1)%n,a%4)이다.
경우 1-1) (a%4)+4=4인 경우: Φ(V)=(x,y,4)와Φ(W)=(x,y+1,0) 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x, y, 4) - (x, y, 5) - (x, y, 6) - (x, (y+1)%n, 5) - (x,(y+1)%n,4)-(x,(y+1)%n,0). ρ(Φ(V),Φ(W))의 경로 길이는 5이므로, 연장율은 5이다.
경우 1-2) (a%4)+4=5인 경우: Φ(V)=(x,y,5)와 Φ(W)=(x,y+1,1) 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,5)-(x,y,6)-(x,(y+1)%n,5)-x,(y+1)%n,1). ρ(Φ(V),Φ(W))의 경로 길이는 3이므로, 연장율은 3이다.
경우 1-3) (a%4)+4=6인 경우: Φ(V)=(x,y,6)와 Φ(W)=(x,y+1,2)사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,6)-(x,y+1,5)-(x,(y+1)%n,1)-(x,(y+1)%n,2). ρ(Φ(V),Φ(W))의 경로 길이는 3이므로, 연장율은 3이다.
경우 1-4) (a%4)+4=7인 경우: Φ(V)=(x,y,7)와 Φ(W)=(x,y+1,3)사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,7)-(x,y,6)-(x,(y+1)%n,5)-(x,(y+1)%n,6)-(x,y+1,7)-(x,(y+1)%n,3). ρ(Φ(V),Φ(W))의 경로 길이는 5이므로, 연장율은 5이다.
위의 4가지 경우의 각 경로 ρ(Φ(V),Φ(W)) 상에는 에지 (x,y,6)-(x,(y+1)%n,5)이 모두 사용되었음을 알 수 있다. 그러므로 경우 1의 밀집율은 4임을 알 수 있다.
경우 2) V=(a,b)와 W=((a+1)%4k,b)가 인접한 경우:
경우 2-1) b가 짝수인 경우: Φ(V)=(x,y,3)이며, Φ(W)=((x+1)%m,y,0)이므로 두 노드 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,3)-(x,y,2)-((x+1)%m,y,1)-((x+1)%m,y,0). ρ(Φ(V),Φ(W))의 경로 길이는 3이므로, 연장율은 3이다.
경우 2-2) b가 홀수인 경우: Φ(V)=(x,y,7)이며, Φ(W)=((x+1)%m,y,4)이므로 두 노드 사이의 경로는 다음과 같다. ρ(Φ(V),Φ(W))=(x,y,7)-(x,y,3)-(x,y,2)-((x+1)%m,y,1)-((x+1)%m,y,0)-((x+1)%m,y,4). ρ(Φ(V),Φ(W))의 경로 길이는 5이므로, 연장율은 5이다.
위의 2가지 경우에 의해 경우 2의 밀집율은 2임을 알 수 있다. 그러므로 토러스 T(4k,2l)는 QT(m,n)에 연장율 5, 밀집율 4, 확장율 1에 임베딩 가능하다.
정리 2 QT(m,n)는 T(4k,2l)에 연장율 3, 밀집율 3, 확장율 1에 임베딩 가능하다(k=m, l=n).
증명 QT(m,n)의 노드 (x,y,q)는 T(4k,2l)의 노드에 다음과 같이 임베딩 한다. Φ((x,y,q))=(x,y,q)=(a,b). 위의 임베딩 기법을 이용하면 QT(m,n)의 기본 모듈인 Q3는 T(4k,2l)의 4×2 메쉬에 각각 임베딩 된다. 다음의 2가지 경우로 나누어 증명하겠다.
경우 1) 내부에지가 임베딩 되는 경우:
경우 1-1) 노드 V=(x,y,0)의 인접 노드가 W=(x,y,3)인 경우: Φ(V)=(x,y,0)=(a,b)이고, Φ(W)=(x,y,3)=((a+3)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a+1)%4k,b)-((a+2)%4k,b)-((a+3)%4k,b).
경우 1-2) 노드 V=(x,y,4)의 인접 노드가 W=(x,y,7)인 경우: Φ(V)=(x,y,4)=(a,b)이고, Φ(W)=(x,y,7)= ((a+3)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a+1)%4k,b)-((a+2)%4k,b)-((a+3)%4k,b).
경우 1-3) 경우 1-1)과 1-2)를 제외한 Q3의 나머지 내부 에지가 임베딩되는 경우: 노드 (x,y,0)과 (x,y,3)을 연결하는 에지와 노드 (x,y,4)와 (x,y,7)은 연결하는 에지를 제거한 Q3는 4×2 메쉬 구조임을 쉽게 알 수 있으므로 이 경우 연장율이 1임을 알 수 있다.
경우 2) 외부에지가 임베딩 되는 경우:
경우 2-1) V=(x,y,0)와 W=((x-1+m)%m, (y-1+n)%n,3)가 인접한 경우: Φ(V)=(x,y,0)=(a,b)이고, Φ(W)=((x-1+m)%m, (y-1+n)%n, 3) =((a-1+4k)%4k, (b-2+2l)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b-1+2l)%2l)-(a,(b-2+2l)%2l)-((a-1+4k)%4k,(b-2+2l)%2l).
경우 2-2) 노드 V=(x,y,1)의 인접 노드가 W=((x-1+m)%m,y,2)인 경우: Φ(V)=(x,y,1)=(a,b)이고, Φ(W)=((x-1+m)%m,y,2)=((a-3+4k)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a-1+4k)%4k,b)-((a-2+4k)%4k,b)-((a-3+4k)%4k,b).
경우 2-3) 노드 V=(x,y,2)의 인접 노드가 W=((x+1)%m,y,1)인 경우: Φ(V)=(x,y,2)=(a,b)이고, Φ(W)=((x+1)%m,y,1)=((a+3)%4k,b)이다. ρ(Φ(V),Φ(W))=(a,b)-((a+1)%4k,b)-((a+2)%4k,b)-((a+3)%4k,b).
경우 2-4) 노드 V=(x,y,3)의 인접 노드가 W=((x+1)%m,(y+1)%n,0)인 경우: Φ(V)=(x,y,3)=(a,b)이고, Φ(W)=((x+1)%m,(y+1)%n,0)=((a+1)%4k,(b+2)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b+1)%2l)-(a,(b+2)%2l)-((a+1)%4k,(b+2)%2l).
경우 2-5) 노드 V=(x,y,4)의 인접 노드가 W=((x-1+m)%m,(y+1)%n,7)인 경우: Φ(V)=(x,y,4)=(a,b) 이고, Φ(W)=((x-1+m)%m,(y+1)%n,7)=((a-1+4k)%4k, (b+2)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b+1)%2l)-(a,(b+2)%2l)-((a-1+4k)%4k,(b+2)%2l).
경우 2-6) 노드 V=(x,y,5)의 인접 노드가 W=(x,(y-1+n)%n,6)인 경우: Φ(V)=(x,y,5)=(a,b)이고, Φ(W)=(x,(y-1+n)%n,6)=((a+1)%4k,(b-2+2l)%2l)이다. ρ(Φ(V),Φ(W))=(a,b)-(a,(b-1+2l)%2l)-(a,(b-2+2l)%2l)-((a+1)%4k,(b-2+2l)%2l).
경우 2-7) 노드 V=(x,y,6)의 인접 노드가 W=(x,(y+1)%n,5)인 경우: Φ(V)=(x,y,6)=(a,b)이고, Φ(W)=(x,(y+1)%n,5)=((a-1+4k)%4k,(b+2)%2l)이다. ρ(Φ(V), Φ(W))=(a,b)-(a,(b+1)%2l)-(a,(b+2)%2l )-((a-1+4k)%4k,(b+2)%2l).
경우 2-8) 노드 V=(x,y,7)의 인접 노드가 W=((x+1)%m,(y-1+n)%n,4)인 경우: Φ(V)=(x,y,4)=(a,b)이고, Φ(W)=((x+1)%m,(y-1+n)%n,4)=((a+1)%4k, (b-2+2l)%2l)이다. ρ(Φ(V), Φ(W))=(a, b) - (a, (b-1+2l)%2l)-(a,(b-2+2l)%2l)-((a+1)%4k, (b-2+2l)%2l).
위의 8가지 경우의 각 경로 ρ(Φ(V),Φ(W))의 연장율은 3이다. 에지 (x,y,0)-(x,y,1)은 경우 1-1), 1-3), 2-2)에서 사용되었으며, 에지 (x,y,2)-(x,y,3)은 경우 1-1), 1-3), 2-3)에서 사용되었으며, 에지 (x,y,3)-(x,y,7)은 경우 1-3), 2-4), 2-8)에서 사용 되었으므로 밀집율은 3임을 알 수 있다. 그러므로 QT(m,n)는 T(4k,2l)에 연장율 3, 밀집율 3, 확장율 1에 임베딩 가능하다.