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 szerkesztés
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ó szerkesztés
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 szerkesztés
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 szerkesztés
- ↑ (Soltan, Zambitskii & Prisǎcaru 1973). Lásd (Peterin 2006)-ot a síkba rajzolható medián gráfok leírásához.
- ↑ a b c (Bandelt, Chepoi & Eppstein 2010).
- Bandelt, H.-J.; Chepoi, V. & Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics 24 (4): 1399–1440, DOI 10.1137/090760301.
- Chepoi, V.; Dragan, F. & Vaxès, Y. (2002), "Center and diameter problem in planar quadrangulations and triangulations", Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 346–355.
- Chepoi, V.; Fanciullini, C. & Vaxès, Y. (2004), "Median problem in some plane triangulations and quadrangulations", Comput. Geom. 27 (3): 193–210, DOI 10.1016/j.comgeo.2003.11.002.
- Peterin, I. (2006), "A characterization of planar median graphs", Discussiones Mathematicae Graph Theory 26: 41–48, <http://www.mp.feri.uni-mb.si/osebne/peterin/clanki/planarmedian6.pdf>. Hozzáférés ideje: 2017-03-28 Archiválva 2011. október 5-i dátummal a Wayback Machine-ben.
- Soltan, P.; Zambitskii, D. & Prisǎcaru, C. (1973), Extremal Problems on Graphs and Algorithms of their Solution, Chişinǎu, Moldova: Ştiinţa.
Fordítás szerkeszté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.