En matemáticas , la constante de Cheeger (también número de Cheeger o número isoperimétrico ) de un gráfico es una medida numérica de si un gráfico tiene o no un "cuello de botella". La constante de Cheeger como medida del "cuello de botella" es de gran interés en muchas áreas: por ejemplo, la construcción de redes de computadoras bien conectadas , el barajado de cartas . La noción teórica de grafos se originó a partir de la constante isoperimétrica de Cheeger de una variedad compacta de Riemann .
La constante de Cheeger lleva el nombre del matemático Jeff Cheeger .
Definición
Sea G un grafo finito no dirigido con el conjunto de vértices V ( G ) y el conjunto de aristas E ( G ) . Para una colección de vértices A ⊆ V ( G ) , sea ∂ A la colección de todas las aristas que van desde un vértice en A a un vértice fuera de A (a veces llamado límite de arista de A ):
Tenga en cuenta que los bordes están desordenados, es decir, . La constante de Cheeger de G , denotada h ( G ) , se define por [1]
La constante de Cheeger es estrictamente positiva si y solo si G es un gráfico conectado . Intuitivamente, si la constante de Cheeger es pequeña pero positiva, entonces existe un "cuello de botella", en el sentido de que hay dos conjuntos de vértices "grandes" con "pocos" enlaces (bordes) entre ellos. La constante de Cheeger es "grande" si cualquier posible división del conjunto de vértices en dos subconjuntos tiene "muchos" enlaces entre esos dos subconjuntos.
Ejemplo: redes de computadoras
En aplicaciones a la informática teórica, se desea idear configuraciones de red para las que la constante de Cheeger sea alta (al menos, limitada desde cero) incluso cuando | V ( G ) | (la cantidad de computadoras en la red) es grande.
Por ejemplo, considere una red en anillo de N ≥ 3 ordenadores, pensado como un gráfico G N . Numere las computadoras 1, 2, ..., N en el sentido de las agujas del reloj alrededor del anillo. Matemáticamente, el conjunto de vértices y el conjunto de aristas están dados por:
Toma A como una colección de de estas computadoras en una cadena conectada:
Entonces,
y
Este ejemplo proporciona un límite superior para la constante de Cheeger h ( G N ) , que también tiende a cero cuando N → ∞ . En consecuencia, consideraríamos una red en anillo como muy "cuello de botella" para N grande , y esto es altamente indeseable en términos prácticos. Solo necesitaríamos que fallara una de las computadoras en el anillo, y el rendimiento de la red se reduciría considerablemente. Si dos computadoras no adyacentes fallaran, la red se dividiría en dos componentes desconectados.
Desigualdades de Cheeger
La constante de Cheeger es especialmente importante en el contexto de los gráficos de expansión, ya que es una forma de medir la expansión de los bordes de un gráfico. Las denominadas desigualdades de Cheeger relacionan la brecha de valores propios de un gráfico con su constante de Cheeger. Más explícitamente
en el cual es el grado máximo para los nodos en y es la brecha espectral de la matriz laplaciana del gráfico. [2]
Ver también
Referencias
- ^ Mohar, Bojan (diciembre de 1989). "Números isoperimétricos de gráficos". Revista de Teoría Combinatoria, Serie B . 47 (3): 274-291. doi : 10.1016 / 0095-8956 (89) 90029-4 . hdl : 10338.dmlcz / 128408 .
- ^ Montenegro, Ravi; Tetali, Prasad (2006). "Aspectos matemáticos de los tiempos de mezcla en cadenas de Markov". Encontró. Tendencias Theor. Computación. Sci: 90–94. Cite journal requiere
|journal=
( ayuda )
- Donetti, L .; Neri, F. y Muñoz, M. (2006). "Topologías de red óptimas: expansores, jaulas, grafos Ramanujan, redes entrelazadas y todo eso". J. Stat. Mech . 2006 (08): P08007. arXiv : cond-mat / 0605565 . Código bibliográfico : 2006JSMTE..08..007D . doi : 10.1088 / 1742-5468 / 2006/08 / P08007 .
- Lackenby, M. (2006). "Escisiones de Heegaard, la conjetura y propiedad virtualmente de Haken (τ)". Inventar. Matemáticas . 164 (2): 317–359. arXiv : matemáticas / 0205327 . Código Bibliográfico : 2006InMat.164..317L . doi : 10.1007 / s00222-005-0480-x .