Conceitos e técnicas da mecânica estatística e termodinâmica aplicados ao estudo dos grafos aleatórios

This dissertation briefly presents the random graphs and the main quantities calculated from them. At the same time, basic thermodynamics quantities such as energy and temperature are associated with some of their characteristics. Approaches commonly used in Statistical Mechanics are employed and rules that describe a time evolution for the graphs are proposed in order to study their ergodicity and a possible thermal equilibrium between them

Estudo da transição de fase da percolação através da entropia da informação

Various physical systems have dynamics that can be modeled by percolation processes. Percolation is used to study issues ranging from fluid diffusion through disordered media to fragmentation of a computer network caused by hacker attacks. A common feature of all of these systems is the presence of two non-coexistent regimes associated to certain properties of the system. For example: the disordered media can allow or not allow the flow of the fluid depending on its porosity. The change from one regime to another characterizes the percolation phase transition. The standard way of analyzing this transition uses the order parameter, a variable related to some characteristic of the system that exhibits zero value in one of the regimes and a nonzero value in the other. The proposal introduced in this thesis is that this phase transition can be investigated without the explicit use of the order parameter, but rather through the Shannon entropy. This entropy is a measure of the uncertainty degree in the information content of a probability distribution. The proposal is evaluated in the context of cluster formation in random graphs, and we apply the method to both classical percolation (Erd¨os- R´enyi) and explosive percolation. It is based in the computation of the entropy contained in the cluster size probability distribution and the results show that the transition critical point relates to the derivatives of the entropy. Furthermore, the difference between the smooth and abrupt aspects of the classical and explosive percolation transitions, respectively, is reinforced by the observation that the entropy has a maximum value in the classical transition critical point, while that correspondence does not occurs during the explosive percolation.

Estudo da transição de fase da percolação através da entropia da informação

Various physical systems have dynamics that can be modeled by percolation processes. Percolation is used to study issues ranging from fluid diffusion through disordered media to fragmentation of a computer network caused by hacker attacks. A common feature of all of these systems is the presence of two non-coexistent regimes associated to certain properties of the system. For example: the disordered media can allow or not allow the flow of the fluid depending on its porosity. The change from one regime to another characterizes the percolation phase transition. The standard way of analyzing this transition uses the order parameter, a variable related to some characteristic of the system that exhibits zero value in one of the regimes and a nonzero value in the other. The proposal introduced in this thesis is that this phase transition can be investigated without the explicit use of the order parameter, but rather through the Shannon entropy. This entropy is a measure of the uncertainty degree in the information content of a probability distribution. The proposal is evaluated in the context of cluster formation in random graphs, and we apply the method to both classical percolation (Erd¨os- R´enyi) and explosive percolation. It is based in the computation of the entropy contained in the cluster size probability distribution and the results show that the transition critical point relates to the derivatives of the entropy. Furthermore, the difference between the smooth and abrupt aspects of the classical and explosive percolation transitions, respectively, is reinforced by the observation that the entropy has a maximum value in the classical transition critical point, while that correspondence does not occurs during the explosive percolation.

Visualización interactiva de grafos con el programa Xglore

[ES] El presente manual describe el manejo de grafos de forma interactiva en el entorno 3D que proporciona el programa Xglore (http://sourceforge.net/projects/xglore/). Forma parte del proyecto “Nerthusv2: Base de datos léxica en 3D del inglés antiguo” patrocinado por el Ministerio de Ciencia e Innovación (nº: FFI08-04448/FILO).

SSI-Dijkstra+: Desarrollo de un sistema de resolución de la ambigüedad semántica basada en grafos

Este documento es la memoria de un Proyecto de Final de Carrera de la Ingeniería Técnica en Informática de Sistemas en la Facultad de Informática de San Sebastián que se encuadra en el procesamiento del lenguaje natural (PLN), el campo de la semántica y la desambiguación de palabras. El idioma del proyecto es el Español.

SSI-Dijkstra-Fast: Desarrollo de un sistema de resolución de la ambigüedad semántica basada en grafos

El proyecto desarrollará el algoritmo SSIDijkstra- Fast (una versión del SSI-Dijkstra) basándose en implementaciones del algoritmo existentes para versiones anteriores de UKB. UKB es una herramienta de desambiguación semántica basada en grafos. 2

Um algoritmo para geração de caminhos em grafos a partir de um vértice.

Revisão de conceitos sobre Grafos. Algoritmo. Complexidade. Exemplos de execução. Código fonte.

Análisis de las resoluciones de problemas de probabilidad condicional mediante grafos. Um ejemplo

En este trabajo mostramos el potencial de los grafos trinomiales como herramienta para el análisis de las resoluciones de problemas ternarios de probabilidad condicional. Mostramos el análisis de dos resoluciones correspondientes a sendos estudiantes de 4o de ESO resolviendo un problema de probabilidad condicional de nivel N0.

Teoría de grafos y geometría reticular: matemáticas elementales para el estímulo del talento matemático

El objetivo de esta charla es presentar algunos resultados recientes sobre teorías elementales en matemáticas para el desarrollo del talento en matemáticas. En particular, se mostrarán algunos resultados relacionados con la teoría de grafos y la teoría reticular, ambas, teorías matemáticas que han venido siendo adaptadas por el Grupo Yaglom de la Universidad Sergio Arboleda para los cursos de pretalentos y talentos en matemáticas.

Una introducción a la teoría de Grafos

Con Frecuencia encontramos artículos que hablan sobre los radicales cambios de la educación matemática y cómo esta se sigue enseñando de la misma forma y con el mismo enfoque que hace más de cien años. Lo que no se encuentra son propuestas nuevas ni textos que permitan otro enfoque de la materia. El siguiente artículo pretende mostrar una nueva propuesta para las aulas de clase. Usando un tema tan “sencillo” como es La Teoría de Grafos se quiere mostrar una opción de trabajo para estudiantes de educación media que permita abrir camino a problemas muy complicados partiendo de enunciados sencillos cuya solución es más cercana a un juego que a una demostración matemática.

El lenguaje de los grafos

Existen medios de comunicación universales como la música o el arte. La notación de las matemáticas también goza, afortunadamente, de cierta universalidad. Una parte de las matemáticas, la teoría de grafos, se ha mostrado, en los últimos tiempos, como una notación muy útil y unificadora en diversas disciplinas.

Resultados espectrais relacionados com a estrutura dos grafos

Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.

Grafos para todos

Dissertação de Mestrado, Matemática, Especialização em Matemática para o Ensino, Faculdade de Ciências e Tecnologia, Universidade do Algarve, 2007

Una breve introducci??n a la teor??a de grafos

Resumen basado en el del autor

Aplicaciones de la teoría de grafos a algunos juegos de estrategia.

Resumen basado en el de los autores