IC-图的存活率

设G是一个有至少2个顶点连通图.当火在G的某个顶点v处燃起时,消防员可以选择k个顶点进行防护.接着在每次时间间隔内,火源传到那些未被防护下来的着火顶点的邻点.火源与消防员交替移动直到火无法传播.消防员的任务是尽可能救多的顶点.图G的k-存活率定义为G的顶点随机着火时消防员一次可以救k个顶点的整个防火过程可救下的顶点的平均存活率.首先把IC-图转化为平面图,然后在平面图上运用权转移方法,证明了:每一个IC-图的5-存活率大于1*10.