Conectividade do grafo aleatório de Erdös-Rényi e uma variante com conexões locais

Abstract

El objetivo de esta investigación es estudiar el umbral de conectividad del grafo aleatorio Erdös-Rényi y una extensión de este modelo agregando una topología simple con conexiones locales. Decimos que un grafo está conectado si existe un camino de aristas entre cualquier par de vértices. El grafo aleatorio de Erdös-Rényi con n vértices se obtiene conectando cada par de vértice con probabilidad p n ∈ (0, 1), independientemente de los otros. En este trabajo, estudiamos en detalle el umbral de conectividad en la probabilidad de conexión p n para grafos aleatorios Erdös-Rényi cuando el número de vértices n diverge. Para este estudio, revisamos algunas herramientas probabilísticas básicas (convergencia de variables aleatorias y métodos del primer y segundo momento), que también ayudarán a comprender mejor los resultados más complejos. Además, aplicamos los conceptos anteriores a un modelo con una topología simple, más específicamente estudiamos el comportamiento asintótico de la probabilidad de no tener vértices aislados, y discutimos la conectividad o no conectividad del grafo. Finalmente, mostramos la convergencia en distribución del número de vértices aislados para una distribución de Poisson del modelo estudiado.

Dizemos que um grafo e conectado se existe um caminho de arestas entre quaisquer par de vértices. O grafo aleatório de Erd os-R enyi com n vértices e obtido conectando cada par de vértice com probabilidade pn 2 (0; 1), independentemente dos outros. Neste trabalho, estudamos em detalhe o limiar da conectividade na probabilidade de conexão pn para grafos aleat órios Erd os-R enyi quando o n úmero de vértices n diverge. Para este estudo, revisamos algumas ferramentas probabilísticas básicas (convergência de variáveis aleatórias e Métodos do primeiro e segundo momento), que também irão auxiliar ao melhor entendimento de resultados mais complexos. Além disto, aplicamos os conceitos anteriores para um modelo com uma topologia simples, mais especificamente estudamos o comportamento assintótico da probabilidade de não existência de vértices isolados, e discutimos a conectividade ou não do grafo. Por mostramos a convergência em distribuição do número de vértices isolados para uma Distribuição Poisson do modelo estudado.