Look-up in Google Scholar
Title: Conectividade do grafo aleatório de Erdös-Rényi e uma variante com conexões locais
Advisor(s): Grimbert Gallo, Alexsandro Giacomo; Rodriguez, Pablo Martin
OCDE field: http://purl.org/pe-repo/ocde/ford#1.01.03
Issue Date: May-2016
Institution: Universidade Federal de São Carlos; Universidade de São Paulo
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.
Discipline: Ciencias naturales
Grade or title grantor: Universidade Federal de São Carlos - Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação
Grade or title: Magíster en Estadística
Register date: 27-Jul-2020

Files in This Item:
File Description SizeFormat 
Chipa_Bedia_E.pdf
  Restricted Access
Disertación (abierta en repositorio de origen)1.14 MBAdobe PDFView/Open Request a copy
Autorizacion.pdf
  Restricted Access
Autorización del registro169.97 kBAdobe PDFView/Open Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.