A matematika, azon belül a gráfelmélet területén egy Pn 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 Pn palacsintagráf reguláris, csúcsainak száma n!, fokszáma n − 1.
Az n méretű palacsintagráf, Pn rekurzívan előállítható a Pn−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 Pn (n ≥ 4) palacsintagráf szuperösszefüggő és hiperösszefüggő.
A palacsintagráf girthparamétere:
A Pn palacsintagráf γ(Pn) génuszáról elmondható, hogy:
Színezése A palacsintagráfok színezésével kapcsolatban a következő eredmények ismertek.
A Pn (n ≥ 3) palacsintagráf totális kromatikus száma , élkromatikus száma .
A palacsintagráf (n−1)-színezésére és totális n-színezésére hatékony algoritmus ismert.
A kromatikus számra a következő korlátok adhatók:
Ha , akkor
ha , akkor
ha , akkor
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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 3 3 4 4 4? 4? 4? 4? 4? 4? 4? 4? 4?
Köreinek száma A Pn (n ≥ 3) palacsintagráfban minden esetben található l hosszúságú kör, ahol (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 Pn (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 független (csúcsdiszjunkt) darabot tartalmaz.
A Pn (n ≥ 4) palacsintagráf 7 hosszúságú köreiről elmondható, hogy minden csúcs pontosan 7 hosszúságú körbe tartozik, melyekből a gráf összesen különböző darabot tartalmaz.
A Pn (n ≥ 4) palacsintagráf 8 hosszúságú köreiről elmondható, hogy ezekből a gráf összesen különböző darabot tartalmaz, melyekből maximálisan 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19
A palacsintaszám, tehát az palacsintát tartalmazó oszlop rendezéséhez mindig elégséges, minimális átfordítások száma és (kb. és ) között van, de a pontos érték nem ismert.
1979-ben Bill Gates és Christos Papadimitriou felső korlátot igazolt. Ezt 30 évvel később -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 égetettpalacsinta-gráf reguláris, rendje (csúcsainak száma) , fokszáma .
Erre a változatra David S. Cohen (David X. Cohen) és Manuel Blum 1995-ben a következő állítást igazolták: (ahol a felső korlát csak -től válik igazzá).David S. Cohen, Manuel Blum: On the problem of sorting burnt pancakes. In: Discrete Applied Mathematics. 61, Nr. 2, 1995, S. 105–120. DOI:10.1016/0166-218X(94)00009-3.
+ Égetettpalacsinta-számok 1 2 3 4 5 6 7 8 9 10 11 12 1 4 6 8 10 12 14 15 17 18 19 21
Az égetettpalacsinta-gráf girthparamétere:
.
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.Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGrawHill (1994)
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ályokNévJelölésMagyarázatRendFokszámGirth (ha n>2) előjel nélküli kezdőszelet-megfordítási gráf(unsigned prefix reversal graph) Az eredeti palacsintarendezési probléma előjel nélküli megfordítási gráf(unsigned reversal graph) Az eredeti probléma két spatulával előjeles kezdőszelet-megfordítási gráf(signed prefix reversal graph) Az égetettpalacsinta-probléma előjeles megfordítási gráf(signed reversal graph) Az égetett probléma két spatulával
További információk Palacsintagráf fogalma
Jegyzetek
Kategória:Gráfelmélet Kategória:Parametrikus gráfcsaládok