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

• Ano de defesa: 2016
• Autor(a) principal: Bedia, Elizbeth Chipa
• Orientador(a): Gallo, Alexsandro Giacomo Grimbert
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de São Carlos; Câmpus São Carlos
• Programa de Pós-Graduação: Programa Interinstitucional de Pós-Graduação em Estatística - PIPGEs
• Palavras-chave em Português: Conectividade; Grafos aleatórios; Transição de fase; Probabilidade
• Palavras-chave em Inglês: Connectivity; Random graphs; Phase transition; Probability
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::PROBABILIDADE E ESTATISTICA::ESTATISTICA::FUNDAMENTOS DA ESTATISTICA
• Link de acesso: https://repositorio.ufscar.br/handle/20.500.14289/7493

We say that a graph is connected if there is a path edges between any pair of vertices. Random graph Erd os-R enyi with n vertices is obtained by connecting each pair of vertex with probability pn 2 (0; 1) independently of the others. In this work, we studied in detail the connectivity threshold in the connection probability pn for random graphs Erd os-R enyi when the number of vertices n diverges. For this study, we review some basic probabilistic tools (convergence of random variables and methods of the rst and second moment), which will lead to a better understanding of more complex results. In addition, we apply the above concepts for a model with a simple topology, speci cally studied the asymptotic behavior of the probability of non-existence of isolated vertices, and we discussed the connectivity or not of the graph. Finally we show the convergence in distribution of the number of isolated vertices for a Poisson distribution of the studied model.