Factor de reticulación

El factor de malla  es una invariante de los gráficos planos que mide el número de caras de gráficos acotados en relación con el número posible de caras de otros gráficos planos con el mismo número de vértices. El coeficiente toma valores desde 0 para árboles hasta 1 para grafos planos máximos [1] [2] .

Definición

El coeficiente se utiliza para comparar la estructura del ciclo general de un gráfico plano conectado con respecto a dos valores extremos. Por un lado, están los árboles , grafos planos sin ciclos [1] . El otro extremo está representado por grafos planos máximos que tienen el mayor número posible de aristas y caras para un número dado de vértices. El factor de malla normalizado es la relación entre el número de ciclos y el máximo número posible de ciclos en el gráfico (con el mismo número de vértices). La relación toma un valor de 0 para árboles a 1 para cualquier gráfico plano máximo.

En términos generales, se puede demostrar usando la característica de Euler que todos los gráficos planos con vértices tienen un máximo de caras acotadas (una cara no acotada no cuenta) y si hay aristas, entonces el número de caras acotadas es igual (que es igual a el rango de contorno del gráfico). Por lo tanto, el factor de malla normalizado se puede definir como la relación de dos números:

Y este coeficiente varía de 0 para árboles a 1 para gráficos planos máximos.

Aplicaciones

El factor de malla se puede utilizar para evaluar la redundancia de una red. Este parámetro, junto con la conectividad algebraica , que mide la confiabilidad de una red, puede usarse para medir los aspectos topológicos de la resiliencia de una red de suministro de agua [3] ; también se usa para describir la estructura de las calles en las ciudades [4] [5] [6] .

Restricciones

En el límite para gráficos grandes (el número de aristas ), la malla tiende al siguiente valor:

,

donde es el grado promedio de los vértices en el gráfico. Así, para gráficos grandes, la reticulación no lleva más información que el grado medio.

Notas

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

Literatura