Factorul de reticulare

Factorul de plasă este un invariant al graficelor plane care măsoară numărul de fețe ale graficului mărginit în raport cu numărul posibil de fețe ale altor grafice plane cu același număr de vârfuri. Coeficientul ia valori de la 0 pentru arbori la 1 pentru graficele planare maxime [1] [2] .

Definiție

Coeficientul este utilizat pentru a compara structura ciclului global a unui grafic plan conex în raport cu două valori extreme. Pe de o parte, există arbori , grafice plane fără cicluri [1] . Cealaltă extremă este reprezentată de grafice plane maxime care au cel mai mare număr posibil de muchii și fețe pentru un număr dat de vârfuri. Factorul de plasă normalizat este raportul dintre numărul de cicluri și numărul maxim posibil de cicluri din grafic (cu același număr de vârfuri). Raportul ia o valoare de la 0 pentru copaci la 1 pentru orice grafic planar maxim.

În general, se poate arăta folosind caracteristica Euler că toate graficele plane cu vârfuri au un maxim de fețe mărginite (o față nemărginită nu contează) și dacă există muchii, atunci numărul de fețe mărginite este egal (care este egal cu rangul de contur al graficului). Astfel, factorul de plasă normalizat poate fi definit ca raportul dintre două numere: $n$ $2n-5$ $m$ $m-n+1$

\alpha ={\frac {m-n+1}{2n-5)).

Și acest coeficient variază de la 0 pentru arbori la 1 pentru graficele plane maxime.

Aplicații

Factorul de plasă poate fi utilizat pentru a evalua redundanța unei rețele. Acest parametru, alături de conectivitatea algebrică , care măsoară fiabilitatea unei rețele, poate fi utilizat pentru măsurarea aspectelor topologice ale rezistenței unei rețele de alimentare cu apă [3] ; folosit și pentru a descrie structura străzilor din orașe [4] [5] [6] .

Restricții

În limita pentru grafice mari (numărul de muchii ), rețeaua tinde către următoarea valoare: $n\gg 1$

\alpha \aprox {\frac {\langle k\rangle }{4}} - {\frac {1}{2}}

unde este gradul mediu al vârfurilor din grafic. Astfel, pentru graficele mari, reticularea nu poartă mai multe informații decât gradul mediu. $\langle k\rangle =2m/n$

Note

↑ 1 2 Buhl, Gautrais, Sole et al., 2004 , p. 123–129.
↑ Buhl, Gautrais, Reeves et al., 2006 , p. 513–522.
↑ Yazdani, Jeffrey, 2012 , p. 153–161.
↑ Wang, Jin, Abdel-Aty et al., 2012 , p. 100–109.
↑ Courtat, Gloaguen, Douady, 2011 , p. 036106.
↑ Rui, Ban, Wang, Haas, 2013 , p. 036106.

Literatură

J. Buhl, J. Gautrais, R. V. Sole, P. Kuntz, S. Valverde, J. L. Deneubourg, G. Theraulaz. Eficiență și robustețe în rețelele de galerii de furnici // The European Physical Journal B-Condensed Matter and Complex Systems. - Springer-Verlag, 2004. - T. 42 , nr. 1 . - doi : 10.1140/epjb/e2004-00364-9 .
J. Buhl, J. Gautrais, N. Reeves, R.V. Sole, S. Valverde, P. Kuntz, G. Theraulaz. Modele topologice în rețelele stradale ale așezărilor urbane auto-organizate // The European Physical Journal B-Condensed Matter and Complex Systems. - Ştiinţe EDP, 2006. - T. 49 , nr. 4 . - doi : 10.1140/epjb/e2006-00085-1 .
A. Yazdani, P. Jeffrey. Aplicarea teoriei rețelelor pentru a cuantifica redundanța și robustețea structurală a sistemelor de distribuție a apei // Journal of Water Resources Planning and Management. - Societatea Americană a Inginerilor Civili, 2012. - Vol. 138 , nr. 2 . - P. 153-161. - doi : 10.1061/(ASCE)WR.1943-5452.0000159 .
X. Wang, Y. Jin, M. Abdel-Aty, PJ Tremont, X. Chen. Dezvoltarea modelului la nivel macro pentru evaluarea siguranței structurilor rețelei rutiere // Înregistrare de cercetare în transport: Jurnalul Consiliului de Cercetare a Transporturilor. - Consiliul de Cercetare în Transport al Academiilor Naţionale, 2012. - Vol. 2280 , nr. 1 . - doi : 10.3141/2280-11 .
T. Courtat, C. Gloaguen, S. Douady. Matematica și morfogeneza orașelor: o abordare geometrică // Phys. Rev. E. - Societatea Americană de Fizică, 2011. - V. 83 , nr. 3 . - doi : 10.1103/PhysRevE.83.036106 .
Y. Rui, Y. Ban, J. Wang, J. Haas. Explorarea tiparelor și evoluției rețelelor stradale urbane auto-organizate prin modelare // The European Physical Journal B. - Springer-Verlag, 2013. - Vol. 86 , nr. 3 . - doi : 10.1140/epjb/e2012-30235-7 .
A. Yazdani, P. Jeffrey. Aplicarea teoriei rețelelor pentru a cuantifica redundanța și robustețea structurală a sistemelor de distribuție a apei // Journal of Water Resources Planning and Management. - Societatea Americană a Inginerilor Civili, 2012. - Vol. 138 , nr. 2 . - doi : 10.1061/(ASCE)WR.1943-5452.0000159 .
X. Wang, Y. Jin, M. Abdel-Aty, PJ Tremont, X. Chen. Dezvoltarea modelului la nivel macro pentru evaluarea siguranței structurilor rețelei rutiere // Înregistrare de cercetare în transport: Jurnalul Consiliului de Cercetare a Transporturilor. - Consiliul de Cercetare în Transport al Academiilor Naţionale, 2012. - Vol. 2280 , nr. 1 . - doi : 10.3141/2280-11 .
T. Courtat, C. Gloaguen, S. Douady. Matematica și morfogeneza orașelor: o abordare geometrică // Phys. Rev. E. - Societatea Americană de Fizică, 2011. - V. 83 , nr. 3 . - doi : 10.1103/PhysRevE.83.036106 .
Y. Rui, Y. Ban, J. Wang, J. Haas. Explorarea tiparelor și evoluției rețelelor stradale urbane auto-organizate prin modelare // The European Physical Journal B. - Springer-Verlag, 2013. - Vol. 86 , nr. 3 . - doi : 10.1140/epjb/e2012-30235-7 .