Gráfszendvics-probléma
A matematika, azon belül a gráfelmélet, valamint a számítástudomány területén a gráfszendvics-probléma (graph sandwich problem) azon gráf megkeresésének a problémája, ami egy bizonyos gráfcsaládba tartozik és két másik gráf „szendvics”-ként közrefogja; az egyik a keresett gráf részgráfja, a másiknak pedig a keresett gráf a részgráfja..
A gráfszendvics-problémák az adott gráf valamely gráfcsaládba tartozása tesztelésének problémáját általánosítják, érdekességüket alkalmazási lehetőségeik mellett az adja, hogy felismerési problémák általánosításaként tekinthetők.[1]
A particionált próbagráf-osztályok felismerési problémája a gráfszendvics-probléma alesetének tekinthető.[2]
Problémafelvetés[szerkesztés]
Precízebben, vegyünk egy V csúcshalmazt, az E1 kötelező élhalmazt és a nagyobb E2 élhalmazt, ekkor a G = (V, E) gráfot akkor nevezzük a G1 = (V, E1), G2 = (V, E2) pár „szendvicsgráfjának”, ha E1 ⊆ E ⊆ E2.
A Π tulajdonságra vonatkozó gráfszendvics-probléma a következőképp határozható meg:[3][4]
- Gráfszendvics-probléma a Π tulajdonságra:
- Példány: V csúcshalmaz, E1 és E2 élhalmazok, melyekre igaz, hogy E1 ⊆ E2 ⊆ V × V.
- Kérdés: létezik-e olyan G = (V, E) gráf, melyre E1 ⊆ E ⊆ E2 és G teljesíti a Π tulajdonságot?
A valamely gráfosztályra (a Π tulajdonságot teljesítő gráfokra) vonatkozó felismerési probléma megegyezik azzal a gráfszendvics-problémával, ahol E1 = E2, tehát az opcionális élhalmaz üres.
Számítási bonyolultság[szerkesztés]
A gráfszendvics-probléma NP-teljes, ha Π az a tulajdonság, hogy a gráf merev körű, összehasonlíthatósági gráf, permutációgráf, gyengén merev körű páros gráf vagy láncgráf (irányított kör-mentes vegyes gráf).[3][5] Polinom időben oldható meg split gráfokra,[3][6] küszöbgráfokra[3][6] és olyan gráfokra, melyekben bármely öt csúcs tartalmaz legalább egy négy csúcs között futó feszített utat.[7] A bonyolultsági osztályba sorolás eldőlt a H-mentességre vonatkozó gráfszendvics-problémákra, ahol H a négy csúcsból álló gráfok egyike.[8]
Fordítás[szerkesztés]
- Ez a szócikk részben vagy egészben a Graph sandwich problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek[szerkesztés]
- ↑ Golumbic, Martin Charles & Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83.
- ↑ David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng: Probe Graph Classes (October 17, 2012)
- ↑ a b c d Golumbic, Martin Charles; Kaplan, Haim & Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms 19: 449–473, DOI 10.1006/jagm.1995.1047.
- ↑ Golumbic, Martin Charles (2004), Algorithmic Graph Theory and Perfect Graphs, vol. 57 (2nd ed.), Annals of Discrete Mathematics, Elsevier, p. 279, <https://books.google.com/books?id=8xo-VrWo5_QC&pg=PA279>.
- ↑ de Figueiredo, C. M. H.; Faria, L. & Klein, S. et al. (2007), "On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs", Theoretical Computer Science 381 (1-3): 57–67, DOI 10.1016/j.tcs.2007.04.007.
- ↑ a b Mahadev, N.V.R. & Peled, Uri N. (1995), Threshold Graphs and Related Topics, vol. 57, Annals of Discrete Mathematics, North-Holland, pp. 19–22, <https://books.google.com/books?id=nWfGo_VX5M8C&pg=PA19>.
- ↑ Dantas, S.; Klein, S. & Mello, C.P. et al. (2009), "The graph sandwich problem for P4-sparse graphs", Discrete Mathematics 309: 3664–3673, DOI 10.1016/j.disc.2008.01.014.
- ↑ Dantas, Simone; de Figueiredo, Celina M.H. & Maffray, Frédéric et al. (2013), "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem", Discrete Applied Mathematics: Available online 11 October 2013, DOI 10.1016/j.dam.2013.09.004.
Irodalom[szerkesztés]
- Dantas, Simone; de Figueiredo, Celina M.H. & da Silva, Murilo V.G. et al. (2011), "On the forbidden induced subgraph sandwich problem", Discrete Applied Mathematics 159: 1717-1725, DOI 10.1016/j.dam.2010.11.010.