피라미드 상호연결망의 기반 그래프로서의 2ⁿ-정방형 메쉬 그래프의 간선 특성 (Edge Property of 2ⁿ-square Meshes as a Base Graphs of Pyramid Interconnection Networks)

서지정보

· 발행기관 : 한국콘텐츠학회
· 수록지 정보 : 한국콘텐츠학회 논문지 / 9권 / 12호 / 582 ~ 591페이지
· 저자명 : 장정환

초록

피라미드 그래프는 정방형 메쉬와 트리 구조를 기반으로 하는 상호연결망 토폴로지이다. 본 논문에서는 피라미드 그래프의 각 계층을 구성하고 있는 기반 그래프로서의 정방형 메쉬 그래프의 간선들을 두 개의 서로 다른 그룹으로 분류하는 전략을 채택한다. 메쉬 내의 간선 집합은 해당 간선의 양 끝 정점들에 인접된 부모 정점들이 상위 계층 내에서 서로 이웃하는 관계인지 아니면 공유하는 관계인지에 따라서 각각 NPC-간선과 SPC-간선이라는 이름으로 불리는 두 개의 서로 다른 부분집합으로 나누어질 수 있다. 아울러 원래 그래프에서의 SPC-간선들을 압축된 결과 그래프에서는 압축된 슈퍼-정점 내부로 숨김으로써 NPC-간선들에만 초점을 맞출 수 있도록 하기 위해 압축 그래프의 개념을 소개한다. 본 논문에서는 2ⁿ×2ⁿ 2-차원 정방형 메쉬 내에서 헤밀톤 사이클 구성 시 포함할 수 있는 NPC-간선 개수의 하한 및 상한이 각각 22n-2와 3*(22n-2－2n-1)임을 분석한다. 이 결과를 피라미드 그래프로 확장시킴으로써 n-차원 피라미드 내에서 헤밀톤 사이클에 포함가능한 NPC-간선의 최대 개수가 4n-1-3*2n-1-2n+7 임을 증명한다.

영어초록

The pyramid graph is an interconnection network topology based on regular square mesh and tree structures. In this paper, we adopt a strategy of classification into two disjoint groups of edges in regular square mesh as a base sub-graph constituting of each layer in the pyramid graph. Edge set in the mesh can be divided into two disjoint sub-sets called as NPC(represents candidate edge for neighbor-parent) and SPC(represents candidate edge for shared-parent) whether the parents vertices adjacent to two end vertices of the corresponding edge have a relation of neighbor or shared in the upper layer of pyramid graph. In addition, we also introduce a notion of shrink graph to focus only on the NPC-edges by hiding SPC-edges in the original graph within the shrunk super-vertex on the resulting graph. In this paper, we analyze that the lower and upper bound on the number of NPC-edges in a Hamiltonian cycle constructed on 2ⁿ×2ⁿ mesh is 22n-2 and 3*(22n-2－2n-1) respectively. By expanding this result into the pyramid graph, we also prove that the maximum number of NPC-edges containable in a Hamiltonian cycle is 4n-1-3*2n-1-2n+7 in the n-dimensional pyramid.

참고자료

· 없음