Palacsintagráf

Sablon:Gráf infobox 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\le \gamma (P_n)\le 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\le n\le 8$, akkor

$\chi (P_n)\le \{\begin{array}{cc}n-k,& \text{ha }n\equiv k(\mathrm{mod}4),k=1,3;\\ n-2,& \text{ha }n\equiv k(\mathrm{mod}4),k=0,2;\end{array}$

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

$\chi (P_n)\le \{\begin{array}{cc}n-(k+2),& \text{ha }n\equiv k(\mathrm{mod}4),k=1,3;\\ n-4,& \text{ha }n\equiv k(\mathrm{mod}4),k=0,2;\end{array}$

ha $n\ge 17$, akkor

$\chi (P_n)\le \{\begin{array}{cc}n-(k+4),& \text{ha }n\equiv k(\mathrm{mod}4),k=1,2,3;\\ n-8,& \text{ha }n\equiv k(\mathrm{mod}4),k=0.\end{array}$

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\le l\le 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
Sablon:OEIS

$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 Sablon:Math 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{\text{'}}_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\le P{\text{'}}_n\le 2n-2$ (ahol a felső korlát csak $n>9$-től válik igazzá).

Égetettpalacsinta-számok
Sablon:OEIS

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$P{\text{'}}_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)	$U{P}_n$	Az eredeti palacsintarendezési probléma	$n!$	$n-1$	$6$
előjel nélküli megfordítási gráf (unsigned reversal graph)	$U{R}_n$	Az eredeti probléma két spatulával	$n!$	$(\genfrac{}{}{0ex}{}{n}{2})$	$4$
előjeles kezdőszelet-megfordítási gráf (signed prefix reversal graph)	$S{P}_n$	Az égetettpalacsinta-probléma	$2^n\cdot n!$	$n$	$8$
előjeles megfordítási gráf (signed reversal graph)	$S{R}_n$	Az égetett probléma két spatulával	$2^n\cdot n!$	$(\genfrac{}{}{0ex}{}{n+1}{2})$	$4$

További információk

• Palacsintagráf fogalma