coeficiente de mallado

En teoría de grafos , el coeficiente de mallado 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 maximales . ^{[ 1 ] [ 2 ]}

El coeficiente de mallado se utiliza para comparar la estructura cíclica general de un grafo planar conexo con dos referencias extremas relevantes. En un extremo, están los árboles , grafos planares sin ciclos. ^{[ 1 ]} El otro extremo está representado por los grafos planares maximales , grafos planares con el mayor número posible de aristas y caras para un número dado de vértices. El coeficiente de mallado normalizado es la razón entre los ciclos de caras disponibles y el número máximo posible de ciclos de caras en el grafo. Esta razón es 0 para un árbol y 1 para cualquier grafo planar maximal.

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

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

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

El coeficiente de mallado puede utilizarse para estimar la redundancia de una red. Este parámetro, junto con la conectividad algebraica que mide la robustez de la red, puede utilizarse para cuantificar el aspecto topológico de la resiliencia de la red en las 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 ]}

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

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

Por lo tanto, para grafos grandes, la interconexión no aporta más información que el grado promedio.