Kehyskaavio

Graafiteoriassa kehysgraafi on eräänlainen suuntaamaton graafi , joka voidaan piirtää tasolle siten, että mikä tahansa rajattu pinta on nelikulmio ja mikä tahansa kärki , jolla on kolme tai vähemmän naapureita, tulee rajaamattomaan pintaan.

Aiheeseen liittyvät graafiluokat

Kehyskaaviot sisältävät erikoistapauksissa puut , hilat , hammaspyörät ja polyominokuvaajat .

Koska laatikkograafit ovat tasomaisia , ne ovat myös mediaaneja , mikä tarkoittaa, että millä tahansa kolmella pisteellä u , v ja w on yksi kärki m ( u , v , w ) (kutsutaan mediaaniksi), joka sijaitsee lyhimmällä polulla kukin näiden kolmen kärjen pari [1] . Kuten yleisemmät mediaanigraafit, laatikkokaaviot ovat osittaisia ​​kuutioita  – niiden kärjet voidaan merkitä bittijonoilla siten, että merkkijonojen välinen Hamming-etäisyys on yhtä suuri kuin pisteiden välinen lyhin etäisyys.

Ominaisuudet

Laatikkokaavioita voidaan luonnehtia useilla eri tavoilla kuin tasomaisuusominaisuuden [2] :

• Ne ovat mediaanikaavioita , jotka eivät sisällä yhtään jäsentä kiellettyjen graafien äärettömästä perheestä generoituna aligraafina . Näitä kiellettyjä graafia ovat kuutio ( simplex graph K 3 ), reunan ja kynnen suora tulo K 1,3 ( claw simplex graph ) sekä graafit, jotka on muodostettu hammaspyörästä lisäämällä ylimääräinen kärki, jota yhdistää reuna pyörän keskelle.
• Ne ovat yhteenliitettyjä ja kaksiosaisia ​​graafeja siten, että jos juuriksi valitaan mikä tahansa kärki r , millä tahansa kärjellä on korkeintaan kaksi naapuria, jotka ovat lähempänä r :tä ja siten, että mille tahansa kärjelle v on v :n nippu (kukin pisteistä koostuva graafi sattuva v reunat ja reunat kaikille syklille, joiden pituus on 4, jotka sisältävät kärjen v ) on joko jakso, jonka pituus on vähintään kolme, tai irrotettu joukko polkuja.
• Ne ovat hyperbolisen tason viivakonfiguraatioiden kaksoiskaavioita, jotka eivät sisällä kolmea pareittain leikkaavaa viivaa.

Algoritmit

Laatikkokaavioiden kuvaamista etäisyyden perusteella juuri- ja kärkinipuista (katso yllä) voidaan käyttää yhdessä leveyshaun kanssa osana lineaariaikaista algoritmia sen testaamiseksi, onko tietty graafi laatikkokaavio ilman, että tarvitsee käyttää enempää. monimutkaiset lineaariaikaiset algoritmit mielivaltaisten graafien tasoisuuden tarkistamiseksi [2] .

Jotkut kehyskaavioiden algoritmiset ongelmat voidaan ratkaista tehokkaammin kuin samat ongelmat yleisemmissä tasokaavioissa. Esimerkiksi Chepoy, Dragan, Waxes ja Fancillini [3] [4] ehdottivat aikalineaarisia algoritmeja laatikkograafien halkaisijan laskemiseksi ja sen kärjen löytämiseksi, joka on pienimmällä etäisyydellä kaikista muista pisteistä (eli kärkipisteestä). jossa suurin mahdollinen etäisyys kaikkiin muihin pisteisiin).

Muistiinpanot

1. ↑ Soltan, Sambitsky, Prisakaru, 1973 . Katso Peterin, 2006 yleisempää keskustelua tasomaisista mediaanikaavioista .
2. ↑ 1 2 Bandelt, Chepoi, Eppstein, 2010 .
3. ↑ Chepoi, Dragan, Vaxès, 2002 .
4. ↑ Chepoi, Fanciullini, Vaxès, 2004 .

Kirjallisuus

• H.J. Bandelt, V. Chepoi, D. Eppstein. Äärillisten ja äärettömien neliögraafien kombinatoriikka ja geometria // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , no. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 .
• V. Chepoi, F. Dragan, Y. Vaxes. Proc. 13. Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2002). - 2002. - S. 346-355 .
• V. Chepoi, C. Fanciullini, Y. Vaxès. Mediaaniongelma joissakin tasokolmioissa ja nelikulmioissa // Laske. Geom.. - 2004. - V. 27 , no. 3 . - S. 193-210 . - doi : 10.1016/j.comgeo.2003.11.002 .
• I. Peterin. Tasomaisten mediaanigraafien karakterisointi // Discussions Mathematicae Graph Theory. - 2006. - T. 26 . - S. 41-48 .  (linkki ei saatavilla)
• Soltan P. S., Zambitsky D. K., Prisacaru K. F. Extremal ongelmia kaavioissa ja algoritmeja niiden ratkaisemiseksi. - Chişinǎu, Moldova: Shtiintsa, 1973.