• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.104.2019.tde-12082019-155714
Documento
Autor
Nombre completo
Elizbeth Chipa Bedia
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2016
Director
Tribunal
Gallo, Alexsandro Giacomo Grimbert (Presidente)
Coletti, Cristian Favio
Leonardi, Florencia Graciela
Título en portugués
Conectividade do grafo aleatório de Erdös-Rényi, e de uma variante com conexões locais
Palabras clave en portugués
Conectividade
Grafos aleatórios
Probabilidade
Transição de fase
Resumen en portugués
Dizemos que um grafo e conectado se existe um caminho de arestas entre quaisquer par de vértices. O grafo aleatório de Erdös-Rényi com n vértices e obtido conectando cada par de vértice com probabilidade pn ∈ (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ös-Rényi 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 m mostramos a convergência em distrubuição do número de vértices isolados para uma Distribuição Poisson do modelo estudado.
Título en inglés
Connectivity for the Erdös-Rényi random graph, and a variant with local connections
Palabras clave en inglés
Connectivity
Phase transition
Probability
Random graphs
Resumen en inglés
We say that a graph is connected if there is a path edges between any pair of vertices. Random graph Erdös-Rényi with n vertices is obtained by connecting each pair of vertex with probability pn ∈ (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ös-Rényi when the number of vertices n diverges. For this study, we review some basic probabilistic tools (convergence of random variables and methods of the first 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, specifically 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2019-08-12
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.