Suppose each vertex of a graph is originally occupied by contamination, except for those vertices occupied by lions. As the lions wander on the graph, they clear the contamination from each vertex they visit. However, the contamination simultaneously spreads to any adjacent vertex not occupied by a lion. How many lions are required in order to clear the graph of contamination? We give a lower bound on the number of lions needed in terms of the Cheeger constant of the graph. Furthermore, the lion and contamination problem has been studied in detail on square grid graphs by Brass et al. and Berger et al., and we extend this analysis to the setting of triangular grid graphs.
翻译：假设一个图表的每个顶部最初都为污染所占据, 除了狮子占据的顶部之外。 当狮子在图表上徘徊时, 它们清除了他们所访问的每个顶部的污染。 但是, 污染同时扩散到任何不为狮子占据的相邻顶部。 需要多少狮子才能清除污染图? 我们给出了一个较低的界限, 以图中Cheeger常数为标准。 此外, Brass et al. 和 Berger et al. 在方格图中详细研究了狮子和污染问题, 我们将这一分析扩大到三角格图的设置 。
相关内容
微信扫码咨询专知VIP会员