팬케이크 그래프

팬케이크 그래프
팬케이크 그래프 P는4 각 카피에 접미사로 {1, 2, 3, 4} 세트와 다른 요소를 할당하여 4장의3 P 복사본에서 반복적으로 구성할 수 있다.
정점	${\displaystyle n!}$
가장자리	${\displaystyle {\dfrac{1}{2}}~n!\왼쪽(n-1\오른쪽)}$
둘레	6, n > 2일 경우
색수	글에서 보다
색도 지수	n − 1
속	글에서 보다
특성.	정규 해밀턴어 케이리 정점 변환 최대 연결 초연결 초연결
표기법	Pn
그래프 및 모수 표

그래프 이론의 수학적 분야에서, 팬케이크 그래프_n P 또는 n 팬케이크 그래프는 정점이 1에서 n까지의 n 기호의 순열이고 그것의 가장자리는 접두사 역순으로 전이되는 순열 사이에 주어지는 그래프다.

팬케이크 구분은 주걱을 스택의 어느 지점에서든 삽입할 수 있고 그 위에 있는 모든 팬케이크를 뒤집는 데 사용될 수 있을 때 크기순으로 팬케이크를 정렬하는 수학적인 문제를 나타내는 구어체 용어다.팬케이크 번호는 주어진 팬케이크 수에 필요한 최소 플립 수입니다.팬케이크 번호를 얻는 것은 팬케이크 그래프의 직경을 얻는 문제와 맞먹는다.^[1]

치수_n n, P의 팬케이크 그래프는 $!$ {\$displaystyle$ n$!}$ 정점을$$ 갖는 정규 그래프다.그것의 정도는 n - 1이므로, 악수하는 보조정리법에 $따르면{\displaystyle {\displaystyle \frac{\mathrm{}}{}}}$, ${\displaystyle {\displaystyle \frac{1}{}}2{\displaystyle }}$n !${\displaystyle }$( ${\displaystyle n}$ - ${\displaystyle 1}$) ${\$1}{2}}~$n!$$\왼쪽(n-1$\오른쪽)$가장자리.$P는_n 각 복사본에 접미사로 {1, 2, …, n} 세트와 다른 요소를 할당하여 P 복사본_n−1 n개에서 반복적으로 구성할 수 있다.

결과.

P_n(n ≥ 4)는 초연결, 초연결이다.^[2]

그들의^[3] 둘레는

${\displaystyle g(P_{n}}=6,{\text{{{}}, }n>2인 경우.}$

P의_n γ(P_n) 속은 다음과 같다.^[4]

${\displaystyle n!\왼쪽({\frac {n-4}{6}\오른쪽)+1\leq \gamma(P_{n}\leq n!\왼쪽({\frac {n-3}{4}\오른쪽)-{\frac}{n}{n}}:{2}}+1+1}$

색채 특성

팬케이크 그래프의 알려진 그래프 색소 특성이 있다.

P_n (n ≥ 3) 팬케이크 그래프는 총 색수 $\chi {\displaystyle {}_{}}$ ${\displaystyle t_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$)${\displaystyle }$= ${\displaystyle n}$ ${\displaystyle \chi _{t}($${\displaystyle {}_{}}$${n}=n}),$색지수 $\chi {\displaystyle {}_{}}$ e (${\displaystyle {}_{}{P}_{}}$ ${\displaystyle n_{}}$)${\displaystyle }$= ${\displaystyle n}$- ${\displaystyle 1}$ ${\displaystyle \chi _{e}(P_{n}=n-1$^[5]

팬케이크 그래프의 적절한 (n-1)-색상과 총 n-색상을 위한 효과적인 알고리즘이 있다.^[5]

$\chi {\displaystyle ({Pn}_{}}$) ${\displaystyle \chi(P_{n})$ 색상의$$ 숫자에 대해 다음과 같은 한계가 알려져 있다.

$4{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle n}$ ${\displaystyle \le }$ ${\displaystyle 8}$ ${\displaystyle 4\leq$ n$\leq 8}$인 경우$,$

${\displaystyle \chi(P_{n})\leq {\begin}n-k,&{\text{}}}n\pmod{4},k=1,3;\n-2,&\text{}}}{\text}}}}n\pmod{4}},k=0,2;end{case}}}}$

$만약{\displaystyle \mathrm{}}$ 9 ${\displaystyle \le n}$ ${\displaystyle \le }$ ${\displaystyle 16}$ ${\displaystyle 9\leq$ n$\leq 16}$이면$,$

${\displaystyle \chi(P_{n})\leq {\begin}n-(k+2)-&#text{{n\pmod{4},k=1,3;\n-4,&\text{{}}}}}},k=0,2;\case{case}}}}}}}}$

$n{\displaystyle }$ ${\displaystyle 17}$ {\$displaystyle n\geq 17}$인 경우$,$

${\displaystyle \chi (P_{n})\leq {\begin}n-(k+4)-{\text{n\pmod{4},k=1,2,3;\n-8,&\text{}}}}}}}}}}{\text{}n\pmod{4},k=0.\end{case}}}$

다음 표에서는 일부 소 n에 대한 특정 색수 값을 설명한다.

색수의 특정 값 또는 가능한 값

${\displaystyle n}$	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle \chi(P_{n})}$	2	3	3	4	4	4?	4?	4?	4?	4?	4?	4?	4?	4?

사이클 열거

P_n(n ≥ 3) 팬케이크 그래프에는 $6{\displaystyle \mathrm{}}$length ${\displaystyle \ell }$ ${\displaystyle \le }$ ${\displaystyle n}$! ${\displaystyle 6\leq \ell \leq n!}($그러나 길이 3, 4, 5의 사이클은 없다).^[6]이것은 그래프가 해밀턴식이고 어떤 두 꼭지점이 해밀턴식 경로로 결합될 수 있다는 것을 암시한다.

P_n (n ≥ 4) 팬케이크 그래프의 6 사이클에 대하여: 모든 꼭지점은 정확히 하나의 6 사이클에 속한다.${\displaystyle \frac{}{}}$에는 $n{\displaystyle \frac{!}{}}$ 6 ${\$$}{6}}}$ 독립형$$( (x-분리)^[7] 6주기

P_n(n ≥ 4) 팬케이크 그래프의 7주기 정보: 모든 꼭지점은 $7{\displaystyle \mathrm{}}$ ${\displaystyle \cdot }$(${\displaystyle n}$-${\displaystyle 3}$ )$${\$displaystyle 7\cdot (n-3)$7-cyle에$$ 속한다.그래프에는 $n{\displaystyle }$ !${\displaystyle \cdot }$(${\displaystyle \mathrm{n}}$- 3$){\displaystyle$ n$!\cdot (n-3)}$개의$$ 서로 다른 7-cycle이 포함되어 있다.^[8]

About the 8-cycles of the P_n (n ≥ 4) pancake graph: the graph contains ${\displaystyle {\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}}$ different 8-cycles; a maximal set of independent 8-cycles contains ${\displaystyle {\frac {n!$$}{8$$}}}.$^[7]

지름

팬케이크 분류 문제(팬케이크 번호 표시)와 팬케이크 그래프의 직경을 구하는 것은 동등하다.이 문제를 해결하는 데 있어 가장 큰 어려움 중 하나는 팬케이크 그래프의 복잡한 사이클 구조다.

팬케이크 번호
(OEIS에서 시퀀스 A058986)

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
${\displaystyle P_{n}}$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

대칭의 최소 숫자와 팬 케이크의 스택 정리하는 데 필요한 팬 케이크 번호,.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-o 사이에 있는 것으로 나타났다.Utput.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}15/14n과 18/11n(대략 1.07n과 1.64n,)지만 정확한 가치는 여전히 개방 문제이다.[9]

1979년 빌 게이츠와 크리스토스 파파디미트리오가^[10] 5/3n의 상한을 부여했다.이는 창립자 할 수드버러^[11] 교수(Chitturi et al., 2009^[12])가 이끄는 댈러스 텍사스 대학교 연구팀에 의해 30년 후 18/11n으로 개선되었다.

2011년, Laurent Bulteau, Guillaume Pertin, Irena Russu는^[13] 주어진 팬케이크 스택에 대한 최단 순서의 플립을 찾는 문제가 NP-hard라는 것을 증명하여, 30년 넘게 열려온 질문에 대답하였다.

탄 팬케이크 그래프

불에 탄 팬케이크 문제라는 변형에서, 더미의 각 팬케이크 바닥은 불에 탔으며, 모든 팬케이크의 불에 탄 면을 아래로 한 채 분류가 완료되어야 한다.서명한 순열로 팬케이크에 불이 붙으면 음의 요소를 대신해서 순열한다.불에 탄 팬케이크 그래프는 이 문제를 그래프로 나타낸 것이다.

P $′{\$ 연소된$$ 팬케이크 그래프는 규칙적이며, 순서는 ${\displaystyle {2n}^{}}$ ${\displaystyle {}^{}n!}$ ${\displaystyle 2^{n}\cdot n!}$이고$,$ $정도$는 n$${\$displaystyn}$이다$.$

그것의 변종인 David S를 위해서.코헨(데이비드 X. 코헨)과 마누엘 블럼은 1995년에 ${\displaystyle \mathrm{3n}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \le }$ P ${\displaystyle n_{}^{}}$ ${\displaystyle \prime }$ ${\displaystyle \mathrm{2n}}$- ${\displaystyle 2}$ $(\displaystyle 3n/2\leq P'_{n}\leq 2n-2}$ $$(> ${\displaysty n>9}$의 경우에만 상한선이 참인 경우)을 증명했다.^[14]

불에 탄 팬케이크 번호
(OEIS에서 시퀀스 A078941)

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12
${\displaystyle P'_{n}}$	1	4	6	8	10	12	14	15	17	18	19	21

불에 탄 팬케이크 그래프의 둘레는 다음과 같다.^[3]

${\displaystyle g(P_{n}}=8{\text{, }}.}$

팬케이크 그래프의 기타 클래스

원래 팬케이크 분류 문제와 불에 탄 팬케이크 문제 둘 다 접두사 반전이 두 순열을 연결하는 작업이었다.만약 우리가 (하나 대신에 두 개의 주걱으로 뒤집듯이) 미확정 반전을 허용한다면, 네 가지 등급의 팬케이크 그래프를 정의할 수 있다.모든 팬케이크 그래프는 같은 계열의 모든 고차 팬케이크 그래프에 포함되어 있다.^[3]

팬케이크 그래프 클래스

이름	표기법	설명	주문	정도	둘레 (만약 n>2)
부호 없는 접두사 반전 그래프	${\displaystyle UP_{n}}$	팬케이크 원본 정렬 문제	${\displaystyle n!}$	${\displaystyle n-1}$	${\displaystyle 6}$
부호 없는 반전 그래프	${\displaystyle UR_{n}}$	두 개의 주걱이 원래 문제	${\displaystyle n!}$	${\displaystyle{n \선택 {{}}}}$	$(\displaystyle 4}$
부호 접두사 반전 그래프	${\displaystyle SP_{n}}$	불에 탄 팬케이크 문제	${\displaystyle 2^{n}\cdot n!}$	${\displaystyle n}$	${\displaystyle 8}$
부호 반전 그래프	${\displaystyle SR_{n}}$	주걱 두 개가 탄 팬케이크 문제	${\displaystyle 2^{n}\cdot n!}$	${\displaystyle {n+1} \선택 사항 2.}$	$(\displaystyle 4}$

적용들

이후 팬 케이크 그래프고, 비교적 드문드문(예에. hypercubes 비해)과 재귀적 대칭 구조,(그들은 케일리 그래프, 따라서vertex-transitive 있)sublogarithmic도 하고 지름 같은 많은 흥미로운 특성을 가지고 있고, 많은 관심을 그들에게 상호 연결 네트워크의 병렬 컴퓨터를 위한 모델로 지급된다.[4][15][16][17]팬케이크 그래프를 상호연결망의 모델로 간주할 때, 그래프의 지름은 통신 지연을 나타내는 척도다.^[18][19]

팬케이크 플립은 유전자 검사 분야에서도 생물학적 응용이 있다.한 종류의 대규모 돌연변이에서는 게놈의 큰 부분이 역전되는데, 이는 불에 탄 팬케이크 문제와 유사하다.

참조