(n,k)-스타 그래프의 사이클 특성

장정환,Chang, Jung-Hwan 한국정보처리학회 2000 정보처리논문지 Vol.7 No.5

In this paper, we analyze the cycle property of the (n,k)-star graph that has an attention as an alternative interconnection network topology in recent years. Based on the graph-theoretic properties in (n,k)-star graphs, we show the pancyclic property of the graph and also present the corresponding algorithm. Based on the recursive structure of the graph, we present such top-down approach that the resulting cycle can be constructed by applying series of "dimension expansion" operations to a kind of cycles consisting of sub-graphs. This processing naturally leads to such property that the resulting cycles tend to be integrated compactly within some minimal subset of sub-graphs, and also means its applicability of another classes of the disjoint-style cycle problems. This result means not only the graph-theoretic contribution of analyzing the pancyclic property in the underlying graph model but also the parallel processing applications such a as message routing or resource allocation and scheduling in the multi-computer system with the corresponding interconnection network. 본 논문에서는 최근 상호연결망 위상으로 관심을 받고 있는 (n,k)-스티 그래프에 대한 사이클 특성을 분석한다.(n,k)-스티 그래프의 그래프 이론적 특성을 바탕으로 (n,k)-스티 그래프가 다양한 종류의 사이클들을 보유하고있는 범사이클(pancyclic)특성을 지니고 있음을 밝히고 해당 사이클들을 찾을 수 있는 알고리즘을 제시한다. 본 논문에서제안하고 있는 기법은 그래프자체의 체귀적 성질을 이용한 하형식(top-down)방식으로써 부-그래프들로 구성된 확장된 개념의 사이클들에 "차원확장"이라는 연산을 연속적으로 적용함으로써 원하는 사이클로 구체화해 가는 과정으로 진행하게 된다. 이러한 기법의 적용 결과 구성되는 사이클은 최소한의 한정된 부-그래프들로 밀집되어 모이는 경향이 있어 노드 또는 예지심에 서로 중복이 없이 독립된(disjoint) 사이클을 찾는 문제 등의 응용분야로 확대적용의 가능성이 있다. 본 연구 결과는 (n,k)-스티 그래프에 대한 그래프 이론적 관점에서의 댐사이클 특성을 분석한 이론적 의미와 더불어 해당 상호연결망 구조를 갖는 다중컴퓨터시스템에서의 메시지 라우팅이나 자원 할당 및 스케쥴링과 관련된 분야로의 응용가능성을 함께 의미하고 있다.

결함 노드를 갖는 (n,K)-스타 그래프에서의 링 임베딩

장정환,김진수,Chang, Jung-Hwan,Kim, Jin-Soo 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.1

본 논문에서는 최근에 제안된 (n,K)-스타 그래프에서 결함 노드를 포함하는 경우의 링 임베딩 문제를 다룬다. 그래프 자체의 계층적 특성을 이용한 일련의 차원 확장 및 결함 노드의 분산 전략 을 효율적으로 이용하여 n-3개의 이하의 결함 노드만을 포함하고, $n-k{\geq}2$를 만족한는(n.k)-스타 그래프에서 고장 노드들만 제외시킨 최대 크기의 링을 임베딩할 수 있음을 보이고해당 임베딩 알고리즘을 제시한다. 본 논문에서 다루고 있는 사이클 특성과 관련된 림 임베딩 연구는 병렬 처리 분야에서의 멀티캐스팅 등 과 같이 내재된 사이클 특성을 활용하는 분야에 응용이 가능하다. In this paper, we consider ring embeding problem in faulty (n,k) star graphs which is recently proposed as an alternative interconnection network topology, By effectively utilizing such strategies as series of dimension expansions and even distribution of faulty nodes into sub-stars in graph itself. we prove that it is possible to construct a maximal fault-free ring excluding only faulty nodes when the number of faults is no more than n-3 and $n-k{\geq}2$, and also propose an algorithm which can embed the corresponding ring in (n.k)-star graphs This results will be applied into the multicasting applications that the underlying cycle properties on the multi-computer system.

피라미드의 3-차원 메쉬로의 신장율 개선 임베딩

장정환,Chang, Jung-Hwan 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.6

본 논문에서는 주어진 손님 그래프 모델의 정점들과 간선들을 신장율, 혼잡율 등의 성능 파라미터들을 보다 우수하게 유지하면서 주인 그래프의 대응되는 정점들 및 경로들오 매핑시키는 "그래프 임베딩 문제"라고 불리는 그래프이론 문제를 다른다. 먼저 높이가 N인 파라미트 모델을 높이가 $(4^{(N+1)/3}+2)/3$ 이고 2-차원 정방현 메쉬의 한 변의 길이가 $2^{(2N-1)/3}$인 3-차원 메쉬 구조의 대규모 병렬처리시스템으로 임베딩 할 수 잇는 새로운 매핑함수를 제안하고, 해당 임베딩 하에서 인접된 두 정점들 상호간 통신에 필요한 단계의 수를 반영하는 신장율의 관점에서 성능을 분석한다. 본 임베딩의 신장율이 $2{\cdot}4^{(N-2)/3}+4)/3$ 임을 증명한다. 이러한 결과는 동일한 조건 하에서 기존의 결과인 $4^{N+183}+2)/3$ 보다 우수한 것이다.다 우수한 것이다. In this paper, we consider a graph-theoretic problem,, the so-called "graph embedding problem" that maps the vertices and edges of the given guest graph model into the corresponding vertices and paths of the host graph under the condition of maintaining better performance parameters such as dilation, congestion, and expansion. We firstly propose a new mapping function which can embed the pyramid model with height N into the 3-dimensional mesh massively parallel processor system with the height $(4^{(N+1)/3}+2)/3$ and the regular 2-dimensional mesh of one side $2^{(2N-1)/3}$, and analyze the performance of the embedding in terms of the dilation parameter that reflects the number of communication steps between two adjacent vertices under the embedding. We prove that the dilation of the embedding is $2{\cdot}4^{(N-2)/3}+4)/3$. This is superior to the previous result of $4^{N+183}+2)/3$ under the same condition.condition.

원전용 비상디젤발전기 국외 손상사례 분석에 관한 연구

장정환,김진성,정해동,조권회,Chang, Jung-Hwan,Kim, Jin-Sung,Chung, Hae-Dong,Cho, Kwon-Hae 한국압력기기공학회 2009 한국압력기기공학회 논문집 Vol.5 No.1

The emergency diesel generator (EDG) in a nuclear power plant (NPP) shall start within 10 secondss and supply electrical power to engineered safety features within one minute and less if a loss of offsite power (LOOP), A design-basis event, or their combination occur. Each NPP has an EDG set consisting of two diesel generators for redundancy. In addition to the EDG set, an alternate Alternating Current Diesel Generator (AAC DG) is installed and shared by several units to cope with a station black out (SBO), i.e., loss of the offsite power concurrent with reactor trip and unavailability of the EDG set. The objective of this study is to analyze the failure data of emergency diesel generators reported in overseas nuclear power plants.

피라미드 그래프의 헤밀톤 특성

장정환,Chang Jung-Hwan 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.3

본 논문에서는 피라미드 그래프에서의 헤밀톤 사이클 특성을 분석한다. 사이클 확장 연산을 이용하여 사이클의 크기를 확대시켜 나가는 일련의 과정을 통하여 헤밀톤 사이클을 찾을 수 있는 제시된 알고리즘을 적용함으로써 임의의 높이 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.

강부재의 손상발견을 위한 모달실험 기법

장정환,이정휘,김성곤,장승필,Jang, Jeong Hwan,Lee, Jung Whee,Kim, Sung Kon,Chang, Sung Pil 한국강구조학회 1997 韓國鋼構造學會 論文集 Vol.9 No.4

모달실험 기법의 강부재 손상발견 적용성에 대한 실험적 연구를 수행하였다. 단경간 및 2경간 강재보에 손상을 모사한 단계적인 절단을 가하면서 모달실험을 반복하고, 손상 정도에 따른 모달 파라미터의 변화를 관찰하였으며, 실험 결과를 검증할 목적으로 수치해석을 병행하였다. 고려한 모달 파라미터는 고유진동수(Frequency), 변위 모드형상(Displacement Mode Shape), 변형률 모드형상(Strain Mode Shape)이며, 이들 모달 파라미터를 구하기 위하여 가속도계와 변형률계를 사용한 모달실험을 실시하였다. 각각의 손상단계에서 손상에 의한 변위 모드형상과 변형률 모드형상의 변화를 위치에 대해 정량적으로 나타내기 위하여, CoMAC과 Modal Vector Error를 사용하였다. 고유진동수는 손상의 정도가 심해짐에 따라 감소하는 경향을 보였으며, 손상의 위치를 발견하는 데에 가장 효과적으로 사용될 수 있는 것은 변형률 모드형상이었다. A series of experimental tests have been performed on a tube beam in which artificial damage is applied in order to address damage detectability using modal analysis. Modal parameters considered are frequency, displacement mode shape and strain mode shape CoMAC(Coordinate Modal Assurance Criterion) and Modal Vector Error have been adopted for presenting the change of displacement mode shape and strain mode shape. It is revealed strain mode shape is the most sensitive to damage.

피라미드 그래프의 범사이클 특성

장정환,Chang, Jung-Hwan 한국정보처리학회 2008 정보처리학회논문지 A Vol.15 No.2

In this paper, we analyze a cycle property embedded in pyramid graphs. We prove that it is always possible to construct diverse cycles of all lengths from 3 to ($4^N-1$)/3 by applying series of cycle expansion operations to the pyramid graph of height N. This means that the pyramid graph has the pancyclic property. 본 논문에서는 피라미드 그래프 내에 내재된 사이클 특성을 분석한다. 높이 N의 피라미드 그래프에 연속적인 사이클 확장 연산을 적용함으로써 길이 3이상 ($4^N-1$)/3 까지에 해당하는 모든 길이의 다양한 사이클들을 생성할 수 있음을 증명한다. 이는 피라미드 그래프가 범사이클 특성을 보유하고 있음을 의미한다.

사구 슬롯이 있는 콘덴서 구동형 단상 유도전동기의 Radial Force Density 해석

張正煥(Jung-Hwan Chang),尹相伯(Sang-Baeck Yoon),玄東石(Dong-Seok Hyun) 대한전기학회 1998 전기학회논문지 Vol.47 No.3

피라미드 그래프로의 링 임베딩

장정환 ( Jung-hwan Chang ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.2

본 논문에서는 피라미드 그래프를 대상으로 링을 임베딩하는 문제를 다룬다. 사이클 확장 연산을 이용하여 사이클의 크기를 확대시켜 나가는 일련의 과정을 통하여 최대 크기의 링을 의미하는 헤밀톤 사이클을 찾을 수 있는 알고리즘을 제시함으로써 임의의 높이 N인 피라미드 그래프 내에 길이 4^N-1/3 인 링을 임베딩 할 수 있음을 증명한다.

피라미드 상호연결망의 기반 그래프로서의 2ⁿ-정방형 메쉬 그래프의 간선 특성

장정환(Jung-Hwan Chang) 한국콘텐츠학회 2009 한국콘텐츠학회논문지 Vol.9 No.12

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