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	n(n−1)
Átmérő	lásd a cikkben
Derékbőség	6, ha n>2
Kromatikus szám	lásd a cikkben
Génusz	lásd a cikkben
Egyéb	reguláris, Cayley-gráf, csúcstranzitív, nem éltranzitív, nem távolságtranzitív
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.

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.

Tulajdonságai

A P_n palacsintagráf reguláris, csúcsainak száma n!, fokszáma n−1. 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$

Átmérője

A palacsintarendezési probléma és a palacsintagráf átmérőjének („palacsintaszám”) meghatározása egymással ekvivalens.

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.

Égetett palacsintagráf

Az égetett palacsinta-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 égetett palacsinta-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. 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á).

Égetett palacsinta-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

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.