Mediaaniluku

Mediaanikuvaaja on graafi , joka edustaa vierekkäisiä reunoja tietyn tasograafin pintojen sisällä .

Muodollinen määritelmä

Yhdistetty tasograafi , sen keskimmäinen kaavio sisältää: $G$ $M(G)$

kärki kullekin reunalle , $G$
kunkin pinnan kahden kärjen välinen reuna , jos graafin reunat ovat rivissä siinä. $G$ $G$

Irrotetun graafin mediaanikuvaaja on kytkettyjen komponenttien mediaanikaavioiden irrotettu liitto .

Ominaisuudet

Koska mediaanikuvaaja riippuu upotusmenetelmästä, mediaanikuvaaja ei ole ainutlaatuinen siinä mielessä, että samalla tasograafilla voi olla useita ei- isomorfisia mediaanikaavioita. Sitä vastoin ei-isomorfisilla kaavioilla voi olla sama keskimmäinen graafi. Erityisesti tasograafilla ja sen kaksoisgraafilla on yksi keskimmäinen graafi.

Mediaanikaaviot ovat 4- säännöllisiä kaavioita . Lisäksi mikä tahansa 4-säännöllinen tasograafi on jonkin tasograafin keskikuvaaja. Yhdistetylle 4-säännölliselle tasograafille tasograafi , jolle on keskimmäinen graafi, voidaan rakentaa seuraavasti: pinnat on väritetty kahdella värillä (mikä on mahdollista, koska se on Euler, ja koska graafin duaali on kaksiosainen ); kärjet vastaavat kasvoja samanvärisiä in . Nämä kärjet on yhdistetty reunalla jokaiselle yhteiselle (kahdelle pinnalle) kärkipisteelle . Huomaa, että tekemällä tämä konstruktio eriväristen pintojen kanssa, saadaan kaksoisgraafi . $H$ $G$ $H$ $G$ $H$ $H$ $G$ $H$ $H$ $G$

Jos kahdella graafilla on sama keskimmäinen graafi, ne ovat duaalisia [1] .

Suunnattu mediaanikaavio

Keskimmäiseen kuvaajaan voidaan tuoda orientaatio : tätä varten keskimmäinen graafi värjätään kahdella värillä riippuen siitä, sisältääkö keskimmäisen graafin pinnat alkuperäisen graafin kärjet vai ei, ja orientaatio tuodaan siten. että minkä tahansa värin pinnat ovat reunojen vasemmalla puolella.

Tasograafilla ja sen duaalilla on erilaiset suunnatut mediaanikuvaajat, jotka ovat käänteisiä toisilleen.

Tatta-polynomi

Tasograafissa Tatta-polynomin kaksinkertainen arvo pisteessä (3,3) on yhtä suuri kuin painotettujen Euler-orientaatioiden summa keskimmäisessä kaaviossa , jossa orientaation paino on ( on orientaation satulapisteet, eli niiden kärkien lukumäärä, joiden tulokaaret on järjestetty syklin "saapuva - lähtevä - saapuva - lähtevä" mukaan) [2] . Koska Tutan polynomi on upotusinvariantti, tulos osoittaa, että annetulla graafilla millä tahansa mediaanigraafilla on sama painotettu Euler-orientaatioiden summa. $G$ $G$ ${\näyttötyyli 2^{s))$ $s$

Suunnatun mediaanigraafin avulla voidaan tehokkaasti yleistää Tatta-polynomin laskentatulos pisteessä (3,3). Tasograafille kerrottuna Tuttin polynomin arvolla pisteessä on yhtä suuri kuin kaikkien kaarien väreiksi tehtyjen värjäytysten painotettu summa graafin orientoidussa mediaanikuvaajassa niin, että kukin (mahdollisesti tyhjä) kaarijoukko sama väri muodostaa orientoidun Euler-graafin, jossa Euler-orientaation painoarvo on ( on monokromaattisten kärkien lukumäärä, ts. kärjet, joiden kaikilla neljällä reunalla on sama väri) [3] [4] . $G$ $n$ ${\näyttötyyli (n+1,n+1)}$ $n$ $G$ ${\näyttötyyli 2^{s))$ $s$

Muistiinpanot

↑ Graafiteorian käsikirja / Jonathan L. Gross, Jay Yellen. - CRC Press, 2003. - S. 724. - ISBN 978-1584880905 .
↑ Michel Las Vergnas. Graafin Tutte-polynomin arvioinnista kohdassa (3, 3) // Journal of Combinatorial Theory, Series B. - 1988. - Vol. 35 , no. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
↑ Joanna A. Ellis-Monaghan. Piiriosiopolynomien identiteetit, joissa on sovelluksia Tutte-polynomiin // Advances in Applied Mathematics. - 2004. - T. 32 , no. 1-2 . - S. 188-197 . — ISSN 0196-8858 . - doi : 10.1016/S0196-8858(03)00079-4 .
↑ Michael Korn, Igor Pak. Tutte-polynon kombinatoriset arvioinnit. — 2003, esipainos. — S. 4, Medialikaavion reunojen väritys .

Kirjallisuus

Thomas Brylawski, James Oxley. Matriod Applications / Neil White. - Cambridge University Press, 1992. - S. 123-225.