Négyszöggráf

Egy négyszöggráf.

A matematika, azon belül a gráfelmélet területén egy négyszöggráf (squaregraph) egy irányítatlan gráf, ami síkba rajzolható oly módon, hogy a lerajzolás minden belső tartománya négyszög, és minden három vagy kevesebb szomszéddal rendelkező csúcs rajta van egy nem korlátos tartományon.

Kapcsolódó gráfcsaládok

A négyszöggráfok közé tartoznak a fák, a rácsgráfok, a fogaskerékgráfok és a poliominók gráfjai.

A négyszöggráfok amellett, hogy síkgráfok, mediángráfok is, tehát bármely három u, v és w csúcsra igaz, hogy létezik olyan egyedi medián tulajdonságú m(u,v,w) csúcs, ami a három csúcs között páronként legrövidebb utakon fekszik.[1] Ahogy az összes medián gráfok is, a négyszöggráfok is mind hiperkockák részgráfjai (partial cube): csúcsaik címkézhetők bitfüzérekkel oly módon, hogy két füzér Hamming-távolsága megegyezzen a csúcsok közötti legrövidebb út hosszával.

Ha egy négyszöggráfból képezünk egy gráfot oly módon, hogy az új gráf minden csúcsa a négyszöggráf egy zónájának feleljen meg (a négyszögek párhuzamos éleinek ekvivalenciaosztálya) és a közös négyszögben találkozó zónák közé pedig élt húzunk, akkor húrmetszetgráfot kapunk.[2]

Karakterizáció

A négyszöggráfok a síkba ágyazásukon kívül másképpen is karakterizálhatók:[2]

  • Azok a mediángráfok, melyek nem tartalmazzák feszített részgráfként a tiltott gráfok végtelen osztályának egyik tagját sem. Ebben az esetben a tiltott gráfok közé tartoznak: a K3 szimplexgráfja), a K1,3 karomgráf és egy él Descartes-szorzata (a karom szimplexgráfja) és a fogaskerékgráfokból a kerékagyhoz egy csúcs csatlakoztatásával kapott gráfok (egy körgráf és egy izolált csúcs diszjunkt uniójából álló gráf szimplexgráfjai).
  • Azok az összefüggő és páros gráfok, melyekre igaz, hogy (bármely r csúcsot választva a gráf gyökerének) minden csúcsnak legfeljebb két, r-hez nála közelebbi csúcsa van és bármely v csúcsára, a v csúcs linkje (az a gráf, melyben egy csúcs szerepel minden v-ből kiinduló élhez, él pedig a v-t tartalmazó 4-körökhöz tartozik) pedig vagy háromnál hosszabb kör, vagy utak diszjunkt uniója.
  • A hiperbolikus sík azon egyeneselrendezéseinek duális gráfjai, melyek nem tartalmaznak három, egymást kölcsönösen metsző egyenest.

Algoritmusok

A négyszöggráfoknak a gyökércsúcstól való távolságon és a csúcsok linkjein alapuló karakterizálása egy szélességi kereséssel együtt egy a négyszöggráfokat tesztelő lineáris idejű algoritmus alapját képezi, és így nincs szükség az általános gráfok síkgráf voltának tesztelésére használt bonyolultabb, lineáris idejű algoritmusokra.[2]

Számos algoritmikus probléma egyszerűbben kiszámítható a négyszöggráfokon, mint az általánosabb síkgráfokon vagy mediángráfokon; például (Chepoi, Dragan & Vaxès 2002) és (Chepoi, Fanciullini & Vaxès 2004) lineáris idejű algoritmusokat mutat a négyszöggráfok átmérőjének meghatározására, továbbá a csúcsoktól való maximális távolság tekintetében minimális csúcs megkeresésére.

Jegyzetek

  1. (Soltan, Zambitskii & Prisǎcaru 1973). Lásd (Peterin 2006)-ot a síkba rajzolható medián gráfok leírásához.
  2. a b c (Bandelt, Chepoi & Eppstein 2010).

Fordítás

  • Ez a szócikk részben vagy egészben a Squaregraph 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.