Număr median

Un grafic median este un grafic care reprezintă muchiile adiacente în interiorul fețelor unui grafic plan dat .

Definiție formală

Având în vedere un grafic planar conex , graficul său din mijloc conține: $G$ $M(G)$

vârf pentru fiecare muchie , $G$
o muchie între două vârfuri pentru fiecare față dacă muchiile graficului sunt într-un rând pe ea. $G$ $G$

Graficul median al unui grafic deconectat este o uniune deconectată a graficelor mediane ale componentelor conectate.

Proprietăți

Deoarece graficul median depinde de metoda de încorporare, graficul median nu este unic în sensul că același grafic planar poate avea mai multe grafice mediane neizomorfe . Dimpotrivă, graficele neizomorfe pot avea același grafic din mijloc. În special, un graf plan și graful său dual au un graf din mijloc.

Graficele mediane sunt 4 grafice regulate . Mai mult, orice graf planar cu 4 regulate este un graf din mijloc al unui graf planar. Pentru un graf planar cu 4 regulate conectat , graful plan pentru care este un graf din mijloc poate fi construit după cum urmează: fețele sunt colorate în două culori (ceea ce este posibil, deoarece este Euler și deoarece dualul grafului este bipartit). ); vârfurile în corespund fețelor de aceeași culoare în . Aceste vârfuri sunt conectate printr-o muchie pentru fiecare vârf comun (pentru două fețe) în . Rețineți că făcând această construcție cu fețe de o culoare diferită, obținem un grafic dual. $H$ $G$ $H$ $G$ $H$ $H$ $G$ $H$ $H$ $G$

Dacă două grafice au același grafic din mijloc, ele sunt duale [1] .

Graficul median direcționat

În graficul din mijloc poate fi introdusă o orientare : pentru aceasta, graficul din mijloc este colorat în două culori, în funcție de faptul că fața graficului din mijloc conține sau nu vârfurile graficului original, iar orientarea este introdusă în așa fel. că feţele oricăreia dintre culori sunt în stânga marginilor .

Graficul plan și dualul său au grafice mediane direcționate diferite care sunt inverse unul față de celălalt.

Polinomul Tatta

Pentru un grafic plan , valoarea dublă a polinomului Tatta în punctul (3,3) este egală cu suma orientărilor Euler ponderate din graficul din mijloc , unde ponderea orientării este ( este numărul de vârfuri de șa ale orientării, adică numărul de vârfuri ale căror arcuri incidente sunt ordonate după ciclu „incoming - outgoing - incoming - outgoing”) [2] . Deoarece polinomul lui Tutta este un invariant de încorporare, rezultatul arată că pentru un grafic dat, orice grafic median are aceeași sumă ponderată a orientărilor Euler. $G$ $G$ ${\displaystyle 2^{s))$ $s$

Folosind un grafic median direcționat, se poate generaliza eficient rezultatul calculării polinomului Tatta în punctul (3,3). Pentru un grafic plan , înmulțit cu valoarea polinomului lui Tutt în punct este egal cu suma ponderată a tuturor colorărilor arcelor în culori din graficul median orientat al graficului , astfel încât fiecare set (eventual gol) de arce de aceeași culoare formează un grafic Euler orientat, unde ponderea orientării lui Euler este ( este numărul de vârfuri monocromatice, adică vârfuri, toate cele patru margini incidente la care au aceeași culoare) [3] [4] . $G$ $n$ $(n+1,n+1)$ $n$ $G$ ${\displaystyle 2^{s))$ $s$

Note

↑ Handbook of Graph Theory / Jonathan L. Gross, Jay Yellen. - CRC Press, 2003. - P. 724. - ISBN 978-1584880905 .
↑ Michel Las Vergnas. Despre evaluarea la (3, 3) a polinomului Tutte a unui graf // Journal of Combinatorial Theory, Series B. - 1988. - Vol. 35 , nr. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
↑ Joanna A. Ellis-Monaghan. Identitati pentru polinoamele de partiție a circuitelor, cu aplicații la polinomul Tutte // Progrese în matematică aplicată. - 2004. - T. 32 , nr. 1-2 . - S. 188-197 . — ISSN 0196-8858 . - doi : 10.1016/S0196-8858(03)00079-4 .
↑ Michael Korn, Igor Pak. Evaluări combinatorii ale polinului Tutte. — 2003, pretipărire. — P. 4, Colorarea marginilor graficului medial .

Literatură

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