网站首页  |  实验室概况  |  研究团队  |  新闻中心  |  学术交流  |  学术报告  |  实验室年报  |  联系我们

 
 
  当前位置:首页 -> 学术报告
吴文俊数学重点实验室组合图论系列讲座之一百零六【王维凡】
题目:The Surviving Rate of a Graph 

报告人:Wang Weifan 浙江师范大学

时间:6月22日10:00-11:00

地点:1518

摘要: 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

欢迎广大师生参加!

中国科学院吴文俊数学重点实验室