팬케익 그래프와 하프 팬케익 그래프에서 해밀턴 특성 분석

Analysis the Hamilton attribute in Half Pancake Graph and Pancake Graph

팬케익 문제는 크기가 모두 다른 다수의 팬케익을 접시에 쌓는 문제이다. 이때 크기가 작은 팬케익은 자신보다 큰 팬케익보다 위에 위치해야 한다. 팬케익 그래프는 n개의 크기가 서로 다른 팬케익 문제에서 출발했다. n-팬케익 그래프는 n!개의 노드를 가진다. 노드는 n개의 자연수로 된 순열로 이루어져 있다. 노드는 임의의 심볼에서부터 최상의 심볼까지 모두 뒤집는 것이 가능하다. 하프 팬케익 그래프와 팬케익 그래프는 스타그래프 부류의 연결망으로 노드수 n!을 갖는다. 하프 팬케익 그래프의 분지수는 팬케익 그래프의 분지수를 절반으로 줄인 약 n/2이다. 하프팬케익은 분지수×지름인 망 비용 측면에서 스타 그래프나 팬케익 그래프보다 향상된 결과를 갖는다. 해밀턴 특성은 고장 하용 라우팅 알고리즘, 다대다 방송, 일대다 방송, 데이터 이동 등 다영한 알고리즘에서 이용되는 기초 알고리즘이다. 본 논문에서는 팬케익 그래프와 하프 팬케익 그래프의 경로 특성을 분석하고 그 결과를 이용하여 팬케익 그래프와 하프 팬케익 그래프의 해밀턴 특성을 도출한다.

The pancake problem is the problem of stacking a large number of different sized pancakes on a plate. At this time, the smaller pancakes should be above the larger pancakes. The pancake graph originated from the problem of pancakes with n different sizes. The n-pancake graph has n! nodes. A node consists of a permutation of n natural numbers. It is possible for a node to flip from any symbol up to the top symbol. The half pancake graph and the pancake graph have a node number n! In the half pancake graph, The degree of the half pancake graph is about n/2 which reduces the degree of the pancake graph by half. Half pancakes have better results than star graphs or pancake graphs in terms of network cost, which is the degree×diameter. Hamiltonian characteristics are the basic algorithms used in multiprocessor algorithms such as fault tolerant routing algorithms, all-to-all broadcasting, one-to-all broadcasting, and data migration. In this paper, we analyze the path characteristics of a pancake graph and a half pancake graph, and derive Hamilton characteristics of a pancake graph and a half pancake graph using the results.