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..

A particionált próbagráf-osztályok felismerési problémája a gráfszendvics-probléma alesetének tekinthető.David B. Chandler, Maw-Shang Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng: Probe Graph Classes (October 17, 2012)

Problémafelveté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:..

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 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).. Polinom időben oldható meg split gráfokra,. küszöbgráfokra é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.. 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..

Fordítás

Jegyzetek

Irodalom .

Kategória:Gráfelmélet Kategória:Számítási problémák a gráfelméletben