The Surviving Rate of a Graph

主讲教师:王维凡 人气:870 更新时间: 2017年06月24日
摘要: Let G be a connected graph with n ≥ 2 vertices. Let k ≥ 1 be an integer. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects k vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let snk(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate ρk(G) of G is defied to be P v∈V snk(v)/n2 , which is the average proportion of saved vertices. In this talk, we give a chief survey on this direction and related problems. In particular, we consider the firefighter problems for some graphs such as trees, outerplanar graphs, planar graphs, d-degenerate graphs, etc
目录
互动讨论

课堂PPT

手动翻阅 (大图)
1/60

相关视频

中国科学技术大学研究生网络课堂试运行版,版权属于中国科学技术大学研究生院。
本网站所有内容属于中国科学技术大学,未经允许不得下载传播。
地址:安徽省合肥市金寨路96号;邮编:230026。TEL:+86-551-63602922;E-mail:wlkt@ustc.edu.cn。 课件总访问人次:17094949