- 피라미드 그래프의 헤밀톤 특성
- ㆍ 저자명
- 장정환,Chang. Jung-Hwan
- ㆍ 간행물명
- 정보처리학회논문지. The KIPS transactions. Part A. Part A
- ㆍ 권/호정보
- 2006년|3호|pp.253-260 (8 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
본 논문에서는 피라미드 그래프에서의 헤밀톤 사이클 특성을 분석한다. 사이클 확장 연산을 이용하여 사이클의 크기를 확대시켜 나가는 일련의 과정을 통하여 헤밀톤 사이클을 찾을 수 있는 제시된 알고리즘을 적용함으로써 임의의 높이 N인 피라미드 그래프 내에 길이 $(4^N-1)/3$인 헤밀톤 사이클이 존재함을 증명한다.
In this paper, we analyze the Hamiltonian property of Pyramid graphs. We prove that it is always possible to construct a Hamiltonian cycle of length $(4^N-1)/3$ by applying the proposed algorithm to construct series of cycle expansion operations into two adjacent cycles in the Pyramid graph of height N.