Wykres naleśnikowy

Wykres naleśnikowy
Wykres naleśnikowy P 4 można zbudować rekurencyjnie z 4 kopii P 3 , przypisując do każdej kopii inny element ze zbioru {1, 2, 3, 4} jako sufiks.
Wierzchołki	${\ Displaystyle n!}$
Krawędzie	${\ Displaystyle {\ dfrac {1} {2}} ~ n! \ lewo (n-1 \ prawo)}$
Obwód	6, jeśli n > 2
Liczba chromatyczna	zobacz w artykule
Indeks chromatyczny	n -1
Rodzaj	zobacz w artykule
Nieruchomości	Regularny hamiltonian Cayley Vertex-przechodni Maksymalnie połączony Super połączony Hiper połączony
Notacja	Pn _
Tabela wykresów i parametrów

W matematycznej dziedzinie teorii grafów graf naleśnikowy Pn lub wykres n -naleśnikowy jest grafem, którego _wierzchołki są permutacjami n symboli od 1 do n , a jego krawędzie są podane między permutacjami przechodnimi przez odwrócenie przedrostków.

Sortowanie naleśników to potoczne określenie matematycznego problemu sortowania nieuporządkowanego stosu naleśników według wielkości, kiedy łopatkę można włożyć w dowolnym miejscu stosu i użyć do przewrócenia wszystkich naleśników znajdujących się nad nim. Liczba naleśników to minimalna liczba przewrotów wymaganych dla danej liczby naleśników. Uzyskanie liczby naleśników jest równoznaczne z problemem uzyskania średnicy wykresu naleśników.

Wykres naleśnikowy o wymiarze _n , Pn , jest wykresem regularnym z ${\ displaystyle n!}$ wierzchołki. Jego stopień wynosi n − 1, stąd zgodnie z lematem o uzgadnianiu , ma ${\ Displaystyle {\ dfrac {1} {2}} ~ n! \ lewo (n-1 \ prawo)}$ krawędzie. P _n można skonstruować rekurencyjnie z n kopii P _{n −1} , poprzez przypisanie do każdej kopii innego elementu ze zbioru {1, 2, …, n } jako sufiksu.

Wyniki

P _n ( n ≥ 4) jest super-połączony i hiper-połączony .

Ich obwód jest

${\ Displaystyle g (P_ {n}) = 6, {\ tekst {jeśli}} n> 2.}$

Rodzaj γ( P _n ) P _n to :

${\ Displaystyle n! \ lewo ({\ Frac {n-4} {6}} \ prawej) + 1 \ równoważnik \ gamma (P_ {n}) \ równoważnik n !\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1.}$

Właściwości chromatyczne

Istnieje kilka znanych właściwości kolorowania grafów grafów naleśnikowych.

ZA P _n ( n ≥ 3) wykres naleśnikowy ma całkowitą liczbę chromatyczną ${\ Displaystyle \ chi _ {t} (P_ {n}) = n}$ , indeks chromatyczny ${\ Displaystyle \ chi _ {e} (P_ {n}) = n-1}$ .

Istnieją skuteczne algorytmy właściwego (n-1)-koloryzacji i całkowitego n -kolorowania grafów naleśnikowych.

Dla liczby chromatycznej znane są następujące granice: ${\ Displaystyle \ chi (P_ {n})}$

Jeśli ${\ Displaystyle 4 \ równoważnik n \ równoważnik 8}$ , to

${\ Displaystyle \ chi (P_ {n}) \ równoważnik {\ rozpocząć {przypadki} nk, & {\ tekst {jeśli}} n \ równoważnik k {\ pmod {4}}, k = 1,3; \\n -2,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{przypadki}}}$

jeśli ${\ Displaystyle 9 \ równoważnik n \ równoważnik 16}$ , to

${\ Displaystyle \ chi (P_ {n}) \ równoważnik {\ rozpocząć {przypadki} n- (k + 2) i {\ tekst {jeśli}} n \ równoważnik k {\ pmod {4}}, k = 1 ,3;\\n-4,&{\text{if }}n\równoważnik k{\pmod {4}},k=0,2;\end{przypadki}}}$

jeśli ${\ Displaystyle n \ geq 17}$ , to

${\ Displaystyle \ chi (P_ {n}) \ równoważnik {\ rozpocząć {przypadki} n- (k + 4) i {\ tekst {jeśli}} n \ równoważnik k {\ pmod {4}}, k = 1 ,2,3;\\n-8,&{\text{if }}n\równoważnik k{\pmod {4}},k=0.\end{przypadki}}}$

W poniższej tabeli omówiono określone wartości liczb chromatycznych dla niektórych małych n .

Konkretne lub prawdopodobne wartości liczby chromatycznej

${\ 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?

Wyliczanie cykli

W grafie naleśnikowym P _n ( n ≥ 3) zawsze istnieje co najmniej jeden cykl o długości ℓ , gdy ${\ Displaystyle 6 \ równoważnik \ ell \ równoważnik n!}$ (ale nie ma cykli o długości 3, 4 lub 5). Oznacza to, że graf jest hamiltonowski i dowolne dwa wierzchołki mogą być połączone ścieżką hamiltonowską.

O 6-cyklach wykresu naleśnikowego P _n ( n ≥ 4): każdy wierzchołek należy do dokładnie jednego 6-cyklu. Wykres zawiera $niezależnych$ (rozłącznych wierzchołków) 6 cykli.

O 7 cyklach $wykresu naleśnikowego$ P _n ( n należy do 7 cylindrów Wykres zawiera ${\ Displaystyle n! \ cdot (n-3)}$ różne 7 cykli.

O 8 cyklach wykresu naleśnikowego P _n ( n ≥ 4): wykres zawiera ${\ Displaystyle {\ Frac {n! (n ^ {3} + 12n ^ {2} -103n + 176)} {16}}}$ różne 8 cykli; maksymalny zbiór niezależnych 8-cykli zawiera ${\ Displaystyle {\ Frac {n!} {8}}}$ z tych.

Średnica

Problem sortowania naleśników (uzyskanie liczby naleśników) i uzyskanie średnicy wykresu naleśników są równoważne. Jedną z głównych trudności w rozwiązaniu tego problemu jest skomplikowana cykliczna wykresu naleśnikowego.

Numery naleśników (sekwencja A058986 w OEIS )

${\ 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

1,07 że a 18/11 n liczba naleśników, która jest minimalną liczbą rzutów wymaganych do posortowania dowolnego stosu n ( , naleśników, mieści się między 15/14 w n n przybliżeniu i 1,64 n ) ale dokładna wartość pozostaje otwarta problem.

W 1979 roku Bill 5/3 n . Gates i Christos Papadimitriou podali górną granicę Zostało to poprawione trzydzieści lat później do 18/11 n University przez zespół naukowców z of Texas w Dallas , kierowany przez profesora założyciela Hala Sudborougha (Chitturi i in., 2009).

W 2011 roku Laurent Bulteau, Guillaume Fertin i Irena Rusu udowodnili, że problem znalezienia najkrótszej sekwencji przewrotów dla danego stosu naleśników jest NP-trudny, odpowiadając w ten sposób na pytanie, które było otwarte przez ponad trzy dekady.

Wykres spalonego naleśnika

W odmianie zwanej problemem spalonego naleśnika spód każdego naleśnika w stosie jest przypalony, a sortowanie musi zostać zakończone spaloną stroną każdego naleśnika w dół. Jest to permutacja ze znakiem i jeśli naleśnik i jest spaloną stroną do góry, w miejsce i w permutacji wstawiany jest element ujemny i` . Wykres spalonego naleśnika jest graficzną reprezentacją tego problemu.

ZA ${\ Displaystyle P'_ {n}}$ wykres spalonego naleśnika jest regularny , jego kolejność to ${\ Displaystyle 2 ^ {n} \ cdot n!}$ , jego stopień wynosi ${\ displaystyle n}$ .

Dla swojego wariantu David S. Cohen ( David X. Cohen ) i Manuel Blum udowodnili w 1995 r., Że ${\ Displaystyle 3n/2 \ równoważnik P'_ {n} \ równoważnik 2n-2}$ (gdy górna granica jest prawdziwa tylko wtedy, gdy ${\ displaystyle n> 9}$ ).

Spalone numery naleśników (sekwencja A078941 w OEIS )

${\ 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

Obwód wykresu spalonego naleśnika wynosi:

${\ Displaystyle g (P_ {n}) = 8 {\ tekst {jeśli}} n> 2.}$

Inne klasy grafów naleśnikowych

Zarówno w pierwotnym problemie sortowania naleśników, jak i problemie spalonego naleśnika, odwrócenie przedrostka było operacją łączącą dwie permutacje. Jeśli pozwolimy na odwrócenie bez prefiksu (jakbyśmy odwracali dwoma szpatułkami zamiast jednej), to można zdefiniować cztery klasy grafów naleśnikowych. Każdy graf naleśnikowy jest osadzony we wszystkich grafach naleśnikowych wyższego rzędu z tej samej rodziny.

Klasy grafów naleśnikowych

Nazwa	Notacja	Wyjaśnienie	Zamówienie	Stopień	Obwód (jeśli n>2)
wykres odwrócenia przedrostka bez znaku	${\ displaystyle UP_ {n}}$	Oryginalny problem z sortowaniem naleśników	${\ Displaystyle n!}$	${\ displaystyle n-1}$	${\ Displaystyle 6}$
niepodpisany wykres odwrócenia	${\ Displaystyle UR_ {n}}$	Oryginalny problem z dwoma szpatułkami	${\ Displaystyle n!}$	${\ Displaystyle {n \ wybierz 2}}$	${\ Displaystyle 4}$
podpisany wykres odwrócenia prefiksu	${\ Displaystyle SP_ {n}}$	Problem spalonego naleśnika	${\ Displaystyle 2 ^ {n} \ cdot n!}$	${\ displaystyle n}$	${\ Displaystyle 8}$
podpisany wykres odwrócenia	${\ displaystyle SR_ {n}}$	Problem spalonego naleśnika z dwiema szpatułkami	${\ Displaystyle 2 ^ {n} \ cdot n!}$	${\ Displaystyle {n + 1 \ wybierz 2}}$	${\ Displaystyle 4}$

Aplikacje

Ponieważ grafy naleśnikowe mają wiele interesujących właściwości, takich jak struktury symetryczne i rekurencyjne (są to grafy Cayleya , a więc są przechodnie przez wierzchołki ), stopień i średnicę sublogarytmiczną oraz są stosunkowo rzadkie (w porównaniu np. z hipersześcianami ), poświęca się im wiele uwagi jako model sieci połączeń dla komputerów równoległych. Kiedy traktujemy wykresy naleśnikowe jako model sieci połączeń międzysieciowych, średnica wykresu jest miarą reprezentującą opóźnienie komunikacji.

Przerzucanie naleśników ma również zastosowania biologiczne, w dziedzinie badań genetycznych. W jednym rodzaju mutacji na dużą skalę duży segment genomu ulega odwróceniu, co jest analogiczne do problemu spalonego naleśnika.