Font Size: a A A

Firefighter Problem Of Some Lattice Graphs In Statistical Model

Posted on:2022-12-09Degree:MasterType:Thesis
Country:ChinaCandidate:Z Y XingFull Text:PDF
GTID:2480306746980409Subject:Architecture and Civil Engineering
Abstract/Summary:PDF Full Text Request
The firefighter problem is a deterministic discrete time model.If graph G represents a social network,with vertices of people and edges of connections between groups,then the firefighter problem can be seen as a simple model for the spread of a virus or epidemic through people.The problem is closely linked to practical problems such as forest fire prevention,epidemic control and curbing rumors.In this paper,mainly study the firefighter problem of plane 4-8 grids graph,plane 4-6-8 grids graph and hexagonal grids graph.The whole paper is divided into four chapters.In the first chapter mainly introduces the development background and research status of firefighter problem,as well as the basic definitions and concepts involved in this paper.The second simply lists the main research results of this paper.In the second chapter,first study the survival rate of finite plane 4-8 grids and analyze the changing rule of the number of surviving points in the lattice graph and give the exact survival rate of finite plane 4-8 grids graph.It is thus proved that for the infinite plane 4-8 grids,the spread of fire can be controlled by using a firefighter per turn after a finite number of protection.In the third chapter,first of all research finite plane 4-6-8 grids graph surviving rate,and analyze the changing rule of the grid graph surviving number of vertices and surviving rate of finite plane 4-6-8 grids is given the exact value,which proves that the graph for infinite plane 4-6-8grids,each round use a firefighter after a finite time protection can control the spread of the fire.In the fourth chapter,the following questions consider in online point of view for the infinite hexagonal grid firefighter problem a protection strategy whether can be find so that any fire source does not spread.
Keywords/Search Tags:Firefighter Problem, Surviving number, Surviving rate, Plane 4-6-8 grids, Hexagonal grids graph, Plane 4-8 grids graph
PDF Full Text Request
Related items