표제지
목차
Abstract 8
I. 서론 10
1. 연구 배경 10
2. 연구 내용 13
3. 논문 구성 14
II. 관련연구 15
1. 상호연결망의 이론적 배경 15
1.1. 상호연결망의 정의 15
1.2. 망 평가척도 15
2. 상호연결망의 분류 18
2.1. 메쉬 18
2.2. 하이퍼큐브 19
2.3. 스타 그래프 21
3. 하이퍼큐브의 분류 23
3.1. 폴디드 하이퍼큐브(Folded Hypercube) 23
3.2. 하프 하이퍼큐브(Half Hypercube) 24
3.3. 계층적 하이퍼큐브(HCN, Hierarchical Cubic Network) 25
III. 로그-하이퍼큐브 그래프: 새로운 스타 그래프 제안 26
1. 로그-하이퍼큐브 그래프 정의 26
2. 로그-하이퍼큐브 그래프 성질 31
3. 로그-하이퍼큐브 라우팅 알고리즘 및 지름 분석 39
IV. 결론 45
참고문헌 46
국문초록 51
[표1] 하이퍼큐브와 변형된 연결망들의 비교 20
[표2] 하이퍼큐브 그래프 부류의 분지수 비교표 30
[표3] 하이퍼큐브 부류와 로그-하이퍼큐브의 망비용 비교 44
[그림1] 4×4 Mesh 그래프 18
[그림2] 2차원과 3차원의 Hypercube 그래프 19
[그림3] 3차원(왼쪽)과 4차원(오른쪽)의 Star 그래프 21
[그림4] 3차원 폴디드 하이퍼큐브 FQ₃ 23
[그림5] 4차원 하프 하이퍼큐브 HH₄ 24
[그림6] 3차원 계층적 하이퍼큐브 HCN(2,2) 25
[그림7] 노드개수와 분지수의 로그 함수 26
[그림8] n(=2k)에서 로그-에지 Ln/2k 모습(이미지참조) 27
[그림9] 로그-하이퍼큐브 LH₂, LH₄ 그래프 29
[그림10] LH2k에서 LH2(k+1)로 재귀적 확장(이미지참조) 33
[그림11] LH4(SA), {00,01,10,11}∈SA(이미지참조) 34
[그림12] LHn그래프의 클러스터를 이용한 완전그래프 구조(이미지참조) 36
[그림13] 노드 S의 인접한 노드 log n개를 제거한 연결망(이미지참조) 37
[그림14] 노드 S에 인접한 노드 log (n-1)개와... 38