Propagación en grafos

Martín Peñalver, Anabel (2019). Propagación en grafos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Propagación en grafos
Author/s:
  • Martín Peñalver, Anabel
Contributor/s:
  • Hernández Peñalver, Gregorio
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2019
Subjects:
Freetext Keywords: Árbol oruga; Árbol langosta; Grafo unicíclico; Grafo cactus; Grafo MOP; Burning Problem; Firefigher Problem; Propagación; Caterpillar tree; Lobster tree; Unicycle graph; Cactus graph; MOP graph; Spread
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (618kB) | Preview

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.

More information

Item ID: 55597
DC Identifier: http://oa.upm.es/55597/
OAI Identifier: oai:oa.upm.es:55597
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 26 Jun 2019 10:25
Last Modified: 26 Jun 2019 10:25
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM