graduado en matemáticas e informática universidad ... · el primer problema se describe como un...

Graduado en Matemáticas e Informática

Universidad Politécnica de Madrid

Escuela Técnica Superior de

Ingenieros Informáticos

TRABAJO FIN DE GRADO

Propagación en grafos

Autor: Anabel Martín Peñalver

Director: Gregorio Hernández Peñalver

MADRID, JUNIO 2019

i

i

Agradecimientos En primer lugar, dar las gracias a mi familia, en especial a mi madre, por apoyarme

siempre y sobre todo en estos 4 años de Universidad. Sin ellos, nada de esto hubiese sido

posible.

Seguidamente, dar las gracias a Gregorio, por ayudarme y guiarme en todo lo que he

necesitado tanto en el TFG como a lo largo de las asignaturas que he cursado contigo.

Gracias por hacerme aprender y a la vez, disfrutar de este bonito tema como son los

grafos.

Y, por último, quería agradecer a todos mis amigos, tanto a los que han compartido

conmigo estos cuatro años aquí dentro, en especial a Paula Esteban quien siempre ha

estado ahí para ayudarme y hacerme reír cuando lo he necesitado, como a los que llevan

conmigo desde siempre. Espero seguir compartiendo mi camino con vosotros. Gracias,

Lydia por ser tan buena amiga y por aconsejarme y amenizarme este largo camino. Eres

un gran ejemplo de quien quiere, puede y, dentro de unos añitos tú también estarás

escribiendo esto, y yo, apoyándote como has hecho tú conmigo hasta ahora.

ii

ii

Resumen 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.

Palabras clave: árbol oruga, árbol langosta, grafo unicíclico, grafo cactus, grafo MOP,

Burning Problem, Firefigher Problem, propagación.

iii

iii

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.

Keywords: caterpillar tree, lobster tree, unicycle graph, cactus graph, MOP graph,

Burning Problem, Firefighter Problem, spread.

Indice general

1. Introduccion 11.1. Propagacion en Grafos. Cuestiones generales . . . . . . . . . . . . . . . . . 11.2. Objetivos del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3. Notacion y terminologıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Trabajos previos 52.1. Firefighter Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2. Burning Graph Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3. Firefighter Problem 113.1. Restricted NAE 3-SAT ∝ 3-T’-FIRE . . . . . . . . . . . . . . . . . . . . . 113.2. Algoritmo para grafos con ∆ = 3 y el fuego con origen en un vertice de

grado 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3. Arbol oruga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4. Arbol langosta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5. Grafo unicıclico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.6. Grafo cactus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.7. Grafo MOP (Maximal Outerplanar Graph) . . . . . . . . . . . . . . . . . . 67

4. Burning Graph Problem 77

5. Conclusiones 80

Bibliografıa 81

5

Capıtulo 1

Introduccion

1.1. Propagacion en Grafos. Cuestiones generales

Los problemas de propagacion de grafos modelan situaciones que se llevan a cabo enla vida real: propagacion de una noticia, por ejemplo, en las redes sociales (Facebook,Twitter, etc ...), de una pandemia, de un incendio o de un virus, ya sea a nivel biologicoo informatico [9],[17]. Ante estas situaciones, estudiaremos dos tipos de problemas: “Fi-refighter Problem“ y “Burning Graph Problem“.

“Firefighter Problem“ fue introducido por Bert Hartnell en 1995 en la Conferenciade Manitoba sobre Matematica Combinatoria y Computacion [7].Se describe como un modelo determinista en tiempo discreto de la propagacion de algunade las situaciones descritas anteriormente en un grafo G = (V,A). Los vertices representana todo aquello donde una enfermedad, un virus informatico o un fuego se puede expandir,es decir, si hablamos de manera especıfica nos referimos a grupos de personas, ordena-dores, arboles, etc... y las aristas establecen la union entre ellos [7]. En este proceso, sedisponen de herramientas para controlar dicha propagacion, las cuales reciben el nombrede bomberos.A continuacion, vamos a describir este problema centrandonos en el caso de un fuego:

Sea un grafo G = (V,A) y t el numero de pasos necesarios para controlar el fuego [16]:

En t = 0 el fuego aparece en uno de los vertices de G.

En cada intervalo (t, t + 1], i ≥ 0 un bombero protege un vertice que, obviamente,aun no ha sido alcanzado por el fuego y, a continuacion el fuego se expande a losvertices adyacentes que no estan protegidos.

El proceso acaba cuando el fuego no se puede expandir mas.

En la siguiente pagina se muestra un ejemplo de “Firefighter Problem“:

1

CAPITULO 1. INTRODUCCION 2

r

(a) El fuego empieza en r.

r

1

1

1

(b) Anadimos un bombero (azul) y el fuegose expande por los vertices adyacentes nocontrolados.

r

1

1

1

2

2

(c) Anadimos otro bombero y el fuego seexpande por el vertice adyacente no contro-lado.

r

1

1

1

2

2

3

(d) Anadimos un ultimo bombero y el fuegoqueda controlado. El proceso se acaba.

Figura 1.1: Firefighter Problem

El fuego se ha controlado en 3 pasos y solo nos han hecho falta utilizar 3 bomberospara ello. Unicamente se han quemado 4 vertices.

Podemos plantear los siguientes objetivos [7]:

Maximizar el numero de vertices salvados.

Minimizar el numero de vertices quemados.

Minimizar el numero de pasos necesarios para controlar el fuego.

Determinar si todos los vertices en un conjunto especıfico pueden prevenirse delfuego.

Averiguar el numero de bomberos necesarios para salvar una parte o un numeroespecıfico de vertices a partir de un subconjunto de V .

“Firefighter Problem“ es un problema NP-Completo incluso para un bombero y paraarboles [9].

Anos mas tarde, se comenzo a estudiar “Burning Graph Problem“. Se describecomo un proceso determinista cuyo objetivo es quemar todos los vertices lo antes posible[2]. A diferencia del problema anterior, este no cuenta con ninguna herramienta de control.Esta inspirado en “Firefighting“, “Graph Cleaning“ y “Graph bootstrap percolation“[17]. El primero se ha definido anteriormente. “Graph Cleaning“ es una combinacionde busqueda de aristas en un grafo simple y “Chip-firing game“ un juego de un solojugador donde tenemos unas pilas las cuales comienzan con un numero concreto de fichas.


Cualquier pila va a tener como mınimo dos fichas y pueden enviar una de ellas a una delas pilas de cada lado. Una vez que todas las pilas tengan una sola ficha, el juego termina[12],[1]. “r-neighbour bootstrap percolation“ fue introducido en 1970 por Chalupa, Leathy Reich y se define como la propagacion de activacion (o de la infeccion) de un grafo G[11]. Posteriormente, lo describiremos con mayor detalle.

1.2. Objetivos del trabajo

El trabajo se centra en el analisis de ambos problemas. Se realizara un estudio com-binatorio y algorıtmico de dichos problemas con la diferencia que en el caso de “BurningGraph Problem“ sera sin estrategias de control y en“Firefighter Problem“ se tendran encuenta. En ambos, se estudiaran de manera particular algunas variantes de dichos pro-blemas en algunas clases de grafos (arboles y triangulaciones) y se elaborara un “survey“sobre los problemas de propagacion en grafos [9].

1.3. Notacion y terminologıa

En este apartado vamos a definir ciertos conceptos que se utilizaran posteriormente yque en la parte anterior de la introduccion no han sido explicados.

Grafo [18]: Es un par G = (V,A), donde V es un conjunto finito no vacıo acuyos elementos llamaremos vertices o nodos y A es una familia finita de pares noordenados de vertices del conjunto V a cuyos elementos llamaremos aristas o arcos.Ademas, el orden de un grafo se define como |V |.

Arbol [15]: Un arbol T = (V,A) es un grafo conexo y acıclico de n vertices y maristas, siendo m = n− 1. Llamamos hojas a los vertices de grado uno.

Vertice adyacente o vecino (neighbour): Sea G = (V,A) un grafo. Se dice quex es un vertice adyacente o vecino de v si existe una arista que una a ambos vertices.El conjunto de vecinos de v se denota N(v). Y si se incluye el propio vertice v lodesignamos con N [v].

Arbol binario completo [6]: Un arbol es un arbol binario completo si cada verticeque no es hoja tiene dos hijos. Un arbol binario completo de altura h tiene exacta-mente 2h+1 − 1 vertices de los cuales 2h son hojas.

Grafo periplano: Es un grafo planar que admite una representacion plana en laque todos sus vertices estan en la cara exterior (o no acotada).

Subgrafo isometrico: Un subgrafo H ⊂ G se dice que es un subgrafo isometricosi para cada par de vertices de H, todos los vertices y aristas de un camino mınimoentre x, y en G siguen estando en H. Es decir, distH(x, y) = distG(x, y).

Bosque [19]: Es un grafo acıclico cuyas componentes conexas son arboles.

Camino [20]: Es un arbol con dos vertices de grado 1 y el resto de grado 2. Serepresenta como Pn al camino formado por n vertices.

Ciclo [18]: Es un camino cerrado. Se representa como Cn al ciclo de n vertices.


Grafo hipercubo n-dimensional: Es el grafo cuyos vertices son las cadenas delongitud n de ceros y unos, y en el que dos de estas cadenas son adyacentes si difierensolo en una posicion. Se representa como Qn al cubo de 2n vertices.

Distancia [18]: Sean G = (V,A) un grafo (o digrafo) ponderado y u y v verticesde dicho grafo. Se llama distancia de u a v, d(u, v), a la mınima longitud de loscaminos que unen u con v. Si @ camino de u a v se dice que d(u, v) =∞.

Grado de un vertice v [2]: Numero de aristas que lo tienen como extremo. Sedesigna como d(v). Se define como grado maximo de un grafo G, al mayor terminode la sucesion de grados de G y su notacion es la siguiente: ∆(G).

Problema perteneciente a la clase NP [10]: Se dice que un problema pertenecea la clase NP si se puede verificar en tiempo polinomico.

Problema NP-duro [10]: Se dice que un problema H es NP-duro si cualquierproblema de la clase NP puede transformarse polinomicamente a H, es decir, siresolviendo H se pueden resolver todos los problemas de la clase NP.

Problema NP-Completo [10]: Decimos que un problema es NP-Completo sipertenece a la clase NP y es NP-duro.

Capıtulo 2

Trabajos previos

Este capıtulo tiene como objetivo hacer una recopilacion sobre resultados que tenemoshasta ahora de la propagacion en grafos.

2.1. Firefighter Problem

Uno de los objetivos que se han definido anteriormente es que este proceso consistıaen maximizar el numero de vertices que se pueden salvar del incendio, o lo que es lomismo, minimizar el numero de vertices quemados. Gracias a esto, podemos introducir lasiguiente proposicion que nos da unos resultados para grafos elementales.

Proposicion 1 [7] El numero de vertices salvados en un grafo G, donde el fuego puedeaparecer en cualquier vertice del conjunto F , se denota de la siguiente manera: MV S(G,F ).

1. Para n ≥ 2, MV S(Kn, r) = 1

2. Para n ≥ 3, MV S(Cn, r) = n− 2

3. Para n ≥ 2, MV S(Pn, r) =

{n− 1 si r es una hojan− 2 en cualquier otro caso

4. Para n ≥ 2, MV S(Qn, r) = n

A continuacion, se puede apreciar un ejemplo de cada uno de los casos de la proposicionanterior.

r

(a) El fuego empieza en r.

r

1

11

1

(b) Podemos salvar unvertice.

Figura 2.1: K5

5

CAPITULO 2. TRABAJOS PREVIOS 6

r

(a) El fuego empiezaen r

r

1

1

(b) Anadimos unbombero. El fuegose expande por losvertices adyacentesno controlados.

r

1

12

(c) Podemos salvar 3vertices, es decir, n−2.

Figura 2.2: C5

r

(a) El fuego empieza en un extemo del camino.

r 1

(b) Podemos salvar 3 vertices es decir, n− 1.

Figura 2.3: P4

r

(a) El fuego empieza en un vertice de grado 2.

r1 1

(b) Anadimos un bombero. El fuego se expandepor el vertice adyacente no controlado.

r1 1 2

(c) Podemos salvar 2 vertices, es decir, n− 2.

Figura 2.4: P4

r

(a) El fuego empiezaen r.

r 1

1

1

(b) Anadimos un bom-bero. El fuego se expan-de por los vertices adya-centes no controlados.

r 1

1

1

2

2

2

(c) Anadimos un bom-bero. El fuego se expan-de por los vertices adya-centes no controlados.

r 1

1

1

2

2

2

3

(d) Podemos salvar 3vertices, es decir, n.

Figura 2.5: Q3


Aunque para los casos anteriores, hemos visto que hallar el maximo numero de verticesque se pueden salvar es “sencillo“, Finbow et al. han demostrado que es un problema NP-completo incluso para arboles cuyo grado maximo es 3. Por otro lado, Hartnell y Li hanprobado que un “simple greedy method“ para arboles es un algoritmo 1/2-aproximado yMacGillivray y Wang han dado una formulacion de programacion entera para arboles yresolvieron el problema en tiempo polinomico para algunas subclases de arboles. Reciente-mente, Cai, Verbin y Yang han obtenido un algoritmo (1−1/e)-aproximado para arboles,basados en programacion lineal y de redondeo aleatorio. Ademas, otros autores han con-siderado varios aspectos, como por ejemplo: el numero de bomberos que necesitamos paracontener el fuego para retıculas d-dimensionales [16].

Otra de las cuestiones que se ha estudiado es el numero de supervivencia (survivingnumber) de un vertice v, la tasa de supervivencia (surviving rate) de un grafo G yel (mınimo) dano esperado (expected damage). El primer parametro se define como elmaximo numero de vertices que un bombero puede salvar en G cuando el fuego apareceen v. Lo expresaremos como sn(v). El segundo parametro se define como el porcentajemedio de vertices que pueden ser salvados cuando el fuego aparece de manera aleatoriaen un vertice del grafo. Lo indicaremos como ρ(G) [16]:

ρ(G) =1

n2

∑v∈V

sn(v)

El tercero fue introducido por Finbow et al. y se define de la siguiente manera [16]:

ed(G) =1

n

∑v∈V

(n− sn(v))

Por ejemplo:

ρ(Pn) = 1− 2

n+

2

n2siendo n ≥ 2

ρ(Cn) = 1− 2

n

ρ(G) > 1−√

2

nsi G es un arbol con n vertices

ρ(G) >1

6si G es un grafo periplano.

Posteriormente, se describira un algoritmo para grafos buenos y para arboles cuyo fuegoempieza en un vertice de grado 2 pero el grado maximo del arbol es 3. Se definiranestrategias para hallar el numero mınimo de vertices quemados en orugas, langostas,unicıclicos, cactus y MOPS serpentinos y se mostraran ejemplos de casos donde el fuegoes imposible de controlar.


2.2. Burning Graph Problem

En la actualidad, el uso de las redes sociales ha aumentando notablemente. Cada vezhay mas personas que lo usan como medio de informacion o de entretenimiento. En estetipo de situaciones, podemos comprobar que una noticia, una fotografıa, un vıdeo o unmeme se comparten por todo el mundo, teniendo como objetivo que lo hagan lo masrapido posible. “Burning Graph Problem“ modela este tipo de situaciones. Se describe dela siguiente manera [2]:Sea un grafo G = (V,A) simple, no dirigido y finito y sea t el numero de pasos necesariospara quemar un grafo:

Si t = 0 todos los vertices estan sin quemar

Para cada t ≥ 1, quemamos un nuevo vertice que no esta quemado. En cada verticequemado, se queman cada uno de sus vecinos en el paso t+1. Una vez que un verticese quema, se mantiene en ese estado hasta el final.

El proceso acaba cuando todos los vertices estan quemados [2].

Respecto a la velocidad de contagio de este problema se mide mediante el numero ar-diente (burning number), b(G). Cuanto menor sea, mayor es la velocidad de propagacion.Podemos encontrar diferentes definiciones sobre dicho numero:

Definicion 2 [13]

Dado un grafo G = (V,A), definimos como numero ardiente el mınimo numero depasos que se necesita para quemar dicho grafo.

Definicion 3 [2], [13]

Dado un grafo G = (V,A), definimos como numero ardiente la longitud de la sucesionardiente mas corta. Siendo sucesion ardiente (burning sequence) la sucesion de quemarun grafo G en k pasos (x1, x2, ..., xk).

Definicion 4 [14], [13]

Dado un grafo G = (V,A), definimos como numero ardiente el tamano del mınimoconjunto dominante con radio de dominio creciente. Siendo el conjunto dominante de G,un subconjunto D ⊂ V tal que ∀ x ∈ V y x /∈ D es adyacente a al menos un vertice deD.

A continuacion, se muestra un ejemplo de “Burning Graph Problem“:


(a) Grafo G

1

(b) Elegimos un vertice paraquemar

1

2

22

2

2

(c) El fuego se expande

1

2

22

2

2

2

(d) Elegimos otro vertice paraquemar

1

2

22

2

2

2

33

(e) El fuego se expande

1

2

22

2

2

2

33

3

(f) Todo el grafo esta quemado

Figura 2.6: Burning Graph Problem en G

Como se puede apreciar en el ejemplo b(G) = 3 porque es el mınimo numero depasos en el que G se ha quemado. Adicionalmente, se han obtenido resultados para grafoscompletos o para caminos siendo b(Kn) = 2 y b(Pn) =

√n [17].

(a) Grafo K5

1

(b) Elegimos un verticepara quemar

1

2

22

2

(c) Todo K5 esta quemadoen 2 pasos

Figura 2.7: Burning Graph Problem en K5


(a) Grafo P16

1

(b) Elegimos un vertice para quemar

12 2

(c) El fuego se expande

12 2 2

(d) Elegimos un vertice para quemar

12 2 2 3 333

(e) El fuego se expande

12 2 2 3 333 3

(f) Elegimos un vertice para quemar

12 2 2 3 333 34 4 4 4 4 4

(g) El fuego se expande

12 2 2 3 333 34 4 4 4 4 44

(h) Todo P16 esta quemado en 4 pasos

Figura 2.8: Burning Graph Problem en P16

Respecto a este parametro se ha profundizado bastante. Mitsche et al. estudiaron unavariante del numero ardiente donde se hace uso de una regla probabilıstica. Aunque Bessyet al. se centraron en hallar el numero ardiente en arboles, probaron que para cualquiergrafo conexo de n vertices el numero ardiente es, a lo sumo, b(G) = 2d

√ne− 1 y conjetu-

raron que, como mucho, podrıa ser b(G) = d√ne. Posteriormente, Land y Lu mejoraron

ligeramente la cota superior a

√6

2

√n y Sim et al. estudiaron dicho parametro para el

famoso grafo de Petersen. Por ultimo, Bonato et al. probaron que calcular el numero ar-diente es un problema NP-duro incluso para arboles.Debido a este problema, para cualquier grafo se introdujo un algoritmo polinomico conuna razon constante de aproximacion, a lo sumo 3 y para un arbol dicho algoritmo se hamejorado para que la razon de aproximacion sea 2. En el caso de bosques de caminos seha elaborado un algoritmo basado en programacion dinamica que obtiene una solucionoptima en tiempo polinomico [4].

Capıtulo 3

Firefighter Problem

3.1. Restricted NAE 3-SAT ∝ 3-T’-FIRE

En esta seccion vamos a realizar la construccion de un arbol a partir de una expresionbooleana para demostrar que:

RESTRICTED NAE 3-SAT ∝ 3-T’-FIRE

En primer lugar, vamos a describir los dos problemas de decision citados anteriormente:

RESTRICTED NAE 3-SAT [6]Instancia: Sea un par ordenado (B,C) que consiste en un conjunto de variables boo-leanas B y en un conjunto de clausulas C sobre B en forma normal conjuntiva, donde|B| = 2m para algun entero m ≥ 2, la mitad de las clausulas de C no contienen literalesnegativos y las clausulas restantes se obtienen reemplazando cada literal con su negacion.Pregunta: ¿Existe un valor de verdad asignado a B tal que toda clausula que se encuen-tra en C contiene al menos un literal verdadero y uno falso?

3-T’FIRE [6]Instancia: Sea un arbol T con raız r tal que d(r) = 2m + 2 para algun entero positivo my el resto de vertices de T tienen grado a lo sumo 3, y un entero positivo k.Pregunta: Si el fuego empieza en r, ¿Existe una estrategia en la que obtengamos, comomucho, k vertices quemados?

Una vez descritos, se comienza con la demostracion.

Para empezar, las expresiones booleanas para NAE 3-SAT restringido cumplen que:

A lo sumo, tiene que haber 3 literales por clausula.

Cada clausula tiene, al menos, un literal verdad y uno falso.

Hay 2m variables.

La mitad de las clausulas no tienen negaciones y la otra mitad se obtienen de estasnegando todas las variables.

11

CAPITULO 3. FIREFIGHTER PROBLEM 12

La construccion del arbol tiene un alto grado de dificultad:

La entrada de datos para nuestro ejemplo NAE 3-SAT restringido es:

E = (x1+x2+x4)(x1+x3+x4)(x′

1+x

′

2+x

′

4)(x′

1+x

′

3+x

′

4)(x1+x2+x4)(x

′

1+x

′

2+x

′

4)

C1 C3 C2 C4 C1 = C5 C2 = C6

El conjunto de variables booleanas se define de la siguiente forma:

B = {x1, x2, x3, x4} con y b = 2m−1 = 4 siendo m = 3 en este caso.

El conjunto de clausulas se describe ası:

C = {C1, C2, C3, C4, C5, C6} con n = 6 y p = dlog2 ne+ 2 = 5

Se puede apreciar que dos clausulas se han duplicado porque n > b ≥ 4.

La construccion se va a generar en 2 fases:

1. Se construye un arbol (T1, r) con raız r de altura b + p = 4 + 5 = 9 y grado enr d(r) = 2m + 2 = 10. Al vertice r se le anaden dos caminos de longitud i parai = 1, 2, ..., b y dos caminos de longitud b + 1 = 5. El resultado que conseguirıamoses el siguiente:

x0

x′

0

x1x′

1

x2x′

2

x3 x′

3

x4 x′

4

Ahora, de x0 y de x′0 colgamos arboles binarios completos de altura p− 1 = 4.

x0x′

0

A las hojas de los arboles cuyo vertice raız es x0 y x′0 se denominan, respectivamente:

tx0,1, tx0,2, ..., tx0,2p−1

tx′0,1, tx′0,2, ..., tx′0,2p−1


Para todo xi y x′i siendo 1 ≤ i ≤ 4 tambien colgamos arboles binarios completospero de altura p = 5.

xi x′

i

A las hojas de los arboles cuyo vertice raız es xi y x′i siendo i 1 ≤ i ≤ 4 se denominan,respectivamente:

txi,1, txi,2, ..., txi,2p

tx′i,1, tx′i,2, ..., tx′i,2p

El numero de vertices de T1 es:

|V (T1)| = 1 + b(b+ 1) + 2b(2p+1 − 2) + 2pb(b− 1) + 2(b+ 1) + 2(2p − 2) =

= 1 + 20 + 496 + 384 + 10 + 60 = 971

2. Construimos el arbol (T, r). En cada hoja tx0,2p−1 y tx′0,2p−1 siendo p 1 ≤ p ≤ 5 seanaden dos hijos y, en cada uno de ellos, un arbol escalera (ladder tree) LT (3n+ 1).Como n = 6, el arbol escalera sera un LT (19), es decir, tendra 39 vertices porqueuna escalera tiene 2n+ 1 vertices y la altura de dicho arbol sera 19.

tx0,1

Dos hijos

Arboles

escalera

t′x0,1Dos hijos

Arboles

escalera

En cada hoja txi,2p y t′xi,2psiendo p 1 ≤ p ≤ 5 para i 1 ≤ i ≤ b = 4 y para j

1 ≤ j ≤ n = 6.


Si xi esta en la clausula Cj ponemos el arbol serpiente ST (3n + 2, 3j − 1) entxi,j y ST (3n+ 2, 3j) en tx′i,j.

Si x′i esta en la clausula Cj ponemos el arbol serpiente ST (3n + 2, 3j − 1) entx′i,j y ST (3n+ 2, 3j) en txi,j.

En las hojas restantes de T1 ponemos la escalera LT (3n+ 2).

Un grafo serpiente S(c, e) tiene 2c− 1 vertices, de los cuales 2e pertenecen al unicociclo que contiene a a y b. Dicho grafo y su arbol tiene la siguiente forma:

a

b

a

b

Figura 3.1: Grafo y arbol serpiente

El numero de vertices de (T, r) es:

|V (T )| = |V (T1)|+2p(6n+3)+2b2p(6n+4)−12b = 971+32·39+8·32·40−48 = 12411

El numero de vertices quemados k de (T, r) es:

k = |V (T )| − (b∑

i=1

[2p(6n+ 6 + b− i)− 1] +

p∑i=0

[2p−i(6n+ 4)− 1] + 9n2 +15n

2+ 1) =

= 12411− (5564 + 2514 + 370) = 3963

La altura d de (T, r) es:

d = b+ p+ 3n+ 2 = 4 + 5 + 18 + 2 = 29

3.2. Algoritmo para grafos con ∆ = 3 y el fuego con

origen en un vertice de grado 2

Esta seccion ha sido recopilada de la siguiente fuente: [6]


“Firefighter Problem“ es un problema NP-completo para grafos G = (V (G), A) con∆ = 3 y el vertice donde se origina el fuego, r con d(r) = 3.A continuacion, se describe un algoritmo para arboles con ∆ = 3 y d(r) ≤ 2 y para grafosque solo contengan un vertice de grado 1, ∆ = 3 y d(r) ≤ 2. Segun el grado de r seactuara de una forma u otra:

Si d(r) = 1, se anade un bombero en el vertice adyacente a r y el proceso ya estarıacontrolado.

Si d(r) = 2 definimos 3 conjuntos:

• V1: conjunto de vertices de grado 1 en G.

• V2: conjunto de vertices de grado 2 en G.

• Vc: conjunto de vertices que pertenecen a un ciclo en G.

Para un vertice u ∈ Vc , C(u) es el ciclo mas pequeno que contiene a u.

Posteriormente, se define una funcion f : (V1 ∪ V2 ∪ Vc)→ Z+:

f(u) =

{d(u, r) + 1 si u ∈ V1 ∪ V2

d(u, r) + C(u)− 1 si u ∈ Vc \ V2Estrategia: Para algun u ∈ V1 ∪ V2 ∪ Vc tal que f(u) = min{f(x)|x ∈ (V1 ∪ V2 ∪ Vc)}

Caso 1:

Si u ∈ V1∪V2, tenemos que encontrar el camino mas corto desde el origen del fuego,r, hasta u. Este camino se llamara P . En cada turno, anadimos un bombero en unvertice que sea adyacente a un vertice quemado y que no se encuentre en P .

Si u ∈ V2 en cada turno f(u), se agrega un bombero en el vertice vecino de u el cualno este quemado. Obviamente, tendremos f(u) vertices quemados.

Caso 2:

Si u ∈ Vc \ V2, en cada turno desde 1 hasta d(r, u), se anade un bombero en elvertice adyacente a un vertice quemado y que no se encuentre en P . En cada turnod(r, u)+1, defendemos un vertice no quemado en C que tenga como vecino un nodoquemado.

Seguidamente, se presentan dos ejemplos de aplicacion del algoritmo y otro de un arbolen el que el fuego no se puede controlar.


r

(a) El incendio se origina en r.

r

C3 C3 C3

C3

1C8C82

2

C8C3

C3

(b) Identificamos el grado de cada vertice y elmınimo ciclo al que pertenecen.

r

C3 C3 C3

C3

1C8C82

2

C8C3

C3

2

45 6

5

65

2 9 4

(c) Etiquetamos todos los vertices (excepto r)segun la funcion f que hemos definido anterior-mente.

r

C3 C3 C3

C3

1C8C82

2

C8C3

C3

2

45 6

5

65

2 9 41

1

(d) Anadimos un bombero y el fuego se expande.

r

C3 C3 C3

C3

1C8C82

2

C8C3

C3

2

45 6

5

65

2 9 41

1

2

(e) El proceso finaliza.

Figura 3.2: Algoritmo en grafo “bueno“


r


r

4 4

3

3

5 5

4 4

(b) Etiquetamos todos los vertices (excepto r y cu-yo grado sea ≥ 3) segun la funcion f que hemosdefinido anteriormente.

r

4 4

3

3

5 5

4 4

11

(c) Anadimos un bombero y el fuego se expande.

r

4 4

3

3

5 5

4 4

11

2 2

(d) El proceso finaliza.

Figura 3.3: Algoritmo en arbol

r



r

1

11

(b) Anadimos un bombero y el fuego se expande.

r

1

11

2

2 22

(c) Anadimos un bombero y el fuego se expande.


r

1

1 1

22 2 2

333

3

3 3

(d) Anadimos un bombero y el fuego se expande.

r

1

1 1

22 2 2

333

3

3 3

4

4

4

4

4

4

4

4

(e) Anadimos un bombero y el fuego se expande.


r

1

1 1

22 2 2

333

3

3 3

4

4

4

4

4

4

4

4

5

5

5

5 5

5

(f) Anadimos un bombero y el fuego se expande.

r

1

1 1

22 2 2

333

3

3 3

4

4

4

4

4

4

4

4

5

5

5

5 5

5

6 66 6

(g) El proceso finaliza.

Figura 3.4: Ejemplo de Firefighter Problem no controlable


Como podemos apreciar en la figura 3.3, practicamente una rama entera desde la raızdel arbol se quema sin ningun tipo de control. Si el arbol fuese todavıa mas grande nose podrıa parar, ya que el proceso finaliza porque ya no hay mas vertices que se puedanquemar.

A continuacion, se recopilan unos lemas y corolarios que se han obtenido tras la des-cripcion del algoritmo.

Lema 5 [6] Dado un grafo G = (V (G), A) con ∆ ≤ 3 y d(r) ≤ 2, ∃ una solucion optimapara Firefighter Problem en el que un vertice adyacente a un quemado es defendido encada paso.

Teorema 6 [6] La estrategia del algoritmo para grafos con ∆ = 3 y el fuego con origenen un vertice de grado 2 nos da una solucion optima.

Corolario 7 [6] Sea un grafo G = (V (G), A) con ∆ ≤ 3 y d(r) ≤ 2, siendo r el verticedonde se origina el fuego. El maximo numero de vertices que pueden ser salvados es|V (G)| −min{f(x)|x ∈ (V1 ∪ V2 ∪ Vc}.

Corolario 8 [6] Firefighter Problem se puede resolver en tiempo polinomico para grafoscon ∆ ≤ 3 y d(r) ≤ 2, siendo r el vertice donde se origina el fuego.

A continuacion, presentamos los resultados que hemos obtenido en el transcurso de estetrabajo para algunos tipos especiales de grafos: orugas, langostas, grafos unicıclicos ycactus.

3.3. Arbol oruga

Definicion 9 [15] Un arbol oruga es un arbol T = (V,A) donde ∃ un camino P al quellamaremos espina de la oruga tal que ∀ v ∈ V o bien v ∈ P o bien dist(v, x) = 1 paraalgun x ∈ P . Se dice que un vertice es pata si d(v) = 1.

Figura 3.5: Ejemplo de un arbol oruga

Ademas, estudiaremos el numero de vertices que se pueden quemar segun el grado delvertice donde se origina el fuego. Como hemos visto en el apartado 2.1 Firefighter Pro-blem, existen 3 conceptos importantes: numero de supervivencia sn(r), tasa de su-pervivencia ρ(G) y dano esperado ed(G). En cada caso, mostraremos los resultadosobtenidos tras estudiar dichos conceptos.

Lema 10 Sea G un arbol oruga, r el vertice donde se origina el fuego. Si d(r) = 1, elnumero de vertices quemados en G es 1.

La siguiente estrategia demuestra el lema 10:


1. Colocamos un bombero en el vertice adyacente a r. Por lo tanto, el fuego ya estarıacontrolado.

r

(a) El incendio se origina en r

r 1

(b) Paso 1

Figura 3.6: Firefighter problem en un arbol oruga

Lema 11 Sea G un arbol oruga de n vertices y r el vertice donde se origina el fuego. Sid(r) = 1, el numero de supervivencia es:

sn(r) = n− 1

Lema 12 Sea G un arbol oruga de n vertices y r el vertice donde se origina el fuego. Sid(r) = 1, la tasa de supervivencia es:

ρ(G) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− 1) =1

n2n(n− 1) = 1− 1

n

Lema 13 Sea G un arbol oruga de n vertices y r el vertice donde se origina el fuego. Sid(r) = 1, el mınimo dano esperado es:

ed(G) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− 1)) =1

n

n∑1

1 =1

nn = 1

Lema 14 Sea G un arbol oruga y r el vertice donde se origina el fuego. Si d(r) ≥ 2, elnumero de vertices quemados en G es |N(r)|.

La estrategia que se sigue a continuacion demuestra el lema anterior:

1. Colocamos un bombero en el vertice adyacente a r con mayor numero de hojas dela espina.

2. El fuego se expande a los vertices no controlados vecinos a r.

3. Colocamos el segundo bombero en el vertice de la espina de la oruga adyacente aun quemado. Por lo tanto, ya tendrıamos controlado el incendio con dos bomberosque se encuentran situados de manera opuesta a distancia 1 y 2 de r.

r


r1

(b) Paso 1r1

1

1

(c) Paso 2

r11

1

2

(d) Paso 3

Figura 3.7: Firefighter problem en un arbol oruga


Lema 15 Sea G un arbol oruga de n vertices y r el vertice donde se origina el fuego. Sid(r) ≥ 2, el numero de supervivencia es:

sn(r) = n− |N(r)|

Lema 16 Sea G un arbol oruga de n vertices y r el vertice donde se origina el fuego. Sid(r) ≥ 2, la tasa de supervivencia es:

ρ(G) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− |N(r)|) =1

n2n(n− |N(r)|) = 1− |N(r)|

n

Lema 17 Sea G un arbol oruga de n vertices y r el vertice donde se origina el fuego. Sid(r) ≥ 2, el mınimo dano esperado es:

ed(G) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− |N(r)|)) =1

nn|N(r)| = |N(r)|

3.4. Arbol langosta

Definicion 18 Un arbol langosta es un arbol T = (V,A) donde ∃ un camino P tal que ∀v ∈ V o bien v ∈ P o bien dist(v, x) ≤ 2 para algun x ∈ P .

Figura 3.8: Ejemplo de un arbol langosta

A continuacion, estudiaremos el numero de vertices que se pueden quemar segun el gradodel vertice donde se origina el fuego. Ademas, Como hemos visto en el apartado 2.1Firefighter Problem, existen 3 conceptos importantes: numero de supervivencia sn(r),tasa de supervivencia ρ(G) y dano esperado ed(G), en cada caso, mostraremos losresultados obtenidos tras estudiar dichos conceptos.

Lema 19 Sea L un arbol langosta y r el vertice donde se origina el fuego. Si d(r) = 1,el numero de vertices quemados en L es 1.


1. Colocamos un bombero en el vertice adyacente a r. Por lo tanto, el fuego ya estarıacontrolado.

r


r 1

(b) Paso 1

Figura 3.9: Firefighter problem en un arbol langosta


Lema 20 Sea L un arbol langosta de n vertices y r el vertice donde se origina el fuego.Si d(r) = 1, el numero de supervivencia es:

sn(r) = n− 1

Lema 21 Sea L un arbol langosta de n vertices y r el vertice donde se origina el fuego.Si d(r) = 1, la tasa de supervivencia es:

ρ(L) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− 1) =1

n2n(n− 1) = 1− 1

n

Lema 22 Sea L un arbol langosta de n vertices y r el vertice donde se origina el fuego.Si d(r) = 1, el mınimo dano esperado es:

ed(L) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− 1)) =1

n

n∑1

1 =1

nn = 1

Lema 23 Sea L un arbol langosta y r el vertice donde se origina el fuego. Si d(r) ≥ 2,el numero de vertices quemados en L es |N [r]|.


1. Colocamos un bombero en el vertice adyacente a r con mayor numero de hojas dela espina.

2. El fuego se expande a los vertices no controlados vecinos a r.

3. Colocamos el segundo bombero en el vertice de la espina de la oruga de mayor gradoadyacente a un quemado.

4. El fuego se expande por el unico vertice que tiene posibilidad de hacerlo. Por lotanto, ya tendrıamos controlado el incendio con dos bomberos que se encuentransituados de manera opuesta a distancia 1 y 2 de r

r


r1

(b) Paso 1

r11

1

(c) Paso 2

r11

1

2

(d) Paso 3

r11

1

2

2

(e) Paso 4

Figura 3.10: Firefighter problem en un arbol langosta


Lema 24 Sea L un arbol langosta de n vertices y r el vertice donde se origina el fuego.Si d(r) ≥ 2, el numero de supervivencia es:

sn(r) = n− |N [r]|

Lema 25 Sea L un arbol langosta de n vertices y r el vertice donde se origina el fuego.Si d(r) ≥ 2, la tasa de supervivencia es:

ρ(L) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− |N [r]|) =1

n2n(n− |N [r]|) = 1− |N [r]|

n

Lema 26 Sea L un arbol langosta de n vertices y r el vertice donde se origina el fuego.Si d(r) ≥ 2, el mınimo dano esperado es:

ed(L) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− |N [r]|)) =1

nn|N [r]| = |N [r]|

3.5. Grafo unicıclico

Definicion 27 [21] Un grafo unicıclico es un grafo que contiene un solo ciclo.

Figura 3.11: Ejemplo de un grafo unicıclico

A continuacion, estudiaremos una serie de estrategias segun el grado del vertice donde seorigina el fuego y de sus adyacentes:

Lema 28 Sea U un grafo unicıclico, r el vertice donde se origina el fuego y x e y susdos vertices adyacentes. Si d(r) = 2 y, como mucho o d(x) > 2 o d(y) > 2, el numero devertices quemados es 2.


1. Colocamos un bombero en el vertice adyacente de mayor grado. Si d(x) = d(y) = 2se elige uno de los dos vertices arbitrariamente.

2. El fuego se expande al vertice no controlado vecino de r.

3. Anadimos el segundo bombero al vertice no controlado adyacente a un quemado yya tendrıamos el incendio controlado.


r

(a) El incendio se origi-na en r

r

1

(b) Paso 1

r

1

1

(c) Paso 2

r

1

1

2

(d) Paso 3

Figura 3.12: Firefighter problem en un unicıclico

Lema 29 Sea U un grafo unicıclico, r el vertice donde se origina el fuego y x e y sus dosvertices adyacentes. Si d(r) = 2 y d(x), d(y) > 2, el numero de vertices quemados varıasegun el tamano del arbol donde el fuego consiga expandirse.


1. Colocamos un bombero en el vertice adyacente de mayor grado. Si d(x) = d(y) seelige uno de los dos vertices arbitrariamente.

2. El fuego se expande al vertice no controlado vecino de r.

3. Tenemos 3 casos diferentes:

a) Si el grado del vertice del paso 2 es mayor o igual que 3 en el arbol, el fuego esimposible de controlar.

b) Si ∆ ≤ 3 y el vertice del paso 2 es de grado 2 en el arbol, utilizamos el algoritmodescrito anteriormente para estos casos (apartado 3.2).

c) Si es distinto a los dos casos planteados anteriormente se intenta controlarreduciendo al maximo el numero de vertices quemados.

4. Se anade un ultimo bombero en el ciclo para evitar que se expanda mas por ahı.

r

(a) El incendio se originaen r

r

1

(b) Paso 1

r

1

1

(c) Paso 2

r

1

1

2

2

3

2

3

(d) Paso 3

r

1

1

2

2

3

2

3

4

(e) Paso 4

Figura 3.13: Ejemplo de Firefighter problem en U


Lema 30 Sea U un grafo unicıclico y r el vertice donde se origina el fuego. Si d(r) > 2,el numero de vertices quemados varıa segun el tamano del arbol donde el fuego consigaexpandirse.


1. Tenemos 4 situaciones diferentes:

a) Si d(r) ≥ 3 en el arbol, el fuego es imposible de controlar.

b) Si d(r) = 2 en el arbol y ∆ ≤ 3, utilizamos el algoritmo descrito anteriormentepara estos casos (apartado 3.2).

c) Si d(r) = 1 en el arbol, se anade un bombero para evitar que se propague porel arbol.

d) Si d(r) = 2 en el arbol y el resto de vertices que forman el arbol tambien tienenel mismo grado, comparamos la cantidad de vertices que nos quedan por trataren el ciclo con la cantidad de vertices que nos quedan en el arbol. En la partemas numerosa, empezamos anadiendo un bombero por esa parte.

2. Si tenemos la situacion b) o c) se tienen que anadir, a lo sumo, dos bomberos maspara controlar el fuego por el ciclo. Si tenemos la situacion d) seguimos avanzandode tal forma que podamos obtener el mınimo numero de vertices quemados.

r


r 1

1

1

(b) Paso 1

r 1

1

1

3

2

2

(c) Paso 2

Figura 3.14: Ejemplo de Firefighter problem en U

3.6. Grafo cactus

Definicion 31 [8] Un cactus es un grafo G = (V,A) en el que cada arista pertenece a losumo a un ciclo. Cualquier par de ciclos comparten, como mucho, un vertice.

(a) Cactus sin aristas puentes (b) Cactus con aristas puentes

Figura 3.15: Ejemplos de grafos cactus


Grafo cactus sin aristas puente

A continuacion, clasificamos este tipo de cactus segun la cantidad de ciclos que con-tenga. Ademas, como hemos visto en el apartado 2.1 Firefighter Problem, existen 3conceptos importantes: numero de supervivencia sn(r), tasa de supervivenciaρ(G) y dano esperado ed(G). En cada caso, mostraremos los resultados obtenidostras estudiar dichos conceptos.

• Cactus con dos ciclos:

Lema 32 Sea G = (V,A) un grafo tipo cactus sin aristas puente formado pordos ciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2

y ∃ x ∈ V tal que x ∈ N(v) y d(x) = d(r) = 2, el incendio se puede controlarcon dos bomberos y siempre hay 2 vertices quemados.

La estrategia descrita demuestra lo dicho en el lema 32.

1. Se anade un bombero en el vertice adyacente a r de mayor grado

2. El fuego se propaga por el vertice adyacente no controlado

3. Anadimos el segundo bombero al vertice no controlado adyacente a unquemado y ya tendrıamos el incendio controlado.

r

(a) El incendio se origina en r ∈ G1

r

1

(b) Paso 1

r

1

1

(c) Paso 2

r

1

1

2

(d) Paso 3

Figura 3.16: Firefighter problem en un cactus con dos ciclos sin aristas puente

Lema 33 Sea G un cactus sin aristas puente de n vertices formado por dosciclos G1 y G2, r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 y ∃x ∈ V tal que x ∈ N(v) y d(x) = d(r) = 2, el numero de supervivencia es:

sn(r) = n− 2

Lema 34 Sea G un cactus sin aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 y ∃x ∈ V tal que x ∈ N(v) y d(x) = d(r) = 2, la tasa de supervivencia es:


ρ(G) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− 2) =1

n2n(n− 2) = 1− 2

n

Lema 35 Sea G un cactus sin aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 y ∃x ∈ V tal que x ∈ N(v) y d(x) = d(r) = 2, el mınimo dano esperado es:

ed(G) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− 2)) =1

n

n∑1

2 =2

nn = 2

Lema 36 Sea G = (V,A) un grafo tipo cactus sin aristas puente formado pordos ciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2, elnumero de vertices quemados, q(G), se puede acotar de la siguiente manera:

|C3|+ 1 ≤ q(G) ≤ 7

A continuacion, la siguiente estrategia demuestra el lema anterior.

1. Se anade un bombero en uno de los vertices adyacentes a r que se encuentraen el ciclo de mayor tamano. Si |G1| = |G2| se puede poner en cualquiera delos 4 vertices adyacentes. El fuego se propaga por los vertices adyacentes nocontrolados. Si el ciclo de tamano mas pequeno es un C3, hemos acabadopues el fuego ya esta controlado. En caso contrario, el proceso continua.

2. El segundo bombero se anade en el mismo ciclo que el bombero anteriorpero en el vertice adyacente a un quemado. Si el ciclo contiene 4 verticesel proceso se acaba. En caso contrario el fuego se sigue propagando por losvertices adyacentes no controlados.

3. El siguiente bombero se coloca en el otro ciclo porque el ciclo mas grandeesta controlado. Si es posible, el fuego se propagara a los vertices adyacen-tes no controlados.

4. Anadimos un cuarto bombero en el vertice adyacente a un quemado. In-dependientemente del tamano de los ciclos, el fuego estarıa totalmentecontrolado

Por tanto, a lo sumo, nos hacen falta 4 bomberos: dos de ellos en uno de losciclos a distancia 1 y 2 de r situandose de manera opuesta y los otros dos enel otro ciclo de la misma forma pero a distancia 3 y 4 de r.


Seguidamente, se puede apreciar la representacion de la cota inferior y superior,respectivamente:

r

(a) El incendio se originaen r ∈ G1

r

1

1

1

1

(b) Paso 1

Figura 3.17: Firefighter problem en cactus con ciclos de 3 vertices

r

(a) El incendio se origina enr ∈ G1 ∩G2

r

1

1

1

1

(b) Paso 1

r

1

1

1

1

2

2

2

(c) Paso 2

r

1

1

1

1

2

2

23

3

(d) Paso 3

r

1

1

1

1

2

2

23

3

4

(e) Paso 4

Figura 3.18: Firefighter problem en cactus con ciclos de 8 y 10 vertices

Lema 37 Sea G un cactus sin aristas puente de n vertices formado por dosciclos G1 y G2, r el vertice donde se origina el fuego. Si r ∈ G1∩G2, el numerode supervivencia es:

◦ sn(r) = n− 7

◦ sn(x) = n− 2 (siendo x ∈ V (G) y x 6= r)

Lema 38 Sea G un cactus sin aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2, la tasade supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−1)(n−2)+n−7] =

1

n2[n2−2n−n+2+n−7] =

=1

n2[n2 − 2n− 5] = 1− 2

n− 5

n2

Lema 39 Sea G un cactus de sin aristas puente de n vertices formado pordos ciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2, elmınimo dano esperado es:


ed(G) =1

n

∑z∈V

[n−sn(z)] =1

n[(n−1)(n−(n−2))+(n−(n−7))] =

1

n(2n+5) = 2+

5

n

• Grafo cactus con tres ciclos

Lema 40 Sea G = (V,A) un grafo tipo cactus sin aristas puente formado portres ciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ytiene como vertices adyacentes a u y v, siendo u ∈ G1 ∩G2 y v ∈ G1 ∩G3, elnumero de vertices quemados, q(G), se puede acotar de la siguiente manera:

|C3| ≤ q(G) ≤ 5

La estrategia siguiente prueba el lema 40.

1. Se anade un bombero en el vertice adyacente a r que se encuentre en elciclo de mayor tamano, es decir, en u o en v. Si |G2| = |G3| se puede poneren cualquiera de los dos. El fuego se propaga por el vertice adyacente a rque no ha sido controlado.

2. El segundo bombero es agregado en uno de los vertices adyacentes a unnodo quemado que se encuentra en el ciclo de segundo tamano mas grande.El fuego se propaga por el otro vertice adyacente que no hemos controlado.Si el ciclo de tamano mas pequeno es un C3, hemos terminado pues el fuegoya esta controlado. En caso contrario, el proceso continua.

3. El tercer bombero se anade en uno de los vertices no controlados que sonadyacentes a un quemado. Si el ciclo mas pequeno es un C4, el proceso yaha acabado. Si no, el fuego se continua expandiendo.

4. El ultimo bombero que es agregado se situa adyacente a un vertice que-mado. Independientemente del tamano de los ciclos, el fuego estarıa total-mente controlado.

Por tanto, como mucho, nos hacen falta 4 bomberos: uno en el vertice que uneel ciclo de mayor tamano con el ciclo donde esta r, el segundo se encuentraen el segundo ciclo mayor y los otros dos en el ciclo mas pequeno. Es decir, seencuentran a distancia 1, 2, 3 y 4 de r, respectivamente.

A continuacion, se puede apreciar la representacion de la cota inferior y supe-rior, respectivamente:

r

(a) El incendio se origina enr ∈ G1

r

1 1

(b) Paso 1

r

1 1

2

2

(c) Paso 2



r


r

1

1

(b) Paso 1

r

1

1

2

2

2

(c) Paso 2

r

1

1

2

2

23

3

(d) Paso 3

r

1

1

2

2

23

34

(e) Paso 4

Figura 3.20: Firefighter problem en cactus con ciclos de 9, 10 y 12 vertices

Lema 41 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3, r el vertice donde se origina el fuego. r ∈ G1 y tiene comovertices adyacentes a u y v, siendo u ∈ G1 ∩ G2 y v ∈ G1 ∩ G3, el numero desupervivencia es:

◦ sn(u) = n− 5 (tambien valido para v)

◦ sn(r) = n− 2

Lema 42 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 y tienecomo vertices adyacentes a u y v, siendo u ∈ G1 ∩ G2 y v ∈ G1 ∩ G3, la tasade supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−2)(n−2)+2(n−5)] =

1

n2[n2−4n+4+2n−10] =

=1

n2[n2 − 2n− 6] = 1− 2

n− 6

n2

Lema 43 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 y tienecomo vertices adyacentes a u y v, siendo u ∈ G1∩G2 y v ∈ G1∩G3, el mınimodano esperado es:

ed(G) =1

n

∑z∈V

[n−sn(z)] =1

n[(n−2)(n−(n−2))+2(n−(n−5))] =

1

n(2n+6) = 2+

6

n


Lema 44 Sea G = (V,A) un grafo tipo cactus sin aristas puente formado portres ciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2

o r ∈ G1 ∩G3, el numero de vertices quemados, q(G), se acota de la siguientemanera:

|C3|+ 1 ≤ q(G) ≤ 7

Posteriormente, se explica la estrategia que demuestra el lema anterior.

1. Se anade un bombero en el vertice adyacente a r que se encuentra en elotro ciclo que se une con G1. Entonces, un ciclo ya lo tenemos controladoy el fuego se propaga por los vertices adyacentes a r que no lo estan. Siesos ciclos son C3, el proceso se ha terminado. Si no, continuamos.

2. El segundo bombero es agregado en uno de los vertices adyacentes a unnodo quemado que se encuentra en el ciclo de mayor tamano hasta ahorasin controlar. El fuego se propaga por los otros vertices adyacentes queno hemos controlado. Si el ciclo de tamano mas pequeno es un C4, hemosterminado pues el fuego ya esta controlado. En caso contrario, el procesocontinua.

3. El tercer bombero se anade en uno de los vertices no controlados que sonadyacentes a un quemado. Si el ciclo es un C6, el proceso ya ha acabado.Si no, el fuego se continua expandiendo.

4. El ultimo bombero que es agregado se situa adyacente al ultimo verticequemado. Independientemente del tamano de los ciclos, el fuego estarıatotalmente controlado.

Por tanto, a lo sumo, nos hacen falta 4 bomberos: uno en el vertice que unedos de los 3 ciclos que forman el cactus, otro en el segundo ciclo mas grande ylos dos ultimos en el ciclo mas pequeno. Los cuatro estan situados a distancia:1, 2, 3 y 4 de r, respectivamente.

A continuacion se puede apreciar la representacion de la cota inferior y superior,respectivamente:

r

(a) El incendio se originaen r ∈ G1 ∩G2

r1

11

1

(b) Paso 1



r

(a) El incendio se origina enr ∈ G1 ∩G2

r1

1

1

1

(b) Paso 1

r1

1

1

1

2

2

2

(c) Paso 2

r1

1

1

1

2

2

2

3

3

(d) Paso 3

r1

1

1

1

2

2

2

3

34

(e) Paso 4


Lema 45 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3, r el vertice donde se origina el fuego. Si r ∈ G1 ∩ G2 or ∈ G1 ∩G3, el numero de supervivencia es:

◦ sn(r) = n− 7


Lema 46 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩ G2 or ∈ G1 ∩G3, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−2)(n−2)+2(n−7)] =

1

n2[n2−4n+4+2n−14] =

=1

n2[n2 − 2n− 10] = 1− 2

n− 10

n2

Lema 47 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩ G2 or ∈ G1 ∩G3, el mınimo dano esperado es:

ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 2)(n− (n− 2)) + 2(n− (n− 7))] =

=1

n(2n+ 10) = 2 +

10

n


Lema 48 Sea G = (V,A) un grafo tipo cactus sin aristas puente formado portres ciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2

o r ∈ G1 ∩G3 o r ∈ G2 ∩G3, el numero de vertices quemados, q(G), se acotade la siguiente manera:

|C3|+ 1 ≤ q(G) ≤ 10

La siguiente estrategia demuestra el lema 48.

1. Se anade un bombero en el vertice interseccion adyacente a r donde lasuma de los dos ciclos a los que pertenece sea mayor. Si son iguales, sepuede poner en cualquiera de los dos. El fuego se propaga por los verticesadyacentes a r que no estan controlados.

2. El segundo bombero es agregado en el vertice adyacente a un nodo que-mado que se encuentra en el ciclo mayor. Si los ciclos son C3 el proceso haterminado. Si no, el fuego continua propagandose.

3. El tercer bombero es anadido a un vertice adyacente a un nodo quemadoque se encuentra en el segundo ciclo de mayor tamano. Si el ciclo menor esun C5 el proceso ya habrıa terminado. En caso contrario, el fuego se sigueextendiendo.

4. El cuarto bombero se agrega a uno de los vertices adyacente a un verticequemado que esta en el ciclo mas pequeno. Si este es un C8 el procesohabrıa finalizado. Si no es ası, el fuego se expande.

5. El quinto bombero se agrega al ultimo vertice adyacente a un vertice que-mado. Independientemente del orden de los ciclos, el fuego estarıa total-mente controlado.

Por tanto, como mucho, nos hacen falta 5 bomberos: uno en el vertice que unedos de los 3 ciclos que forman el cactus, otro en el ciclo mas grande, el siguienteen el segundo ciclo mayor y los ultimos en el ciclo mas pequeno. Los cinco estansituados a distancia: 1, 2, 3, 4 y 5 de r, respectivamente.


r


r

1

1

1

1

(b) Paso 1

r

1

1

1

1

2

(c) Paso 2



r

(a) El incendio se origina en r ∈G1 ∩G2

r

1

1 1

1

(b) Paso 1

r

1

1 1

12

2

22

(c) Paso 2

r

1

1 1

1 2

2

223

3

3

(d) Paso 3

r

1

1 1

1 2

2

223

3

3

4

4

(e) Paso 4

r

1

1 1

1 2

2

223

3

3

4

4

5

(f) Paso 5


Lema 49 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3, r el vertice donde se origina el fuego. Si r ∈ G1 ∩ G2 or ∈ G1 ∩G3 o r ∈ G2 ∩G3, el numero de supervivencia es:

◦ sn(r) = n− 10


Lema 50 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩ G2 or ∈ G1 ∩G3 o r ∈ G2 ∩G3, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−3)(n−2)+3(n−10)] =

1

n2[n2−2n−3n+6+3n−30] =

=1

n2[n2 − 2n− 24] = 1− 2

n− 24

n2

Lema 51 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩ G2 or ∈ G1 ∩G3 o r ∈ G2 ∩G3, el mınimo dano esperado es:

ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 3)(n− (n− 2)) + 3(n− (n− 10))] =

=1

n(2n+ 24) = 2 +

24

n


• Grafo cactus con cuatro ciclos

Lema 52 Sea G = (V,A) un grafo tipo cactus sin aristas puente formadopor cuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Sir ∈ G1, d(r) = 2 y los ciclos estan unidos formando una cadena, el numero devertices quemados en G siempre es 2.

Seguidamente, la estrategia demuestra el lema anterior.

1. Colocamos un bombero en el vertice adyacente a r de mayor grado. Elfuego se propaga.

2. El segundo bombero se anade el vertice adyacente al quemado sin controlary ya lo tendrıamos controlado.

1


1

1

1

(b) Paso 1

1

1

1

2

(c) Paso 2

Figura 3.25: Firefighter problem en cactus con 4 ciclos

Lema 53 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1, d(r) =2 y los ciclos estan unidos formando una cadena, el numero de supervivenciaes:

sn(r) = n− 2

Lema 54 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1, d(r) =2 y los ciclos estan unidos formando una cadena, la tasa de supervivencia es:

ρ(G) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− 2) =1

n2n(n− 2) = 1− 2

n

Lema 55 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1, d(r) =2 y los ciclos estan unidos formando una cadena, el mınimo dano esperado es:

ed(G) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− 2)) =1

n

n∑1

2 =2

nn = 2

Lema 56 Sea G = (V,A) un grafo tipo cactus sin aristas puente formadopor cuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Sir ∈ G1∩G2, d(r) = 4 y los ciclos estan unidos formando una cadena, el numerode vertices quemados, q(G), se acota de la siguiente manera:


|C3|+ 1 ≤ q(G) ≤ 7

Posteriormente, la estrategia descrita demuestra el lema 56.

1. Se anade un bombero en el vertice adyacente a r de mayor grado. En elhipotetico caso en el que los grados de los vertices son iguales, tenemosque tener en cuenta cual se encuentra en el ciclo de mayor tamano. Si|G1| = |G2| se acaba eligiendo uno arbitrariamente. El fuego se propagapor los vertices adyacentes a r que no han sido controlados. En el caso deque |G1| = |G2| = 3 el proceso ha terminado. Si no, se continua.

2. El segundo bombero es agregado en uno de los vertices adyacentes a unnodo quemado que se encuentra en el ciclo de mayor tamano. Si el ciclomenor es un C4, el problema ha finalizado. En caso contrario, el fuego seexpande,

3. El tercer bombero se anade en uno de los vertices no controlados que sonadyacentes a un quemado. Si el ciclo mas pequeno es un C5, habrıamosacabado. Si no es ası, el fuego se propaga.

4. El cuarto bombero que es agregado se situa adyacente a un vertice que-mado. Independientemente del tamano de los ciclos, el fuego estarıa total-mente controlado.

Por tanto, como mucho, nos hacen falta 4 bomberos: dos en el ciclo mayor yotros dos en el otro ciclo donde se esta expandiendo el fuego.


r

(a) El incendio se origina en r ∈ G1 ∩G2

r 1

1

1 1

(b) Paso 1



r


r

1

1

1

1

(b) Paso 1

r

1

1

1

1

2

2

2

(c) Paso 2

r

1

1

1

1

2

2

2

3

3

(d) Paso 3

r

1

1

1

1

2

2

2

3

3

4

(e) Paso 4

Figura 3.27: Firefighter problem en cactus con ciclos de 8, 9, 7 y 6 vertices

Lema 57 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2, d(r) = 4 y los ciclos estan unidos formando una cadena, el numero desupervivencia es:

◦ sn(r) = n− 7


Lema 58 Sea G un cactus sin aristas puente de n vertices formado por cua-tro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈G1 ∩ G2, d(r) = 4 y los ciclos estan unidos formando una cadena, la tasa desupervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−3)(n−2)+3(n−7)] =

1

n2[n2−2n−3n+6+3n−21] =

=1

n2[n2 − 2n− 15] = 1− 2

n− 15

n2

Lema 59 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2, d(r) = 4 y los ciclos estan unidos formando una cadena, el mınimo danoesperado es:

ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 3)(n− (n− 2)) + 3(n− (n− 7))] =

=1

n(2n+ 15) = 2 +

15

n


Lema 60 Sea G = (V,A) un grafo tipo cactus sin aristas puente formadopor cuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Sir ∈ G1 ∩ G2 o r ∈ G1 ∩ G3 o r ∈ G2 ∩ G4 o r ∈ G3 ∩ G4 y d(N(r)]) = 2, elnumero de vertices quemados, q(G), se acota de la siguiente manera:

|C3|+ |C3| ≤ q(G) ≤ 7

Seguidamente, la estrategia demuestra el lema anterior:

1. El primer bombero se anade en uno de los vertices adyacentes que a suvez son adyacentes a uno que tiene grado 4 y se encuentran en el ciclo demayor tamano. Posteriormente, el fuego se expande a los vertices de r queno han sido controlados

2. El segundo bombero, por consecuente, se va a agregar al vertice que tienegrado 4 y que es adyacente a un quemado ya que el objetivo es evitar quese expanda al resto de ciclos. El fuego continua propagandose.

3. El tercer bombero es anadido en el vertice adyacente al quemado que seencuentra en el ciclo de mayor tamano. Si el ciclo menor es un C5 el procesofinaliza, pues esta todo controlado. En caso contrario, el fuego se continuaexpandiendo.

4. El ultimo bombero se anade en el vertice adyacente al ultimo nodo que-mado. Independientemente, del orden de los ciclos, el problema estarıacontrolado.

Por tanto, como mucho, nos hacen falta 4 bomberos: dos en el ciclo mayor yotros dos en el ciclo menor.

A continuacion, se puede apreciar que en este caso se ha utilizado C4 y no C3 yaque si todos los vecinos de un vertice de grado 4 son de grado 2, como mınimonecesitamos dos vertices de grado 2. La representacion de la cota inferior ysuperior es la siguiente:

r

(a) El incendio se origi-na en r ∈ G1 ∩G2

r

1

1

1

1

(b) Paso 1

r

1

1

1

1

22

(c) Paso 2

r

1

1

1

1

22

3

3

(d) Paso 3

r

1

1

1

1

22

3

34

(e) Paso 4

Figura 3.28: Firefighter problem en cactus con 4 ciclos de 4 vertices


r


r

1 1

11

(b) Paso 1

r

1 1

11

2

22

(c) Paso 2

r

1 1

1 1

2

2 2

3

3

(d) Paso 3

r

1 1

1 1

2

2 2

3

3

4

(e) Paso 4

Figura 3.29: Firefighter problem en cactus con 4 ciclos de 7, 8, 9 y 10 vertices

Lema 61 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2

o r ∈ G1 ∩ G3 o r ∈ G2 ∩ G4 o r ∈ G3 ∩ G4 y d(N(r)]) = 2, el numero desupervivencia es:

◦ sn(r) = n− 7



o r ∈ G1 ∩ G3 o r ∈ G2 ∩ G4 o r ∈ G3 ∩ G4 y d(N(r)]) = 2, la tasa desupervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−4)(n−2)+4(n−7)] =

1

n2[n2−2n−4n+8+4n−28] =

1

n2[n2 − 2n− 20] = 1− 2

n− 20

n2

Lema 63 Sea G un cactus sin aristas puente de n vertices formado por tresciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1 ∩G2

o r ∈ G1 ∩ G3 o r ∈ G2 ∩ G4 o r ∈ G3 ∩ G4 y d(N(r)]) = 2, el mınimo danoesperado es:


ed(G) =1

n

∑z inV

[n− sn(z)] =1

n[(n− 4)(n− (n− 2)) + 4(n− (n− 7))] =

=1

n(2n+ 20) = 2 +

20

n

Lema 64 Sea G = (V,A) un grafo tipo cactus formado por cuatro ciclos G1,G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1∩G2 o r ∈ G1∩G3

o r ∈ G2∩G4 o r ∈ G3∩G4 y todos los vertices de grado 4 son adyacentes entresı, el numero de vertices quemados, q(G), se acota de la siguiente manera:

|C3|+ 2 ≤ q(G) ≤ 14

Posteriormente, la estrategia explicada demuestra el lema 64:

1. Anadimos un bombero d(N(r)]) = 4 que una ciclos de tamano mayor. Sison iguales, se elige uno de ellos que cumpla estas condiciones. El fuego sepropaga.

2. El segundo bombero se agrega en un vertice de grado 4 que es vecino a unquemado con el objetivo de evitar que se propague lo maximo posible porotros ciclos. Si los ciclos son C3 el problema habrıa finalizado. Si no es ası,el fuego continua extendiendose.

3. Hasta ahora tenemos controlado un ciclo, en los otros tres el fuego secontinua expandiendo. Para frenarlo se anade el tercer bombero en el ciclomas grande de los que no estan controlados, obviamente en un verticevecino a un quemado. Si es posible, el fuego continua expandiendose.

4. En ese mismo ciclo, se introduce otro bombero en el otro vertice adyacentea un vertice quemado. De esta manera habremos conseguido controlar elfuego en ese ciclo. El fuego continua propagandose en el caso de que seaposible.

5. Nos quedan dos ciclos por controlar, por tanto se agrega el quinto bomberoen el vertice adyacente a un nodo quemado que se encuentre en el ciclomas grande que se encuentra sin controlar. Si hay posibilidad, el fuego sepropaga.

6. El sexto bombero se introduce en el unico ciclo donde se esta propagando elfuego. Independientemente del orden de los ciclos, el proceso ha terminado.

Por tanto, a lo sumo, nos hacen falta 6 bomberos: dos en cada ciclo situados adistancia 1, 2, 3, 4, 5 y 6 respectivamente.

A continuacion se puede apreciar la representacion de la cota inferior y superior,respectivamente:


r


r

1

11

1

(b) Paso 1

r

1

11

1

2

2

(c) Paso 2


r


r

1

1

1

1

(b) Paso 1

r

1

1

1

1

2

22

2

2

(c) Paso 2

r

1

1

1

1

2

22

2

2

3

3

3

3

(d) Paso 3

r

1

1

1

1

2

22

2

2

3

3

3

3

4

4

4

(e) Paso 4

r

1

1

1

1

2

22

2

2

3

3

3

3

4

4

4

5

5

(f) Paso 5

r

1

1

1

1

2

22

2

2

3

3

3

3

4

4

4

5

5

6

(g) Paso 6

Figura 3.31: Firefighter problem en cactus con 4 ciclos de 7, 8, 9 y 10 vertices



o r ∈ G1 ∩G3 o r ∈ G2 ∩G4 o r ∈ G3 ∩G4 y todos los vertices de grado 4 sonadyacentes entre sı, el numero de supervivencia es:

◦ sn(r) = n− 14



o r ∈ G1 ∩G3 o r ∈ G2 ∩G4 o r ∈ G3 ∩G4 y todos los vertices de grado 4 sonadyacentes entre sı, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−4)(n−2)+4(n−14)] =

1

n2[n2−2n−4n+8+4n−56] =

=1

n2[n2 − 2n− 48] = 1− 2

n− 48

n2

Lema 67 Sea G un cactus de sin aristas puente de n vertices formado porcuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Sir ∈ G1 ∩G2 o r ∈ G1 ∩G3 o r ∈ G2 ∩G4 o r ∈ G3 ∩G4 y todos los vertices degrado 4 son adyacentes entre sı, el mınimo dano esperado es:

ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 4)(n− (n− 2)) + 4(n− (n− 14))] =

=1

n(2n+ 48) = 2 +

48

n

Lema 68 Sea G = (V,A) un grafo tipo cactus sin aristas puente formadopor cuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Sir ∈ G1 ∩G2 o r ∈ G1 ∩G3 o r ∈ G1 ∩G4, d(r) = 4 y d(N(r)) = 2, el numerode vertices quemados, q(G), se acota de la siguiente manera:

|C3|+ 1 ≤ q(G) ≤ 7

Con la siguiente estrategia se demuestra el lema 68.

1. Se anade un bombero adyacente a r, como los dos vertices son de grado2 se elige uno arbitrariamente. A continuacion, el fuego se propagara si esposible.

2. El siguiente bombero se agrega en el vertice adyacente a uno quemado quese encuentre en el ciclo de mayor tamano. En caso de ser posible, el fuegose extendera.

3. El tercer bombero se anade en un vertice adyacente a uno quemado quese encuentre en el ciclo de mayor tamano hasta ahora sin controlar. Si sepuede, el fuego se propagara a los vertices vecinos.


4. El ultimo bombero es agregado de manera adyacente al unico nodo que-mado que se encuentra sin controlar. Con esto, el proceso finaliza.

Por tanto, a lo sumo, nos hacen falta 4 bomberos: dos en cada ciclo situados adistancia 1, 2, 3 y 4 respectivamente.


r

(a) El incendio se origina en r ∈ G1∩G2

r

1

1

1

1

(b) Paso 1

r

1

1

1

1

2

(c) Paso 2



r


r

11

11

(b) Paso 1

r

11

11

2

2

2

(c) Paso 2

r

11

1 1

2

2

2

3

3

(d) Paso 3

r

11

1 1

2

2

2

3

3

4

(e) Paso 4


Lema 69 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1∩G2 or ∈ G1∩G3 o r ∈ G1∩G4, d(r) = 4 y d(N(r)) = 2, el numero de supervivenciaes:

◦ sn(r) = n− 7



o r ∈ G1 ∩G3 o r ∈ G1 ∩G4, d(r) = 4 y d(N(r)) = 2, la tasa de supervivenciaes:


ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−3)(n−2)+3(n−7)] =

1

n2[n2−2n−3n+6+3n−21] =

=1

n2[n2 − 2n− 15] = 1− 2

n− 15

n2

Lema 71 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1∩G2 or ∈ G1 ∩G3 o r ∈ G1 ∩G4, d(r) = 4 y d(N(r)) = 2, El mınimo dano esperadoes:

ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 3)(n− (n− 2)) + 3(n− (n− 7))] =

=1

n(2n+ 15) = 2 +

15

n

Lema 72 Sea G = (V,A) un grafo tipo cactus sin aristas puente formado porcuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1,d(r) = 2 y d(N(r)]) = 4, el numero de vertices quemados, q(G), se acota de lasiguiente manera:

|C3|+ 1 ≤ q(G) ≤ |C3|+ 2

Seguidamente, se explica la estrategia del lema anterior.

1. El primer bombero es anadido de manera adyacente a r. Como los dosvertices que hay posible son del mismo grado, tenemos que tener en cuentael orden de los ciclos donde se encuentra. En el que sea mayor, ahı loponemos. Si estos tambien son iguales, se elige arbitrariamente. Despues,el fuego se propagara.

2. El segundo bombero se agrega con el objetivo de que el fuego no se puedaexpandir a otros ciclos. A continuacion, el fuego se propagara a los verticesadyacentes. Si el ciclo por donde el fuego se esta expandiendo es un C3 elproceso acaba.

3. Solo nos queda por controlar el fuego en un ciclo. Entonces, se introducirael tercer bombero en el vertice adyacente a un nodo quemado y si se puede,el fuego se seguira propagando.

4. Con el cuarto bombero que se agregue con el mismo criterio que el anterior,el proceso ha finalizado.




r

(a) El incendio se origina en r ∈G1

r

1

1

(b) Paso 1

r

1

1

2

2

2

(c) Paso 2



r


r

1 1

(b) Paso 1

r

1 1

2

2

2

(c) Paso 2

r

1 1

2

2

2

3

3

(d) Paso 3

r

1 1

2

2

2

3

3

4

(e) Paso 4


Lema 73 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1,d(r) = 2 y d(N(r)]) = 4, el numero de supervivencia es:

◦ sn(x) = n− 5 (siendo x ∈ V (G) y d(x) = 4)

◦ sn(r) = n− 2


Lema 74 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Si r ∈ G1,d(r) = 2 y d(N(r)]) = 4, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−3)(n−2)+3(n−5)] =

1

n2[n2−2n−3n+6+3n−15] =

=1

n2[n2 − 2n− 9] = 1− 2

n− 9

n2

Lema 75 Sea G un cactus de dos ciclos sin aristas puente de n vertices for-mado por cuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego.Si r ∈ G1, d(r) = 2 y d(N(r)]) = 4, el mınimo dano esperado es:

ed(G) =1

n

∑z∈V

[n−sn(z)] =1

n[(n−3)(n−(n−2))+3(n−(n−5))] =

1

n(2n+9) = 2+

9

n

Lema 76 Sea G = (V,A) un grafo tipo cactus sin aristas puente formadopor cuatro ciclos G1, G2, G3 y G4 y r el vertice donde se origina el fuego. Sir ∈ G1 ∩G2 o r ∈ G1 ∩G3 o r ∈ G1 ∩G4, d(r) = 4 y d(N(r)) = 4, el numerode vertices quemados, q(G), se acota de la siguiente manera:

|C3|+ 2 ≤ q(G) ≤ 10

La estrategia siguiente demuestre el lema 76.

1. El primer bombero es anadido en el vertice adyacente a r de grado 4. Elfuego se propagara por los vertices adyacentes no controlados.

2. El segundo bombero se anade en uno de los vertices adyacentes a un que-mado que se encuentre en el ciclo de mayor tamano hasta ahora sin con-trolar. El fuego se expandira y si contamos con ciclos C3 el proceso habraterminado. Si no, tendremos que seguir controlando.

3. El tercer bombero se introduce en uno de los vertices vecinos a un quemadoque se encuentre en el anterior ciclo. Si es posible, el fuego se propagara.

4. Si aun no se ha controlado, el cuarto bombero se agregara en el ultimo cicloque queda sin controlar adyacente a un quemado. Si se puede, el fuego seseguira extendiendo por los vertices vecinos.

5. Se introduce el ultimo bombero con el fin de tener el fuego totalmentecontrolado independientemente del orden de los ciclos.




r


r

1

1

1

1

(b) Paso 1

r

1

1

1

1

2

2

(c) Paso 2



r


r

1

11

1

(b) Paso 1

r

1

11

1

2

2

2

2

(c) Paso 2

r

1

11

1

2

2

2

2

3

3

3

(d) Paso 3

r

1

11

1

2

2

2

2

3

3

3

4 4

(e) Paso 4

r

1

11

1

2

2

2

2

3

3

3

4 4

5

(f) Paso 5


Lema 77 Sea G un cactus sin aristas puente de n vertices formado por cuatrociclos G1, G2, G3 y G4, r el vertice donde se origina el fuego. Si r ∈ G1∩G2 or ∈ G1∩G3 o r ∈ G1∩G4, d(r) = 4 y d(N(r)) = 4, el numero de supervivenciacuando es:

◦ sn(r) = n− 10




o r ∈ G1 ∩G3 o r ∈ G1 ∩G4, d(r) = 4 y d(N(r)) = 4, la tasa de supervivenciaes:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−3)(n−2)+3(n−10)] =

1

n2[n2−2n−3n+6+3n−30] =

=1

n2[n2 − 2n− 24] = 1− 2

n− 24

n2


o r ∈ G1∩G3 o r ∈ G1∩G4, d(r) = 4 y d(N(r)) = 4, el mınimo dano esperadoes:

ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 3)(n− (n− 2)) + 3(n− (n− 10))] =

=1

n(2n+ 24) = 2 +

24

n


Finalmente, en lo que a cactus sin aristas respecta, se ha anadido de un ejemplodonde el fuego no se ha podido controlar.

• Caso incontrolable:Como se puede apreciar en la figura posterior, aunque han sido necesarios 6bomberos para “controlar“ el fuego, podemos ver que la mayor parte del cactusha sido quemada, es decir, el proceso ha sido totalmente incontrolable. Si elcactus fuese todavıa mas grande, hubiese continuado propagandose.

r



r

1

1

1

1

(b) Se anade un bombero y se expande

r

1

1

1

1

2

2

2

2

2

2

2

2

(c) Se anade un bombero y se expande


r

1

1

1

1

2

2

2

2

2

2

2

2

33

3

3

33

3

3

3

3

3

3

3

3

3

3

3

(d) Se anade un bombero y se expande

r

1

1

1

1

2

2

2

2

2

2

2

2

33

3

3

33

3

3

3

3

3

3

3

3

3

3

3

4

4

4

4

4

4

4

4

4

4

(e) Se anade un bombero y se expande


r

1

1

1

1

2

2

2

2

2

2

2

2

33

3

3

33

3

3

3

3

3

3

3

3

3

3

3

4

4

4

4

4

4

4

4

4

4

5

5

5

5

(f) Se anade un bombero y se expande

r

1

1

1

1

2

2

2

2

2

2

2

2

33

3

3

33

3

3

3

3

3

3

3

3

3

3

3

4

4

4

4

4

4

4

4

4

4

5

5

5

5

6

6

(g) Se anade un bombero y se expande

Figura 3.38: Firefighter problem no controlable en cactus


Grafo cactus con aristas puenteEste tipo de cactus se va a clasificar segun la cantidad de ciclos que contenga.Ademas, como hemos visto en el apartado 2.1 Firefighter Problem, existen 3 con-ceptos importantes: numero de supervivencia sn(r), tasa de supervivenciaρ(G) y dano esperado ed(G). En cada caso, mostraremos los resultados obtenidostras estudiar dichos conceptos.

• Cactus con dos ciclos

Lema 80 Sea G = (V,A) un grafo tipo cactus con aristas puente formado pordos ciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2

y d(r) = 2, el numero de vertices quemados es 2.


1. El primer bombero es anadido en el vertice adyacente a r de mayor grado.El fuego se propagara por el vertice adyacente no controlado. Si el ciclodonde el fuego se esta propagando es un C3, el proceso ha terminado. Sino, se continua.

2. El segundo bombero se anade en el vertice adyacente a un quemado. Elfuego ya estarıa controlado.

Por tanto, a lo sumo, nos hacen falta 2 bomberos en el ciclo donde se encuentrar a distancia 1 y 2 del origen del fuego, respectivamente.

r


r

1

1

(b) Paso 1

r

1

1

2

(c) Paso 2


Lema 81 Sea G un cactus con aristas puente de n vertices formado por dosciclos G1 y G2, r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 yd(r) = 2, el numero de supervivencia es:

sn(r) = n− 2

Lema 82 Sea G un cactus con aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 yd(r) = 2, la tasa de supervivencia es:

ρ(G) =1

n2

n∑1

sn(r) =1

n2

n∑1

(n− 2) =1

n2n(n− 2) = 1− 2

n

Lema 83 Sea G un cactus con aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 yd(r) = 2, el mınimo dano esperado es:


ed(G) =1

n

n∑1

(n− sn(r)) =1

n

n∑1

(n− (n− 2)) =1

n

n∑1

2 =2

nn = 2

Lema 84 Sea G = (V,A) un grafo tipo cactus con aristas puente formado pordos ciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2

y d(r) = 3, el numero de vertices quemados, q(G), se acota de la siguientemanera:

|C3| ≤ q(G) ≤ |C3|+ 1

Seguidamente, se explica una estrategia que demuestra el lema anterior:

1. El primer bombero es anadido en el vertice adyacente a r de mayor grado.El fuego se propagara por los vertices adyacentes no controlados. Si el ciclodonde el fuego se esta propagando es un C3, el proceso ha terminado. Sino, se continua.

2. El segundo bombero se anade en el vertice adyacente a un quemado. Sidonde se encuentra es un C4 el proceso ha finalizado. Si no es ası, el incendiose seguira extendiendo.

3. El tercer bombero es agregado en el nodo adyacente a un vertice quemado.Independientemente del tamano de los ciclos, el incendio se ha controlado.

Por tanto, como mucho, nos hacen falta 3 bomberos: uno en el otro extremode la arista puente y los otros dos en el ciclo donde el fuego se propaga. Seencuentran a distancia 1, 2 y 3, respectivamente.


r


r 1

1

1

(b) Paso 1



r


r 1

1

1

(b) Paso 1

r 1

1

1

2

2

(c) Paso 2

r 1

1

1

2

2

3

(d) Paso 3

Figura 3.41: Firefighter problem en cactus con 2 ciclos de 6 y 5 vertices

Lema 85 Sea G un cactus con aristas puente de n vertices formado por dosciclos G1 y G2, r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 yd(r) = 3, el numero de supervivencia es:

◦ sn(r) = n− 4


Lema 86 Sea G un cactus con aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 yd(r) = 3, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−2)(n−2)+2(n−4)] =

1

n2[n2−4n+4+2n−8] =

=1

n2[n2 − 2n− 4] = 1− 2

n− 4

n2

Lema 87 Sea G un cactus con aristas puente de n vertices formado por dosciclos G1 y G2 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2 yd(r) = 3, el mınimo dano esperado es:

ed(G) =1

n

∑z∈V

[n−sn(z)] =1

n[(n−2)(n−(n−2))+2(n−(n−4))] =

1

n(2n+4) = 2+

4

n


• Cactus con tres ciclos

Lema 88 Sea G = (V,A) un grafo tipo cactus con aristas puente formado portres ciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 or ∈ G2 o r ∈ G3, d(r) = 2 y d(N(r)) = 3, el numero de vertices quemados,q(G), se acota de la siguiente manera:

2 ≤ q(G) ≤ |C3|

Posteriormente, se describe una estrategia que demuestra el lema 88:

1. El primer bombero es agregado a cualquier vertice de grado 3 que es ad-yacente a r. El fuego se propagara.

2. El segundo bombero se anade al extremo de la arista puente que no estacontrolado. Si en el ciclo donde el fuego se esta expandiendo es un C3 elproceso ha finalizado. Si no, el incendio se propagara.

3. El tercer bombero se agrega en un vertice adyacente a un nodo quemado.Independientemente del tamano de los ciclos, el proceso se ha acabado.

Por tanto, como mucho, nos hacen falta 3 bomberos: uno en el extremo de unaarista puente adyacente a r, otro en el otro extremo de la otra arista puente yel ultimo dentro del ciclo donde se esta expandiendo el fuego a distancia 3 de r.


r


r

1

1

(b) Paso 1

r

1

1

2

(c) Paso 2



r


r

1

1

(b) Paso 1

r

1

1

2

2

(c) Paso 2

r

1

1

2

2

3

(d) Paso 3


Lema 89 Sea G un cactus con aristas puente de n vertices formado por tresciclos G1, G2 y G3, r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2

o r ∈ G3, d(r) = 2 y d(N(r)) = 3, el numero de supervivencia es:

◦ sn(x) = n− 3 (siendo x ∈ V (G) y d(x) = 3)

◦ sn(r) = n− 2

Lema 90 Sea G un cactus con aristas puente de n vertices formado por tresciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 o r ∈ G2

o r ∈ G3, d(r) = 2 y d(N(r)) = 3, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−4)(n−2)+4(n−3)] =

1

n2[n2−2n−4n+8+4n−12] =

=1

n2[n2 − 2n− 4] = 1− 2

n− 4

n2


o r ∈ G3, d(r) = 2 y d(N(r)) = 3, el mınimo dano esperado es:

ed(G) =1

n

∑z inV

[n−sn(z)] =1

n[(n−4)(n−(n−2))+4(n−(n−3))] =

1

n(2n+4) = 2+

4

n


Lema 92 Sea G = (V,A) un grafo tipo cactus con aristas puente formado portres ciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1 or ∈ G2 o r ∈ G3, d(r) = 3 y d(N(r)) = 2 (exceptuando los vertices vecinos queson extremos de una arista puente), el numero de vertices quemados, q(G), seacota de la siguiente manera:

|C3| ≤ q(G) ≤ |C3|+ 1

La estrategia que demuestra dicho lema es la siguiente:

1. El primer bombero se anade en el otro extremo de la arista puente desdedonde ha empezado el fuego. Posteriormente, el fuego se extendera y si esun C3 el proceso ha finalizado.

2. El segundo bombero se agrega en el extremo de la arista puente que quedasin controlar adyacente a un vertice quemado. Si es posible, el fuego sepropagara y si no, el proceso ha terminado.

3. El ultimo bombero es agregado en el vertice adyacente a un nodo quemado.Independientemente del tamano de los ciclos, el proceso ha acabado.

Por tanto, a lo sumo, nos hacen falta 3 bomberos: uno en el extremo de unaarista puente adyacente a r, otro en el otro extremo de la otra arista puente yel siguiente en el ciclo donde se encuentra r. Los bomberos estan a distancia 1,2 y 3, respectivamente.


r

(a) El incendio se origi-na en r ∈ G1

r 1

1

1

(b) Paso 1

r 1

1

1

2

(c) Paso 2


r

(a) El incendio se origi-na en r ∈ G1

r 1

1

1

(b) Paso 1

r 1

1

1

2

2

(c) Paso 2

r 1

1

1

2

23

(d) Paso 3




o r ∈ G3, d(r) = 3 y d(N(r)) = 2 (exceptuando los vertices vecinos que sonextremos de una arista puente), el numero de supervivencia es:

◦ sn(r) = n− 4



o r ∈ G3, d(r) = 3 y d(N(r)) = 2 (exceptuando los vertices vecinos que sonextremos de una arista puente), la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−4)(n−2)+4(n−4)] =

1

n2[n2−2n−4n+8+4n−16] =

=1

n2[n2 − 2n− 8] = 1− 2

n− 8

n2


o r ∈ G3, d(r) = 3 y d(N(r)) = 2 (exceptuando los vertices vecinos que sonextremos de una arista puente), el mınimo dano esperado es:

ed(G) =1

n

∑z∈V

[n−sn(z)] =1

n[(n−4)(n−(n−2))+4(n−(n−4))] =

1

n(2n+4) = 2+

8

n

Lema 96 Sea G = (V,A) un grafo tipo cactus con aristas puente formado portres ciclos G1, G2 y G3 y r el vertice donde se origina el fuego. Si r ∈ G1

o r ∈ G2 o r ∈ G3, d(r) = 3 y r tiene dos vertices adyacentes de grado 3 yuno de grado 2, el numero de vertices quemados, q(G), se acota de la siguientemanera:

|C3| ≤ q(G) ≤ |C3|+ |C3|

Seguidamente, se explica una estrategia que demuestra el lema anterior:

1. El primer bombero se anade en el otro extremo de la arista puente desdedonde ha empezado el fuego. Posteriormente, el fuego se extendera.

2. El segundo bombero se agrega en el extremo de la arista puente que quedasin controlar adyacente a un vertice quemado. Si el ciclo donde se ha ex-pandido el fuego es un C3, el proceso finaliza, pues el fuego esta totalmentecontrolado. Si no, se continua con el proceso.

3. El tercer bombero es anadido en uno de los vertices adyacentes a un nodoquemado y, si es posible, el fuego se seguira propagando por los verticesvecinos.

4. El cuarto bombero se anade en el vertice adyacente al nodo quemado quetodavıa queda sin controlar. Independientemente del tamano de los ciclos,el proceso ha terminado.


Por tanto, a lo sumo, nos hacen falta 4 bomberos: uno en el extremo de unaarista puente adyacente a r, otro en el otro extremo de la otra arista puente ylos otros dos en el ciclo donde se encuentra r. Los 4 bomberos estan a distancia1, 2, 3 y 4, respectivamente.


r


r 1

1

1

(b) Paso 1

r 1

1

1

2

(c) Paso 2



r


r 1

1

1

(b) Paso 1

r 1

1

1

2

2

2

(c) Paso 2

r 1

1

1

2

2

2

3

3

(d) Paso 3

r 1

1

1

2

2

2

3

3

4

(e) Paso 4



o r ∈ G3, d(r) = 3 y r tiene dos vertices adyacentes de grado 3 y uno de grado2, el numero de supervivencia es:

◦ sn(r) = n− 6



o r ∈ G3, d(r) = 3 y r tiene dos vertices adyacentes de grado 3 y uno de grado2, la tasa de supervivencia es:

ρ(G) =1

n2

∑z∈V

sn(z) =1

n2[(n−4)(n−2)+4(n−6)] =

1

n2[n2−2n−4n+8+4n−24] =

=1

n2[n2 − 2n− 16] = 1− 2

n− 16

n2


o r ∈ G3, d(r) = 3 y r tiene dos vertices adyacentes de grado 3 y uno de grado2, el mınimo dano esperado es:


ed(G) =1

n

∑z∈V

[n− sn(z)] =1

n[(n− 4)(n− (n− 2)) + 4(n− (n− 6))] =

=1

n(2n+ 4) = 2 +

16

n

3.7. Grafo MOP (Maximal Outerplanar Graph)

Definicion 100 [5] Un grafo G = (V (G), A) es un MOP ↔ es isomorfo a la triangula-cion de un polıgono. Ademas, un MOP es un grafo maximal periplano.

Nos centraremos en dos tipos de MOPS: Serpentinos y MOPS con un triangulo separador.

(a) MOP serpentino

T

(b) MOP con un trianguloseparador

Figura 3.48: Ejemplo de MOPS

Grafos MOPS serpentinos

Definicion 101 Un MOP es serpentino si solo tiene dos vertices de grado dos.

Ademas, este tipo de grafos tiene propiedades como las que se mencionan a conti-nuacion:

1. Un MOP de n vertices tiene 2n− 3 aristas.

2. Los vertices de grado dos descomponen el conjunto de vertices en dos cadenas.

Estudiaremos el numero de vertices que se pueden quemar segun el grado del verticedonde se origina el fuego.

Lema 102 Sea M un MOP serpentino y r el vertice donde se origina el fuego. Sid(r) = 2, el numero de vertices quemados en M es 2.

La siguiente estrategia demuestra el lema anterior:


1. Colocamos un bombero en el vertice de mayor grado adyacente a r. El fuegose seguira propagando por los vertices vecinos.

2. El segundo bombero se agrega a un nodo adyacente a un quemado. Por lotanto, el fuego estarıa totalmente controlado.

Por lo tanto, a lo sumo, nos hacen falta 2 bomberos. Se encuentran a distancia 1 y2 de r, respectivamente.

r

(a) El fuego se origina en r

r1

1

(b) Paso 1

r1

1

2

(c) Paso 2

Figura 3.49: Ejemplo de Firefighter Problem en MOP serpentino

Lema 103 Sea M un MOP serpentino y r el vertice donde se origina el fuego. Sid(r) = 3 y dos de sus vertices vecinos son de grado 2 y 3, el numero de verticesquemados en M es 3.

Seguidamente, la estrategia demuestra el lema 103:

1. Colocamos un bombero en el vertice de mayor grado adyacente a r. El fuegose seguira propagando por los vertices vecinos.

2. El segundo bombero se agrega a un nodo adyacente a un quemado. Por lotanto, el fuego estarıa totalmente controlado.

Por lo tanto, a lo sumo, nos hacen falta 2 bomberos adyacentes a un quemado. Seencuentran a distancia 1 y 2 de r, respectivamente.


r


r

1

1

1

(b) Paso 1

r

1

1

1

2

(c) Paso 2


Lema 104 Sea M un MOP serpentino y r el vertice donde se origina el fuego. Sid(r) > 3 y uno de sus vertices adyacentes es de grado 2, el numero de verticesquemados en M es d(r).

Antes de nada, tenemos que tener en cuenta cual es el grado de r porque gran partede sus vertices vecinos van a ser quemados. Se va a tratar dicho caso como si r solotuviera dos vertices adyacentes asumiendo que los vertices anteriormente citados seperderan. Al trabajar como si d(r) = 2 ya tenemos la reglas del lema 102.

Por lo tanto, a lo sumo, nos hacen falta 2 bomberos. Se encuentran a distancia 1 y2 de r, respectivamente.

r


r 11

1

11

1

(b) Paso 1

r 11

1

11

1

2

(c) Paso 2



Para los siguientes casos, tenemos que tener en cuenta el lema siguiente:

Lema 105 Sea M un MOP, los bomberos tienen que colocarse por parejas en trans-versales. Se dice que una transversal es una diagonal del polıgono que conecta dosvertices de distinta cadena.

Lema 106 Sea M un MOP serpentino y r el vertice donde se origna el fuego. Si rno es adyacente a un vertice de grado 2, el numero de vertices quemados en M es:

r + etiqueta 1 + etiqueta 2 + etiqueta 3 = 1 + d(r)− 1 + 2 + 1 = d(r) + 3

Seguidamente, la estrategia demuestra el lema 106:

1. Colocamos un bombero en el vertice de mayor grado adyacente a r y quecumpla el lema 105. El fuego se seguira propagando por los vertices vecinos.

2. El segundo se agrega en el otro extremo de donde se ha anadido el primerbombero para completar la arista transversal y que por un lado no continueexpandiendose o en el otro lado de r y que cumpla las mismas condiciones queel paso anterior, pero en vez de ser vecino a r, sera vecino a un nodo quemadocualquiera.

3. Al tener dos bomberos anadidos, se puede anadir un bombero en el otro ladomanteniendo el mismo criterio que en el paso 1, pero en vez de adyacente a r,adyacente a un quemado cualquiera o en el otro extremo de una de las transver-sales para que por una parte el fuego no continue expandiendose. Tendremosque obrar segun hayamos actuado en el paso 2.

4. El ultimo bombero es agregado en el otro extremo de una de las transversalesdonde sea posible. El fuego estarıa totalmente controlado.

Por lo tanto, como mucho, nos hacen falta 4 bomberos. Cada par se situa en unatransversal a distancia 1, 2, 3 y 4 de r.


r


r1

1

1 1 11 1

(b) Paso 1

r1

1

1 1 11 1

2

2

2

(c) Paso 2

r1

1

1 1 1 1 1

2

2

23

3

(d) Paso 3

r1

1

1 1 1 1 1

2

2

23

3

4

(e) Paso 4


A continuacion, vamos a hallar la cota inferior del numero de supervivenciasn(r), de la tasa de supervivencia ρ(G) y de el dano esperado ed(G) de unMOP.

Lema 107 Sea M un MOP serpentino y r el vertice donde se origina el fuego. Lacota inferior del numero de supervivencia es:

sn(r) ≥ n− (d(r) + 3)

Lema 108 Sea M un MOP serpentino y r el vertice donde se origina el fuego. Lacota inferior de la tasa de supervivencia es:

ρ(G) ≥ 1

n2

∑r∈V

sn(r) =1

n2

∑r∈V

[n− (d(r) + 3)] =1

n2[n2 − 3n−

∑r∈V

d(r)] =

=1

n2[n2 − 3n− (2(2n− 3))] =

1

n2[n2 − 3n− 4n+ 6] = 1− 7

n+

6

n2


Lema 109 Sea M un MOP serpentino y r el vertice donde se origina el fuego. Lacota inferior de el mınimo dano esperado es:

ed(G) ≥ 1

n

∑r∈V

[n− sn(r)] =1

n

∑r∈V

[n− (n− (d(r) + 3))] =1

n[3n+

∑r∈V

d(r)] =

=1

n[3n+ 2(2n− 3)] ==

1

n[3n+ 4n− 6] = 7− 6

n

Grafo MOP con un triangulo separador

Definicion 110 Un MOP con un triangulo separador es un tipo de MOP que con-tiene 3 MOPS serpentinos separados por un triangulo cuyo nombre es trianguloseparador.

Lema 111 Sea M un MOP con un triangulo separador, r el vertice donde se originael fuego y T el triangulo separador. Si r no forma parte de T pero es adyacente aun vertice que sı lo es, el numero de vertices quemados en M depende del tamanodel MOP.

A continuacion, la siguiente estrategia demuestra el lema anterior:

1. Se anade un bombero en un vertice adyacente a r que forma parte de T paraevitar que se expanda por la componente de mayor tamano que no sea en laque esta r. El fuego se expandira por el resto de vertices vecinos.

2. El segundo bombero se agrega con el mismo objetivo que en el paso 1. Estavez sera adyacente a un quemado, no tiene por que ser a r.

3. Ya se ha controlado el incendio en una de las componentes. Si nos fijamosatentamente es como si nos hubiese quedado un MOP serpentino. Por tanto, apartir de aquı, aplicamos la estrategia de MOP serpentino en el caso en el quenos encontremos.

Por consiguiente, a lo sumo, nos hacen falta 6 bomberos. Tres en una componentey otros tres en otra a distancia 1, 2, 3, 4, 5 y 6 de r.


r

T


r1

1

1

T

(b) Paso 1

r1

1

1

T

2

2

2

2

2

2

(c) Paso 2

r1

1

1

T

2

2

2

2

2

2

3

3

3

3

3

3

(d) Paso 3


r1

1

1

T

2

2

2

2

2

2

3

3

3

3

3

3

4

4

4

4

4

(e) Paso 4

r1

1

1

T

2

2

2

2

2

2

3

3

3

3

3

3

4

4

4

4

4

5

5

(f) Paso 5

r1

1

1

T

2

2

2

2

2

2

3

3

3

3

3

3

4

4

4

4

4

5

5

6

(g) Paso 6

Figura 3.53: Ejemplo de Firefighter Problem en MOP con triangulo separador

Lema 112 Sea M un MOP con un triangulo separador, r el vertice donde se originael fuego y T el triangulo separador. Si r ∈ T , el numero de vertices quemados en Mdepende del tamano del MOP y del grado de sus vertices.


No existe una estrategia que demuestre el lema porque tenemos muchas barreraspara decidir donde agregar una transversal. Lo que sı se puede afirmar es que nece-sitamos 6 bomberos a distancia 1, 2, 3, 4, 5 y 6 y, a continuacion, se puede observarun ejemplo del caso contemplado.

T

r


T

r

1

1

1

1

(b) Paso 1

T

r

1

1

1

12

2

2

2

2

2

2

2

(c) Paso 2

T

r

1

1

1

12

2

2

2

2

2

2

2

3

3

3

3

3

(d) Paso 3


T

r

1

1

1

12

2

2

2

2

2

2

2

3

3

3

3

3

4

4

4

(e) Paso 4

T

r

1

1

1

12

2

2

2

2

2

2

2

3

3

3

3

3

4

4

4

5

5

(f) Paso 5

T

r

1

1

1

12

2

2

2

2

2

2

2

3

3

3

3

3

4

4

4

5

5

6

(g) Paso 6

Figura 3.54: Ejemplo de Firefighter Problem en MOP con triangulo separador

Capıtulo 4

Burning Graph Problem

Como se explico anteriormente, Burning Graph Problem es un problema NP-completopara muchos tipos de grafos. A continuacion, se demostrara para arboles de grado maximotres pero antes de esto citaremos una serie de corolarios y teoremas que necesitaremospara su demostracion:

Corolario 113 [2] Si (x1, x2, ..., xk) es una secuencia de vertices en un grafo G, tal queNk−1[x1] ∪Nk−2[x2] ∪ ... ∪N0[xk] = V (G), entonces b(G) ≤ k

Teorema 114 [2] Para un camino Pn, tenemos que b(Pn) = dn 12 e. Para ser mas preci-

so, si n = k2 para algun entero k, entonces Pn se quema en k pasos y es equivalente adescomponer Pn en k subcaminos de orden 1, 3, ..., 2k − 1. Si dn 1

2 e = k y n no es numerocuadrado, entonces toda secuencia ardiente optima para Pn corresponde a la descomposi-cion de Pn en k subcaminos Q1, Q2, ..., Qk en el que el orden de cada Qi es un numeroentre 1 y 2i− 1.

Corolario 115 [2] Si G es un grafo con componentes G1, G2, ..., Gt y H es un subbosqueisometrico de G, entonces tenemos que b(H) ≤ b(T ).

Seguidamente, se encuentra el teorema que se va a demostrar.

Teorema 116 [2] Burning Graph Problem es un problema NP-completo para arboles degrado maximo tres.

Demostracion: Dado un grafo G = (V (G), A) de orden n con una secuencia ardiente(x1, x2, ..., xk) siendo xk ∈ G. Para que sea un problema NP-completo tiene que:

1. Pertenecer a la clase NP: Para que pertenezca a la clase NP se tiene que verificaren tiempo polinomico.Para 1 ≤ i ≤ k, se pueden encontrar en tiempo polinomico Nk−i[xi]. Se verificatambien en dicho tiempo si

V (G) =k⋃

i=1

Nk−i[xi]

77

CAPITULO 4. BURNING GRAPH PROBLEM 78

Al cumplirse la condicion anterior, Burning Graph Problem pertenece a la clase NP.

2. Ser NP-duro: Para que sea NP-duro, vamos a reducir este problema al problemade 3-Particion distinta (3-Partition problem).

Burning Graph Problem ∝ 3-Partition Problem

Antes de continuar vamos a describir el problema 3-Particion distinta.

Instancia: Sea un conjunto finito X = {a1, a2, ..., a3n} de enteros positivos y seaB un entero positivo donde B/4 < ai < B/2 para 1 ≤ i ≤ 3n y

∑3ni=1 ai = nB.

Pregunta: ¿Existe alguna particion de X en n ternas tal que cada terna se sume aB?

Es un problema NP-completo incluso cuando la cota superior de B es un polinomion, cuando es ası recibe el nombre de NP-completo en el sentido fuerte. Por el con-trario, en otros casos esta restringido por Om que es el conjunto de los primeros menteros positivos impares: Om = {1, 3, .., 2m− 1}.

⇒ Teniendo en cuenta la instancia de dicho problema, asumimos que es un problemaNP-completo en el sentido fuerte y que X esta limitado por B/2.A continuacion, construimos un arbol, T (X) cuyo ∆ = 3 con las caracterısticasdescritas en [2]. El arbol es el siguiente:

Q1

Q2

Q′

1

Q′

2

Q′

3

Q′

4Q′

5Q′

6

T1

T2

T3

T4

T5 T6 T7 T8

T9

T10

T11

T12

Figura 4.1: Bosquejo de T (X)

CAPITULO 4. BURNING GRAPH PROBLEM 79

Se puede apreciar facilmente que hay una particion de X en ternas tal que loselementos de cada terna se suman a B si y solo si se puede descomponer los caminosQ1, Q2, ....Qn en subcaminos de orden 2ai − 1 ∈ Y siendo Y = {2ai − 1 : ai ∈ X}.Entonces, Y ⊆ Om y 2nB + 3n =

∑3ni=1 2ai − 1 es la suma de los numeros en Y .

Consecuentemente, por el corolario 113, concluimos que (x1, x2, ..., x2m+1) forma unasecuencia ardiente de longitud 2m+ 1 para T (X). Entonces, b(T (X)) ≤ 2m+ 1.

⇐ Suponemos que b(T (X)) = 2m + 1. A continuacion, se aprecia que el caminoP de orden (2m + 1)2 es un subarbol de T (X). Por lo tanto, por el teorema 114y el corolario 115 obtenemos que b(T (X)) ≥ b(P ) = 2m + 1 y por consiguiente,(x1, x2, ..., x2m+1) es una secuencia ardiente optima de T (X).

Seguidamente, se tiene que tener en cuenta que cada xi ∈ P y que para 1 ≤ i ≤ m+1,debemos tener xi = ri siendo ri el centro de Ti. Con N2m+1−i[ri] = V (Ti), el fuegotiene que empezar en xi = ri y quemara todos los vertices en Ti.

Para m+2 ≤ i ≤ 2m+1, N2m+2−i[xi]⋂

(T (X)\⋃m+1

i=1 Ti) es un camino de orden iguala 2(2m+ 1− i) + 1; ya que de otra manera, no podemos quemar todos los nodos enT (X)\

⋃m+1i=1 Ti en m pasos, lo que es una contradiccion. Ademas, tenemos una par-

ticion de T (X)\⋃m+1

i=1 Ti (inducida por la secuencia ardiente (xm+2, xm+3, ..., x2m+1))para T (X) \

⋃m+1i=1 Ti en subcaminos {Pl : l ∈ Om}.

Ahora, al considerar la particion descrita en el parrafo anterior, nos encontramosotra particion que la notaremos Q1, Q2, ..., Qn y esta descompuesta en caminos, Q′ique es una componente de T (X) \

⋃m+1i=1 Ti. Cada camino Qi es de orden 2B + 3

que es una particion de Y en ternas tal que los elementos de cada terna se sumanal orden dicho anteriormente. Equivalentemente, hay otra particion de X en ternastal que cada elemento se suma a B. Desde T (X) es un arbol de ∆ = 3, entonces,el problema 3-Particion Distinta se reduce a Burning Graph Problem para arbolescon ∆ = 3.

Capıtulo 5

Conclusiones

A lo largo de este trabajo se ha estudiado dos problemas: “Firefighter Problem“ y“Burning Graph Problem“. Se ha recopilado los resultados mas relevantes para dichosproblemas y, ademas, se han obtenido nuevos resultados combinatorios y algorıtmicos del“Firefighter Problem“ para tipos especiales de grafos: orugas, langostas, unicıclicos, cac-tus y MOPs.

Respecto al estudio algorıtmico y combinatorio, principalmente se ha basado en ladescripcion de una estrategia para conseguir el objetivo del problema en cada caso que seha contemplado. Asimismo, en todos los ejemplos de grafos orugas, langostas y cactus y,de manera general en grafos MOPS se ha examinado el numero de supervivencia, la tasay el mınimo dano esperado.

Por otro lado, a nivel teorico, cabe resaltar que se ha realizado la construccion de unarbol a partir de una expresion booleana para demostrar que: Restricted NAE 3-SAT ∝3-T’-FIRE.

En “Burning Graph Problem“ se ha demostrado que es un problema NP-completopara muchos tipos de grafos y, tambien se ha reunido informacion acerca del numero ar-diente y se han hecho varios ejemplos sobre ese parametro.

Por ultimo, personalmente, me ha aportado un gran aprendizaje acerca de la Teorıade Grafos y ha sido bastante reconfortante ver como a lo largo de los meses iba avanzandoen el y ser capaz de poder superarme a mı misma.

80

Bibliografıa

[1] Noga Alon et al., Cleaning regular graphs with brushes, SIAM Journal on DiscreteMathematics, 23, pp. 233-250 (Jan. 2008) 6.

[2] Anthony Bonato et al., Burning a graph is hard, Discrete Applied Mathematics, 232,Toronto, pp. 73-87 (2017).

[3] Anthony Bonato et al. How to burn a Graph, Internet Mathematics, 12, pp. 9-10(Jul. 2015).

[4] Anthony Bonato, Shahin Kamali Approximation Algorithms for Graph Burning, ar-Xiv 3 (2018).

[5] Michel Deza, I.G. Rosenberg, “Centers of 2-Trees“ in Combinatorics 79. Part II, 9thed., Amsterdam, Holland, North-Holland, ch. 1, sec. 1, pp. 1 (1982).

[6] Stephen Finbow et al., The Firefighter Problem for graphs of maximum degree three,Discrete Mathematics, 307, pp. 2094-2105 (2007).

[7] Stephen Finbow, Gary MacGillivray, The Firefighter Problem: A survey of results,directions and questions, Australasian Journal of Combinatorics, 43, pp. 57-77 (2009).

[8] Alejandro Flores Lamas (2019, Mayo). Teorıa de Grafos, Grafo tipo Cactus, [Online].Available: https://alexfloreslamas.wordpress.com/

[9] Gregorio Hernandez Penalver, Propuesta de Trabajo Fin de Grado, DMATIC, UPM,(2019).

[10] Gregorio Hernandez Penalver, Complejidad, NP-completitud, Apuntes de clase, UPM,(2018).

[11] Svante Janson et al., Bootstrap percolation on random graphs, Sixteenth INFORMSApplied Probability Conference, Stockholm, pp. 2 (2011).

[12] Anne Kelley, 18.204 Chip firing games, Undergraduate Seminar in Discrete Mathe-matics, Cambridge, pp. 1 (2016).

[13] Stanislav Kucera, Jakub Pekarek, Burning Number conference at Comput. Sci. Inst.of Charles Univ., Prague.

[14] Aman Kumar Srivastava. (2019, Mayo). Dominant Set of a Graph, [Online]. Availa-ble: https://www.geeksforgeeks.org/dominant-set-of-a-graph/

[15] Gloria Labory Pesquer Alianzas en Grafos DMATIC, UPM (2018).

81

BIBLIOGRAFIA 82

[16] Cai Leizhen, Wang Weifan, The surviving rate of a graph for the firefighter problem,SIAM Journal Discrete Math. 23, pp. 1814-1826 (2009).

[17] Elham Roshanbin, Burning a graph as a model for the spread of social contagion,M.S. thesis, Dept. of Maths. and Stat., Dalhousie Univ., Halifax (2016).

[18] Rafael Sanchez Bodoque (2019, Mayo). Caminos de lon-gitud mınima en grafos y digrafos, [Online]. Available:http://www.dma.fi.upm.es/personal/gregorio/grafos/web/caminos minimos/inicio/Inicio.htm

[19] Eric Weisstein (2019, Mayo). Forest, [Online]. Available:http://mathworld.wolfram.com/Forest.html

[20] Eric Weisstein (2019, Mayo). Path Graph, [Online]. Available:http://mathworld.wolfram.com/PathGraph.html

[21] Eric Weisstein (2019, Mayo). Unicyclic Graph, [Online]. Available:http://mathworld.wolfram.com/UnicyclicGraph.html

Este documento esta firmado porFirmante CN=tfgm.fi.upm.es, OU=CCFI, O=Facultad de Informatica - UPM,

C=ES

Fecha/Hora Sun Jun 09 17:51:25 CEST 2019

Emisor delCertificado

[email protected], CN=CA Facultad deInformatica, O=Facultad de Informatica - UPM, C=ES

Numero de Serie 630

Metodo urn:adobe.com:Adobe.PPKLite:adbe.pkcs7.sha1 (AdobeSignature)

graduado en matemáticas e informática universidad ... · el primer problema se describe como un...

Documents