서지주요정보
Circulant graphs and their application to communication networks = Circulant 그래프 및 그의 통신망에 대한 응용
서명 / 저자 Circulant graphs and their application to communication networks = Circulant 그래프 및 그의 통신망에 대한 응용 / Jung-Heum Park.
저자명 Park, Jung-Heum ; 박정흠
발행사항 [대전 : 한국과학기술원, 1992].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8002512

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 92004

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

In this thesis, network metrics of circulant graphs are investigated, and a new topology of communication networks is proposed. We consider diameters of circulant graphs with degree four of less and diameters of circulant graphs which are isomorphic to the product of two nontrivial circulant graphs. We present a necessary and sufficient condition for a strongly connected circulant digraph with two jumps to have a directed hamiltonian cycle. The problems of constructing circulant minimal broadcast digraphs and regular minimal broadcast digraphs with as small degree as possible are considered. We propose a construction of circulant graphs with the property that every circulant graph can be obtained by applying the constructions repeatedly to trivial graphs, and give a generalization of the construction by relaxing some constraints posed on the construction. Many graphs including hypercubes with the maximum connectivity and edge connectivity can be obtained by applying the generalized constructions repeatedly to trivial graphs. The connectivity and edge connectivity of graphs obtained by applying the generalized construction to d connected graphs are considered. We also consider the connectivity and edge connectivity of digraphs obtained by applying the digraph-form generalized construction to d strongly connected digraphs. A new topology of communication networks is proposed. The network G (N, d), d≥2, is a circulant graph with N nodes and jumps $d^i$, 0i$\iceil\log_dN\iceil$-1. The network is vertex transitive (not edge transitive), and has a hamiltonian cycle. The connectivity and edge connectivity, diameter, mean intemode distance, and node visit ratio and edge visit ratio (under the uniform message distribution) of G($cd^m$, d), 1≤c

Circulant그래프의 지름, 해밀톤 특성, 방송, 노드 및 에지 연결도 등 통신망 척도에 대해 고찰하고, Circulant 그래프 부류에 속하는 새로운 통신망의 위상을 제안하였다. 분지수가 4 이하인 Circulant 그래프와 두 Circulant 그래프의 곱으로 표현될 수 있는 Circulant그래프의 지름을 고려하였고, 두 개의 점프를 가진 유향 Circulant그래프가 해밀톤 사이클을 가질 필요 충분 조건을 제시하였다. 그리고 Circulant 그래프와 정규 그래프의 부류에 속하면서 분지수가 작은 최소 시간 방송 유향 그래프를 설계하는 문제를 고려하였다. 모든 Circulant그래프를 하나의 노드만 가진 그래프로부터 반복 적용하여 얻을 수 있는 "설계"를 제시하고, 설계에 가해진 제약을 완화하여 "일반적 설계"를 제시하였다. 일반적 설계를 이용하면 Circulant그래프뿐만 아니라 하이퍼큐브 등 망특성이 좋은 많은 그래프를 얻을 수 있다. 일반적 설계를 이용하여 얻을 수 있는 그래프의 노드 연결도와 에지 연결도를 고찰하였다. 그리고 유향 그래프 형태의 설계와 일반적 설계를 제시하고, 유향 그래프 형태의 일반적 설계를 적용하여 얻을 수 있는 유향 그래프의 노드 및 에지 연결도도 고찰하였다. 새로운 통신망의 위상 G(N, d)를 제안하고, N = $cd^m$(1≤c

서지기타정보

서지기타정보
청구기호 {DCS 92004
형태사항 ix, 104 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 박정흠
지도교수의 영문표기 : Kyung-Yong Chwa
지도교수의 한글표기 : 좌경룡
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 Reference : p. 98-104
주제 Electric network topology.
그래프 이론. --과학기술용어시소러스
프로토콜. --과학기술용어시소러스
통신 교환. --과학기술용어시소러스
Graph theory.
QR CODE qr code