A matematika, azon belül a gráfelmélet területén a boxicitás, boxicity paraméter vagy hipertéglatest-dimenzió egy Fred S. Roberts által 1969-ben bevezetett gráfparaméter. Egy gráf boxicitása az a minimális dimenzió, melyben adott gráf felírható egymással párhuzamos tengelyű hipertéglatestek metszetgráfjaként. Tehát ha a gráf csúcsai és a hipertéglatestek halmaza között kölcsönös megfeleltetés létesíthető oly módon, hogy két hipertéglatest pontosan akkor metszi egymást, ha a nekik megfelelő csúcsok között él húzódik.

Téglalapok metszetgráfja, boxicitás = 2

PéldákSzerkesztés

Az ábrán egy hat csúcsú gráf és téglalapok (kétdimenziós hipertéglatestek) metszetgráfjaként való reprezentációja látható. Ez a gráf nem ábrázolható alacsonyabb dimenziójú hipertéglatestek metszetgráfjaként (pl. intervallumgráfként), ezért boxicity paramétere kettő. (Roberts 1969) megmutatta, hogy a 2n csúcsú csúcsú teljes gráfból egy teljes párosítás eltávolításával kapott gráf boxicitása éppen n: minden eltávolított csúcspárt másik dimenzióban elválasztott hipertéglatesteknek kell reprezentálnia, mint a többi párt. Ennek a gráfnak egy konkrét hipertéglatest-reprezentációját elő lehet állítani egy n dimenziós hiperkocka hiperlapjainak hipertéglatestté vastagításával. Az eredmény alapján ezt a gráfot Roberts-gráfnak is hívják,[1] bár ismertebb neve koktélpartigráf, illetve tekinthető úgy is, hogy ez a T(2n,n) Turán-gráf.

Más gráfcsaládokkal való kapcsolataSzerkesztés

Egy gráf boxicity paramétere pontosan akkor egy, ha intervallumgráf (az intervallum felfogható egydimenziós téglatestként). A külsíkgráfok boxicitása legfeljebb kettő,[2] az általánosabb síkbarajzolható gráfoké pedig legfeljebb három.[3] Ha egy páros gráf boxicitása kettő, előállítható egy síkbeli derékszögű koordináta-rendszer tengelyeivel párhuzamos intervallumok metszetgráfjaként.[4]

Algoritmikus eredményekSzerkesztés

Számos gráfokkal kapcsolatos probléma az általános esetnél egyszerűbben megoldható korlátozott boxicitású gráfokra. Például a maximálisklikk-probléma korlátos boxicitású gráfokra polinom időben megoldható.[5] Néhány más gráfproblémánál a hatékony megoldást vagy a jó közelítő megoldást elősegíti, ha ismert a gráf egy alacsony dimenziószámú hipertéglatest-reprezentációja.[6] Az ilyen reprezentáció előállítása azonban nehéz: NP-teljes annak tesztelése, hogy adott gráf boxicitása K-val egyezik-e, még K = 2-re is.[7]

A (Chandran, Francis & Sivadasan 2010) leír néhány algoritmust tetszőleges gráfok hipertéglatest-metszetgráfként való reprezentációinak előállítására, a gráf maximális fokszámával logaritmikus faktor közelségben lévő dimenziószámmal; ez az eredmény egyben megad egy felső korlátot a gráf boxicitására.

Bár a boxicitás meghatározása nehéz probléma, a bemeneti gráf csúcslefedési számával parametrizálva rögzített paraméter mellett kezelhető.[8]

KorlátokSzerkesztés

Louis Esperet a G gráf boxicitására a gráf élszámának, m-nek függvényében a következő, aszimptotikusan optimális korlátot igazolta:

 .[9]

Kapcsolódó gráfparaméterekSzerkesztés

Ugyanazon gráf Colin de Verdière-invariánsa és boxicitása között Louis Esperet a következő összefüggést igazolta:

 ,

továbbá valószínűsíti, hogy a boxicitás legfeljebb a Colin de Verdière-invariánssal egyenlő.[9]

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Boxicity 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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Pl. lásd (Chandran, Francis & Sivadasan 2010) és (Chandran & Sivadasan 2007).
  2. (Scheinerman 1984).
  3. (Thomassen 1986).
  4. (Bellantoni et al. 1993).
  5. (Chandran, Francis & Sivadasan 2010) megfigyelése szerint ez abból fakad, hogy ezek a gráfok polinomiális számú maximális klikkel rendelkeznek. Nincs szükség a hipertéglatest-reprezentáció tényleges előállítására a maximális klikkek hatékony megkereséséhez.
  6. Lásd pl. (Agarwal, van Kreveld & Suri 1998) és (Berman et al. 2001) téglalapok metszetgráfjai maximális független csúcshalmazainak approximációiért, (Chlebík & Chlebíková 2005)-t pedig arról, magasabb dimenziókban mennyire nehéz ezeknek a problémáknak az approximációja.
  7. (Cozzens 1981) megmutatja, hogy a boxicitás kiszámítása NP-teljes; (Yannakakis 1982) igazolja, hogy még azt is NP-nehéz eldönteni, hogy a boxicitás legfeljebb 3-e; végül (Kratochvil 1994) megmutatja, hogy a 2 boxicitás felismerése is NP-nehéz.
  8. (Adiga, Chitnis & Saurabh 2010).
  9. a b Sablon:Cite arXiv