표제지
목차
ABSTRACT 8
I. 서론 10
II. 이론적 배경 13
1. 그래프 이론 13
(1) 그래프 개념 및 정의 13
(2) 그래프 분류 및 범주 특성 15
(3) 용어정의 15
(4) 활용분야 16
2. 망 비용과 (d,k)-문제 17
3. 하이퍼큐브 19
III. 회전이진 그래프 설계 21
1. 연산정의 21
2. 회전이진 그래프 정의 22
3. 위상속성 분석 23
3.1. 노드 수 23
3.2. 분지수 24
3.3. 에지 수 24
4. 이진 스패닝 트리 25
IV. 망 비용 비교와 통신 알고리즘 27
1. 라우팅 알고리즘 27
2. 지름과 망 비용 비교 28
3. 방송 알고리즘 29
4. 임베딩 알고리즘 33
V. 결론 38
참고문헌 39
[표 2.1] (d,k)-그래프에서 설계된 최대 노드 수 19
[표 4.1] 상수분지수 네트워크들과 비교 29
[그림 2.1] 쾨니히스베르크에 있는 다리 모양과 그래프 13
[그림 2.2] 5개의 노드와 4개의 에지로 구성된 그래프 14
[그림 2.3] 모양은 다르지만 두 개의 동일 그래프 15
[그림 2.4] (3,2)-moore 그래프 18
[그림 2.5] Hyper cube 20
[그림 3.1] Rotational Binary Graph 22
[그림 3.2] RBG₄에서 binary spanning tree 25
[그림 3.3] RBG5에서 one-to-all broadcasting step(이미지참조) 30
[그림 3.4] RGB₄을 Q₄에 임베딩 35
[알고리즘 3.1] constructing BST 25
[알고리즘 4.1] simple routing 27
[알고리즘 4.2] one-to-all broadcasting routing 31