¿Por qué es importante el diámetro de un gráfico aleatorio?
Puedo ver que el diámetro de un gráfico, definido como la longitud del camino más largo y más corto, es una cantidad no trivial en un gráfico aleatorio , por ejemplo, el gráfico aleatorio$G(n,p)$formado por la adición de bordes entre$n$puntos independientemente con probabilidad$p$.
Pero, ¿qué lo hace tan matemáticamente significativo? ¿Qué relaciones tiene con las otras ideas gráficas fundamentales? Además, si agrego alguna restricción en el gráfico, como la distribución de grados o restricciones espaciales en los vértices (es decir, un gráfico geométrico aleatorio), ¿qué efecto tiene esto en la importancia del diámetro del gráfico?
Respuestas
El diámetro de la gráfica es significativo por derecho propio, al igual que el número cromático o grado máximo. Si desea que su gráfico modele una red, le indicará el número máximo de 'saltos' que se deben realizar para ir de un nodo a otro. Si su gráfico está incrustado geométricamente como, digamos, un gráfico donde cada borde es una línea recta de longitud 1, entonces el diámetro del gráfico (abstracto) es un límite superior en el diámetro del gráfico incrustado, considerado como un subconjunto de$\mathbb{R}^n$.
Dejar$D$Sea el diámetro de un gráfico,$n$su orden,$\Delta$su grado máximo y$\kappa$su conectividad. Algunas heurísticas generales sobre cómo se comporta el diámetro (estas son tendencias, no teoremas):
- Si un gráfico tiene un diámetro bajo y muchos vértices, entonces debe tener muchos bordes, y estos bordes deben distribuirse de una manera algo "uniforme" para no permitir que dos vértices estén muy separados.
- Si el diámetro del gráfico es muy grande en comparación con el número de vértices, entonces el gráfico tiene menos aristas.
- De manera similar a los puntos anteriores, el diámetro y el grado máximo juntos limitan el número total de vértices que puede tener un gráfico. Heurísticamente, no puede obtener más vértices de un gráfico que si crea un árbol de profundidad$D$que se ramifica aproximadamente$\Delta-1$veces en cada capa, con algunos bordes adicionales para cerrar las cosas. El estudio de este límite es el tema del problema del diámetro del grado .
- Mientras que el diámetro y el grado máximo limitan$n$desde arriba, el diámetro y la conectividad lo unían desde abajo. El límite se ve más o menos como$n \geq \kappa \cdot (D-1)$.
- El diámetro también restringe la circunferencia del gráfico. En resumen, si el diámetro es bajo y el gráfico contiene algún ciclo, debe contener un ciclo de corta duración.
Finalmente, el diámetro actúa como una buena restricción de complejidad. Si está tratando de estudiar alguna estructura o característica en gráficos generales y se está perdiendo irremediablemente, a menudo es útil considerar lo que sucede en los gráficos de diámetro 2 (especialmente si hay alguna otra restricción o clase de gráfico restringida que lo acompañe). ¡Lo que hace que sea bastante fortuito que casi todos los gráficos tengan un diámetro de 2!