Boxicitás

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez
Téglalapok metszetgráfja, boxicitás = 2

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.

Példák

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ő. Sablon:Harvtxt 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ó kapcsolata

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ények

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 Sablon:Harvtxt 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átok

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:

box⁡(G)=O(m⋅log⁡(m)).[9]

Kapcsolódó gráfparaméterek

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

box⁡(G)=O(μ(G)4(log⁡(μ(G))2),

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

Fordítás

Jegyzetek

Sablon:Reflist

Sablon:Refbegin

Sablon:Refend

Sablon:Portál

  1. ↑ Pl. lásd Sablon:Harvtxt és Sablon:Harvtxt.
  2. ↑ Sablon:Harvtxt.
  3. ↑ Sablon:Harvtxt.
  4. ↑ Sablon:Harvtxt.
  5. ↑ Sablon:Harvtxt 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. Sablon:Harvtxt és Sablon:Harvtxt téglalapok metszetgráfjai maximális független csúcshalmazainak approximációiért, Sablon:Harvtxt-t pedig arról, magasabb dimenziókban mennyire nehéz ezeknek a problémáknak az approximációja.
  7. ↑ Sablon:Harvtxt megmutatja, hogy a boxicitás kiszámítása NP-teljes; Sablon:Harvtxt igazolja, hogy még azt is NP-nehéz eldönteni, hogy a boxicitás legfeljebb 3-e; végül Sablon:Harvtxt megmutatja, hogy a 2 boxicitás felismerése is NP-nehéz.
  8. ↑ Sablon:Harvtxt.
  9. ↑ 9,0 9,1 Sablon:Cite arXiv
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Boxicitás&oldid=3777”