Graf sendvich muammosi - Graph sandwich problem - Wikipedia

Yilda grafik nazariyasi va Kompyuter fanlari, sendvich muammosi - bu ma'lum bir grafikalar oilasiga mansub va boshqa ikkita grafik o'rtasida "joylashtirilgan" grafikni topish muammosi, ulardan biri subgraf, ikkinchisi esa kerakli grafikning supergrafasi bo'lishi kerak.

Graf sendvich muammolari, berilgan grafikaning grafikalar oilasiga mansubligini tekshirish muammolarini umumlashtiradi va ularning qo'llanilishi sababli va tanib olish muammolarining tabiiy umumlashtirilishi sifatida e'tiborni tortdi.[1]

Muammoni hal qilish

Aniqrog'i, vertex to'plami berilgan V, majburiy chekka to'plami E1va kattaroq chekka to'plami E2, grafik G = (V, E) a deyiladi sendvich juftlik uchun grafik G1 = (V, E1), G2 = (V, E2) agar E1 ⊆ E ⊆ E2.The sendvich muammosi property xususiyati uchun quyidagicha aniqlanadi:[2][3]

Grafik sendvich muammosi mulk uchun Π:
Mavzu: Vertex o'rnatildi V va chekka to'plamlar E1 ⊆ E2 ⊆ V × V.
Savol: Grafik bormi? G = (V, E) shu kabi E1 ⊆ E ⊆ E2 va G mulkni qondiradi Π?

The tanib olish muammosi grafikalar sinfi uchun (xususiyatni qondiradiganlar), bu erda ma'lum bir sendvich muammosiga tengdir E1 = E2, ya'ni ixtiyoriy chekka to'plami bo'sh.

Hisoblashning murakkabligi

Graf sendvich muammosi To'liq emas $ Delta $ a bo'lish xususiyatidir akkord grafigi, taqqoslash grafigi, almashtirish grafigi, akkord ikki tomonlama grafigi, yoki zanjir grafigi.[2][4] Uni polinom vaqtida echish mumkin bo'lingan grafikalar,[2][5] pol qiymatlari,[2][5] va har beshta tepada ko'pi bilan to'rtta vertikal bo'lgan grafikalar induktsiya qilingan yo'l.[6]Murakkablik holati ham hal qilindi H- to'rtta vertikal grafikaning har biri uchun bepul grafik sendvich muammolari H.[7]

Adabiyotlar

  1. ^ Golumbich, Martin Charlz; Trenk, Ann N. (2004), "4-bob. Zondlarning intervalli grafikalari va sendvich muammolari", Bardoshlik grafigi, Kembrij, 63-83 betlar.
  2. ^ a b v d Golumbich, Martin Charlz; Kaplan, Xaym; Shamir, Ron (1995), "Graf sendvich muammolari", J. Algoritmlar, 19: 449–473, doi:10.1006 / jagm.1995.1047.
  3. ^ Golumbich, Martin Charlz (2004), Algoritmik grafik nazariyasi va mukammal grafikalar, Diskret matematika yilnomalari, 57 (2-nashr), Elsevier, p. 279.
  4. ^ de Figueiredo, C. M. H.; Farya, L .; Klayn, S .; Sritharan, R. (2007), "Kuchli xordal grafikalar va xordal bipartitli grafikalar uchun sendvich muammolarining murakkabligi to'g'risida", Nazariy kompyuter fanlari, 381 (1–3): 57–67, doi:10.1016 / j.tcs.2007.04.007, JANOB  2347393.
  5. ^ a b Mahadev, N.V.R .; Peled, Uri N. (1995), Eshik grafikalari va tegishli mavzular, Diskret matematika yilnomalari, 57, Shimoliy-Gollandiya, 19-22 betlar.
  6. ^ Dantas, S .; Klayn, S .; Mello, C.P.; Morgana, A. (2009), "Graf sendvich muammosi P4- siyrak grafikalar ", Diskret matematika, 309: 3664–3673, doi:10.1016 / j.disc.2008.01.014.
  7. ^ Dantas, Simone; de Figueiredo, Celina M.H.; Maffray, Frederik; Teixeira, Rafael B. (2013), "Taqiqlangan subgraf sendvich muammolari va skew bo'linish sendvich muammolarining murakkabligi", Diskret amaliy matematika: 2013 yil 11 oktyabrda onlayn mavjud, doi:10.1016 / j.dam.2013.09.004.

Qo'shimcha o'qish

  • Dantas, Simone; de Figueiredo, Celina M.H.; da Silva, Murilo V.G.; Teixeira, Rafael B. (2011), "Taqiqlangan subgraf sendvich muammosi to'g'risida", Diskret amaliy matematika, 159: 1717–1725, doi:10.1016 / j.dam.2010.11.010.