Palacsintagráf

Palacsintagráf
A P4 palacsintagráf rekurzívan előállítható a P3 4 kópiájából úgy, hogy az {1, 2, 3, 4} halmaz más-más elemét fűzzük hozzá az egyes kópiákhoz.
Csúcsok száma	n!
Élek száma	1/2 n!(n − 1)
Átmérő	lásd a cikkben
Derékbőség	6, ha n > 2
Kromatikus szám	lásd a cikkben
Élkromatikus szám	n − 1
Génusz	lásd a cikkben
Egyéb	reguláris, hamiltoni, Cayley-gráf, csúcstranzitív, nem éltranzitív, nem távolságtranzitív, maximálisan összefüggő, szuperösszefüggő, hiperösszefüggő
Jelölés	$P_{n}$

A matematika, azon belül a gráfelmélet területén egy P_n palacsintagráf, avagy n-palacsintagráf olyan egyszerű, irányítatlan, hurokmentes gráf, melynek csúcshalmaza az 1,2,...,n számok permutációinak (sorbaállításainak) halmaza. Két permutáció között akkor húzódik él, ha az egyik tranzitív módon átvihető a másikba egy kezdőszeletének megfordításával (prefix reversal).

A palacsintarendezés (pancake sorting) az a matematikai probléma, melynek során különböző méretű palacsintákból álló oszlopot nagyság szerinti sorba rendeznek oly módon, hogy az oszlopba bárhol beszúrható egy fordítólapát, és az összes fölötte lévő palacsinta megfordítható vele. A palacsintarendezési probléma és a palacsintagráf átmérőjének meghatározása egymással ekvivalens.

A P_n palacsintagráf reguláris, csúcsainak száma n!, fokszáma n − 1.

Az n méretű palacsintagráf, P_n rekurzívan előállítható a P_n−1 palacsintagráf n kópiájából oly módon, hogy az {1, 2, …, n} halmaz más-más elemét fűzzük hozzá az egyes kópiákhoz.

Eredmények

A P_n (n ≥ 4) palacsintagráf szuperösszefüggő és hiperösszefüggő.

A palacsintagráf girthparamétere:

$g(P_{n})=6{\text{, ha }}n>2.$

A P_n palacsintagráf γ(P_n) génuszáról elmondható, hogy:

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

Színezése

A palacsintagráfok színezésével kapcsolatban a következő eredmények ismertek.

A P_n (n ≥ 3) palacsintagráf totális kromatikus száma $\chi _{t}(P_{n})=n$, élkromatikus száma $\chi _{e}(P_{n})=n-1$.

A palacsintagráf (n−1)-színezésére és totális n-színezésére hatékony algoritmus ismert.

A $\chi (P_{n})$ kromatikus számra a következő korlátok adhatók:

Ha $4\leq n\leq 8$, akkor

$\chi (P_{n})\leq {\begin{cases}n-k,&{\mbox{ha }}n\equiv k{\pmod {4}},k=1,3;\\n-2,&{\mbox{ha }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}$

ha $9\leq n\leq 16$, akkor

$\chi (P_{n})\leq {\begin{cases}n-(k+2),&{\mbox{ha }}n\equiv k{\pmod {4}},k=1,3;\\n-4,&{\mbox{ha }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}$

ha $n\geq 17$, akkor

$\chi (P_{n})\leq {\begin{cases}n-(k+4),&{\mbox{ha }}n\equiv k{\pmod {4}},k=1,2,3;\\n-8,&{\mbox{ha }}n\equiv k{\pmod {4}},k=0.\end{cases}}$

A következő táblázat alacsony n-ekre a palacsintagráfok kromatikus számának konkrét értékeit tárgyalja.

A kromatikus szám konkrét, illetve valószínűsíthető értékei

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

Köreinek száma

A P_n (n ≥ 3) palacsintagráfban minden esetben található l hosszúságú kör, ahol $6\leq l\leq n!$ (de 3, 4 és 5 hosszúságú körök nem). Ebből az is következik, hogy a gráf rendelkezik Hamilton-körrel, és bármely két csúcsa összeköthető Hamilton-úttal.

A P_n (n ≥ 4) palacsintagráf 6 hosszúságú köreiről elmondható, hogy minden csúcs egyetlen 6-körbe tartozik, melyekből a gráf összesen ${\frac {n!}{6}}$ független (csúcsdiszjunkt) darabot tartalmaz.

A P_n (n ≥ 4) palacsintagráf 7 hosszúságú köreiről elmondható, hogy minden csúcs pontosan $7\cdot (n-3)$ 7 hosszúságú körbe tartozik, melyekből a gráf összesen $n!\cdot (n-3)$ különböző darabot tartalmaz.

A P_n (n ≥ 4) palacsintagráf 8 hosszúságú köreiről elmondható, hogy ezekből a gráf összesen ${\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}$ különböző darabot tartalmaz, melyekből maximálisan ${\frac {n!}{8}}$ független 8-kör választható ki.

Átmérője

A palacsintarendezési probléma és a palacsintagráf átmérőjének („palacsintaszám”) meghatározása egymással ekvivalens. A palacsintaszám meghatározásának egyik fő nehézsége a palacsintagráf komplikált körszerkezetében rejlik.

Palacsintaszámok
(A058986 sorozat az OEIS-ben)

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

A palacsintaszám, tehát az n palacsintát tartalmazó oszlop rendezéséhez mindig elégséges, minimális átfordítások száma ${\frac {15}{14}}n$ és ${\frac {18}{11}}n$ (kb. $1,07n$ és $1,64n$) között van, de a pontos érték nem ismert.

1979-ben Bill Gates és Christos Papadimitriou ${\frac {5}{3}}n$ felső korlátot igazolt. Ezt 30 évvel később ${\frac {18}{11}}n$-re javította a University of Texas at Dallas egyetem Hal Sudborough által vezetett kutatócsoportja. (Chitturi et al., 2009).

2011-ben Laurent Bulteau, Guillaume Fertin és Irena Rusu bebizonyították, hogy egy adott palacsintaoszlop rendezéséhez szükséges legrövidebb átfordítás-sorozat megtalálása NP-nehéz feladat.

Égetettpalacsinta-gráf

Az égetettpalacsinta-problémaként (burnt pancake problem) ismert változatban a palacsinták alja megégett, és a rendezés végén minden palacsintának az égett oldalával alul kell elhelyezkednie. Az égetettpalacsinta-gráf ennek a problémának a gráf-reprezentációja: az előjeles permutációban ha az i palacsinta égett oldalával felfelé van, akkor a permutációban az i helyén az i` negatív elem szerepel.

A $P'_{n}$ égetettpalacsinta-gráf reguláris, rendje (csúcsainak száma) $2^{n}\cdot n!$, fokszáma $n$.

Erre a változatra David S. Cohen (David X. Cohen) és Manuel Blum 1995-ben a következő állítást igazolták: $3n/2\leq P'_{n}\leq 2n-2$ (ahol a felső korlát csak $n>9$-től válik igazzá).

Égetettpalacsinta-számok
(A078941 sorozat az OEIS-ben)

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

Az égetettpalacsinta-gráf girthparamétere:

$g(P_{n})=8{\text{, ha }}n>2$.

Alkalmazásai

A palacsintagráfok számos érdekes tulajdonsággal rendelkeznek – szimmetrikus és rekurzív szerkezetük (Cayley-gráfok, ezért csúcstranzitívek), szublogaritmikus fokszámmal és átmérővel rendelkeznek és relatíve ritkák (pl. a hiperkockagráfokhoz képest), ezért a permutáló csillaggráfok mellett a párhuzamos számítógépek hálózati összeköttetéseinek modelljeként komoly érdeklődés tárgyát képezik. Hálózati összeköttetések modelljeként tekintve a palacsintagráfokra, a gráf átmérője a kommunikációs késleltetést reprezentálja.

A palacsinta-megfordításnak biológiai aspektusai is vannak, a genetikai vizsgálatok területén. Az evolúciós változások egyik fajtájában az egyed DNS-ének valamely szakasza megfordul, ami az égetettpalacsinta-problémával analóg.

Egyéb palacsintagráf-osztályok

Az eredeti palacsintarendezési problémánál és az égetettpalacsinta-problémánál is a kezdőszelet megfordítása (prefix reversal) volt a művelet, amivel az egyik permutációból el lehetett jutni a másikba. Ha megengedjük a nem prefixált fordításokat is (a „két fordítólapátos” eset), akkor összesen négy palacsintagráf-osztály határozható meg. Minden palacsintagráf beágyazható a saját osztályába tartozó bármely magasabb rendű gráfba.

Palacsintagráf-osztályok

Név	Jelölés	Magyarázat	Rend	Fokszám	Girth (ha n>2)
előjel nélküli kezdőszelet-megfordítási gráf (unsigned prefix reversal graph)	$UP_{n}$	Az eredeti palacsintarendezési probléma	$n!$	$n-1$	$6$
előjel nélküli megfordítási gráf (unsigned reversal graph)	$UR_{n}$	Az eredeti probléma két spatulával	$n!$	${n \choose 2}$	$4$
előjeles kezdőszelet-megfordítási gráf (signed prefix reversal graph)	$SP_{n}$	Az égetettpalacsinta-probléma	$2^{n}\cdot n!$	$n$	$8$
előjeles megfordítási gráf (signed reversal graph)	$SR_{n}$	Az égetett probléma két spatulával	$2^{n}\cdot n!$	${n+1 \choose 2}$	$4$

További információk

• Palacsintagráf fogalma