Coeficiente de malla

En teoría de grafos , el coeficiente de malla es un invariante de grafos planares que mide el número de caras acotadas del grafo, como una fracción del número posible de caras para otros grafos planares con el mismo número de vértices. Varía de 0 para árboles a 1 para grafos planares maximalistas . ^{[1] [2]}

Definición

El coeficiente de malla se utiliza para comparar la estructura general del ciclo de un grafo plano conectado con dos referencias relevantes extremas. En un extremo, hay árboles , grafos planos sin ciclo. ^[1] El otro extremo está representado por grafos planos maximalistas , grafos planos con el mayor número posible de aristas y caras para un número dado de vértices. El coeficiente de malla normalizado es la relación entre los ciclos de caras disponibles y el número máximo posible de ciclos de caras en el grafo. Esta relación es 0 para un árbol y 1 para cualquier grafo plano maximalista.

En términos más generales, se puede demostrar mediante la característica de Euler que todos los grafos planares de n vértices tienen como máximo 2 n  − 5 caras acotadas (sin contar la cara no acotada) y que si hay m aristas, entonces el número de caras acotadas es m  −  n  + 1 (el mismo que el rango del circuito del grafo). Por lo tanto, un coeficiente de mallado normalizado se puede definir como la relación de estos dos números:

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

Varía de 0 para árboles a 1 para gráficos planares máximos.

Aplicaciones

El coeficiente de mallado se puede utilizar para estimar la redundancia de una red. Este parámetro, junto con la conectividad algebraica que mide la robustez de la red, se puede utilizar para cuantificar el aspecto topológico de la resiliencia de la red en redes de distribución de agua. ^[3] También se ha utilizado para caracterizar la estructura de la red de calles en áreas urbanas. ^{[4] [5] [6]}

Limitaciones

Utilizando la definición del grado promedio , se puede ver que en el límite de gráficos grandes (número de aristas ) la malla tiende a ${\displaystyle \langle k\rangle =2m/n}$ ${\displaystyle n\gg 1}$

${\displaystyle \alpha \approx {\frac {\langle k\rangle }{4}}-{\frac {1}{2}}}$

Por lo tanto, para gráficos grandes, la malla no transporta más información que el grado promedio.

Referencias

1. Buhl, J.; Gautrais, J.; Sole, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004). "Eficiencia y robustez en redes de hormigas de galerías". The European Physical Journal B . 42 (1): 123–129. Bibcode :2004EPJB...42..123B. doi :10.1140/epjb/e2004-00364-9. S2CID  14975826.
2. Buhl, J.; Gautrais, J.; Reeves, N.; Sole, RV; Valverde, S.; Kuntz, P.; Theraulaz, G. (2006). "Patrones topológicos en redes de calles de asentamientos urbanos autoorganizados". The European Physical Journal B . 49 (4): 513–522. Bibcode :2006EPJB...49..513B. doi :10.1140/epjb/e2006-00085-1. S2CID  9862922.
3. Yazdani, A.; Jeffrey, P. (2012). "Aplicación de la teoría de redes para cuantificar la redundancia y la robustez estructural de los sistemas de distribución de agua". Revista de planificación y gestión de recursos hídricos . 138 (2): 153–161. doi :10.1061/(ASCE)WR.1943-5452.0000159.
4. Wang, X.; Jin, Y.; Abdel-Aty, M.; Tremont, PJ; Chen, X. (2012). "Desarrollo de modelos de nivel macro para la evaluación de la seguridad de las estructuras de la red vial". Transportation Research Record: Journal of the Transportation Research Board . 2280 (1): 100–109. doi :10.3141/2280-11. S2CID  110263962. Archivado desde el original el 21 de noviembre de 2014.
5. Courtat, T.; Gloaguen, C.; Douady, S. (2011). "Matemáticas y morfogénesis de las ciudades: un enfoque geométrico". Phys. Rev. E . 83 (3): 036106. arXiv : 1010.1762 . Bibcode :2011PhRvE..83c6106C. doi :10.1103/PhysRevE.83.036106. PMID  21517557. S2CID  808585.
6. Rui, Y.; Ban, Y.; Wang, J.; Haas, J. (2013). "Explorando los patrones y la evolución de las redes de calles urbanas autoorganizadas a través del modelado". The European Physical Journal B . 86 (3): 036106. Bibcode :2013EPJB...86...74R. doi :10.1140/epjb/e2012-30235-7. S2CID  254118471.