Palačinkový graf - Pancake graph - Wikipedia

Palačinkový graf
Graf lívance P4 lze konstruovat rekurzivně ze 4 kopií P3 přiřazením jiného prvku ze sady {1, 2, 3, 4} jako přípony ke každé kopii.
Vrcholy	${ displaystyle n!}$
Hrany	${ displaystyle { dfrac {1} {2}} ~ n! vlevo (n-1 vpravo)}$
Obvod	6, pokud n > 2
Chromatické číslo	viz v článku
Chromatický index	n − 1
Rod	viz v článku
Vlastnosti	Pravidelný Hamiltonian Cayley Vrchol-tranzitivní Maximálně připojeno Super propojený Hyper propojený
Zápis	Pn
Tabulka grafů a parametrů

V matematický pole teorie grafů, lívancový graf P_n nebo n-pancake graf je graf, jehož vrcholy jsou permutacemi n symboly od 1 do n a jeho okraje jsou uvedeny mezi permutacemi přechodnými zvrácením předpony.

Třídění palačinek je hovorový výraz pro matematický problém třídění neuspořádaného stohu palačinky v pořadí podle velikosti, když a špachtle lze vložit do libovolného bodu v zásobníku a použít k překlopení všech palačinek nad ním. A číslo palačinky je minimální počet otočení požadovaný pro daný počet palačinek. Získání čísla palačinky je ekvivalentní problému získání průměr lívancového grafu.^[1]

Palačinkový graf dimenze n, P_n, je běžný graf s ${ displaystyle n!}$ vrcholy. Jeho stupeň je n - 1, tedy podle handmaking lemma, má to ${ displaystyle { dfrac {1} {2}} ~ n! vlevo (n-1 vpravo)}$ hrany. P_n lze sestavit rekurzivně z n kopií P_n−1, přiřazením jiného prvku ze sady {1, 2,…, n} jako přípona ke každé kopii.

Výsledek

P_n (n ≥ 4) je super propojený a velmi propojený.^[2]

Jejich obvod je^[3]

${ displaystyle g (P_ {n}) = 6, { text {if}} n> 2.}$

Γ (P_n) rod z P_n je:^[4]

${ displaystyle n! left ({ frac {n-4} {6}} right) +1 leq gamma (P_ {n}) leq n! left ({ frac {n-3} {4}} right) - { frac {n} {2}} + 1.}$

Chromatické vlastnosti

Některé jsou známé zbarvení grafu vlastnosti palačinkových grafů.

A P_n (n ≥ 3) palačinkový graf má celkové chromatické číslo ${ displaystyle chi _ {t} (P_ {n}) = n}$, chromatický index ${ displaystyle chi _ {e} (P_ {n}) = n-1}$.^[5]

Existují účinné algoritmy pro správné (n − 1) barvení a součet n-barvení grafů palačinky.^[5]

Pro ${ displaystyle chi (P_ {n})}$ chromatické číslo jsou známy následující limity:

Li ${ displaystyle 4 leq n leq 8}$, pak

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

-li ${ displaystyle 9 leq n leq 16}$, pak

${ displaystyle chi (P_ {n}) leq { začátek {případy} n- (k + 2), & { text {if}} n equiv k { pmod {4}}, k = 1 , 3; n-4, & { text {if}} n equiv k { pmod {4}}, k = 0,2; end {případy}}}$

-li ${ displaystyle n geq 17}$, pak

${ displaystyle chi (P_ {n}) leq { začátek {případy} n- (k + 4), & { text {if}} n equiv k { pmod {4}}, k = 1 , 2,3; n-8, & { text {if}} n equiv k { pmod {4}}, k = 0. End {cases}}}$

Následující tabulka pojednává o konkrétních hodnotách chromatického čísla pro některé malé n.

Konkrétní nebo pravděpodobné hodnoty chromatického čísla

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

Výčet cyklu

V P_n (n ≥ 3) palačinkový graf vždy existuje alespoň jeden cyklus délky ℓ, když ${ Displaystyle 6 leq ell leq n!}$ (ale neexistují žádné cykly o délce 3, 4 nebo 5).^[6] To znamená, že graf je Hamiltonian a libovolné dva vrcholy mohou být spojeny hamiltonovskou cestou.

O 6 cyklech P_n (n ≥ 4) pancake graph: každý vrchol patří přesně do jednoho 6-cyklu. Graf obsahuje ${ displaystyle { frac {n!} {6}}}$ nezávislé (vrchol-disjunktní) 6 cyklů.^[7]

O 7 cyklech P_n (n ≥ 4) pancake graph: každý vrchol patří ${ displaystyle 7 cdot (n-3)}$ 7-cyklů. Graf obsahuje ${ displaystyle n! cdot (n-3)}$ různých 7 cyklů.^[8]

O 8 cyklech P_n (n ≥ 4) pancake graph: graf obsahuje ${ displaystyle { frac {n! (n ^ {3} + 12n ^ {2} -103n + 176)} {16}}}$ různé 8 cykly; obsahuje maximální sada nezávislých 8 cyklů ${ displaystyle { frac {n!} {8}}}$ z těch.^[7]

Průměr

Problém třídění palačinek (získání čísla palačinky) a získání průměru grafu palačinky jsou ekvivalenty. Jednou z hlavních obtíží při řešení tohoto problému je složitost cyklus struktura grafu palačinky.

Čísla palačinek
(sekvence A058986 v 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

Číslo palačinky, což je minimální počet otočení potřebný k seřazení libovolného stohu n Bylo prokázáno, že mezi nimi leží palačinky 15/14n a 18/11n (přibližně 1,07n a 1,64n,), ale přesná hodnota zůstává otevřeným problémem.^[9]

V roce 1979 Bill Gates a Christos Papadimitriou^[10] dal horní hranici 5/3n. Toto bylo o třicet let později vylepšeno na 18/11n týmem výzkumníků na University of Texas v Dallasu, vedená profesorem zakladatelů Hal Sudborough^[11] (Chitturi et al., 2009^[12]).

V roce 2011 Laurent Bulteau, Guillaume Fertin a Irena Rusu^[13] dokázal, že problém najít nejkratší sekvenci převrácení pro danou hromádku palačinek je NP-těžký, čímž odpověděl na otázku, která byla otevřená více než tři desetiletí.

Spálený palačinkový graf

Ve variantě zvané problém spálené palačinky, spodní část každé palačinky na hromádce je spálená a druh musí být dokončen spálenou stranou každé palačinky dolů. Je to podepsaná permutace, a pokud palačinka i je „spálená strana nahoru“ negativní prvek já` je nahrazen i v permutaci. The spálený palačinkový graf je grafická reprezentace tohoto problému.

A ${ displaystyle P '_ {n}}$ graf spálené palačinky je pravidelný, jeho pořadí je ${ displaystyle 2 ^ {n} cdot n!}$, jeho stupeň je ${ displaystyle n}$.

Pro jeho variantu David S. Cohen (David X. Cohen ) a Manuel Blum v roce 1995 to prokázal ${ displaystyle 3n / 2 leq P '_ {n} leq 2n-2}$ (když je horní limit pravdivý pouze pokud ${ displaystyle n> 9}$).^[14]

Spálená čísla palačinek
(sekvence A078941 v 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

Obvod grafu spálené palačinky je:^[3]

${ displaystyle g (P_ {n}) = 8 { text {, pokud}} n> 2.}$

Další třídy grafů palačinek

Jak v původním problému s tříděním palačinek, tak v problému spálené palačinky, obrácení předpony byla operace spojující dvě permutace. Pokud povolíme nepředpony zvratů (jako kdybychom převraceli dvě špachtle místo jedné), pak lze definovat čtyři třídy grafů palačinky. Každý graf palačinky je vložen do všech grafů palačinek vyššího řádu stejné rodiny.^[3]

Třídy palačinkových grafů

název	Zápis	Vysvětlení	Objednat	Stupeň	Obvod (pokud n> 2)
graf obrácení nepodepsané předpony	${ displaystyle UP_ {n}}$	Původní problém s tříděním palačinek	${ displaystyle n!}$	${ displaystyle n-1}$	${ displaystyle 6}$
nepodepsaný reverzní graf	${ displaystyle UR_ {n}}$	Původní problém se dvěma stěrkami	${ displaystyle n!}$	${ displaystyle {n vyberte 2}}$	${ displaystyle 4}$
podepsaný prefix obrácení grafu	${ displaystyle SP_ {n}}$	Problém se spálenou palačinkou	${ displaystyle 2 ^ {n} cdot n!}$	${ displaystyle n}$	${ displaystyle 8}$
podepsaný obrácený graf	${ displaystyle SR_ {n}}$	Problém se spálenou palačinkou se dvěma stěrkami	${ displaystyle 2 ^ {n} cdot n!}$	${ displaystyle {n + 1 vyberte 2}}$	${ displaystyle 4}$

Aplikace

Protože palačinkové grafy mají mnoho zajímavých vlastností, jako jsou symetrické a rekurzivní struktury (jsou Cayleyovy grafy, tak jsou vrchol-tranzitivní ), sublogaritmický stupeň a průměr, a jsou relativně řídký (ve srovnání např. hyperkrychle ), je jim věnována velká pozornost jako modelu propojovacích sítí pro paralelní počítače.^{[4][15][16][17]} Když považujeme palačinkové grafy za model propojovacích sítí, je průměr grafu mírou, která představuje zpoždění komunikace.^[18][19]

Překlopení palačinky má biologické aplikace také v oblasti genetických vyšetření. V jednom druhu rozsáhlých mutací dojde k obrácení velké části genomu, což je analogické problému spálené palačinky.

Reference