Propagación en grafos

Abstract

La propagación en grafos es un tema que ha sido bastante estudiado en los últimos años. Modela situaciones que podemos encontrar en la vida real como la propagación de una noticia en las redes sociales, de una pandemia, de un incendio o de un virus, ya sea en un contexto biológico o informático. Respecto a dicho tema, estudiamos dos tipos de problemas que reciben la denominación de “Firefighter Problem” y “Burning Graph Problem”. El primer problema se describe como un modelo determinista en tiempo discreto de la propagación de alguna de las situaciones descritas anteriormente en un grafo G=(V,A) pero con herramientas para controlar dicha propagación, las cuales reciben el nombre de bomberos. Tiene como objetivo principal maximizar el número de vértices salvados. “Burning Graph Problem” es, también, un proceso determinista cuya finalidad es quemar todos los vértices lo antes posible. A diferencia del problema anterior, no cuenta con ninguna herramienta de control. Este Trabajo de Fin de Grado se ha dividido en dos partes: La primera, un resumen (tipo “survey”), donde se han recopilado teoremas, lemas, corolarios y demostraciones sobre los dos problemas citados anteriormente. La segunda, un estudio algorítmico y combinatorio en distintos tipos de grafos en “Firefighter Problem” donde, además, también se han estudiado parámetros importantes como el número de supervivencia, la tasa y el mínimo daño esperado.---ABSTRACT---The propagation in graphs is a topic which has been studied during the last years. It models situations that can be found in real life, such as the spread of news on social media networks, pandemic, fire or virus, either in a biological or computer context. Regarding this topic, it will be studied two types of problems which receive the denomination of “Firefighter Problem” and “Burning Graph Problem”. The first problem is a deterministic, discrete-time model of the spread of any of the situations described above in a graph G=(V, A). However, it uses tools to control this expansion. These tools are firefighters. The main goal is saving the maximum plausible number of vertices. “Burning Graph Problem” is a deterministic, discrete-time model whose purpose is burning all nodes as soon as possible. Unlike the previous problem, this has not any control instrument. This paper has been divided into two parts. Firstly, there is a summary (type “survey”), where it has been collected theorems, lemmas, corollaries and proofs about the issues that have been gathered previously. Secondly, it can be found an algorithmic and combinatorial study in different kinds of graphs in the Firefighter Problem. Moreover, it has been studied important parameters, for instance, the surviving number, surviving rate, and the minimum expected damage.