图的燃烧数
字数 2452 2025-12-07 23:52:19

图的燃烧数

我们先从直观背景开始。想象你在森林中点火，火会从着火点向相邻区域蔓延。在图论中，“燃烧数”（burning number）描述的是用最少的“着火步骤”将整个图的所有顶点“烧完”所需的最小步骤数（或等价地，最小着火点数）。

1. 定义与基本模型

设 \(G = (V, E)\) 是一个有限简单图。
一个燃烧过程（burning process）按离散时间步 \(t = 0, 1, 2, \dots\) 进行：

  • 在 \(t = 0\) 时，所有顶点未燃烧。
  • 在每个时刻 \(t\)，你可以选择一个顶点点燃（称为“着火点”，fire source），这个顶点在时刻 \(t\) 立即燃烧。
  • 同时，所有在 \(t-1\) 时刻已燃烧的顶点，会点燃它们的每个邻居顶点（如果邻居未燃烧，则在 \(t\) 时刻燃烧）。

假设我们在时刻 \(1, 2, \dots, k\) 各选一个着火点（着火点本身立即燃烧），火焰传播规则始终有效。如果在时刻 \(k\) 结束时所有顶点都燃烧了，则称这是一个长度为 \(k\) 的燃烧过程。

图的燃烧数 \(b(G)\) 定义为使得存在一个燃烧过程能在 \(k\) 步内烧完整张图的最小整数 \(k\)。
等价地，如果我们记着火点选择序列为 \((x_1, x_2, \dots, x_k)\)（其中 \(x_t\) 是在时刻 \(t\) 点燃的新着火点），那么燃烧过程满足：

  • 每个顶点 \(v\) 到某个着火点 \(x_t\) 的距离 \(d(v, x_t) \le k - t\)，
    因为 \(x_t\) 在时刻 \(t\) 点燃，火焰传播速度每步走一条边，在时刻 \(k\) 前传播距离最多 \(k-t\)。

所以等价条件：
存在正整数 \(k\) 和顶点序列 \(x_1, \dots, x_k\) 使得

\[V \subseteq \bigcup_{t=1}^k B_{k-t}(x_t), \]

其中 \(B_r(x)\) 表示以 \(x\) 为中心、半径 \(r\) 的闭球（包含距离 ≤ \(r\) 的所有顶点）。
最小的这样的 \(k\) 就是 \(b(G)\)。

2. 简单例子

（1）路径图 \(P_n\)（n 个顶点依次连接）：
可以证明 \(b(P_n) = \lceil \sqrt{n} \,\rceil\)。
例如 \(P_4\)：顶点标为 1-2-3-4，取 \(k=2\)，选着火点：时刻 1 点 2，时刻 2 点 4。

  • 时刻 1：2 燃烧（传播距离 0，仅自燃）。
  • 时刻 2：4 立即燃烧，同时上一轮燃烧的顶点 2 点燃邻居 1 和 3（距离 1）。至此全部燃烧，\(b(P_4)=2\)，而 \(\lceil\sqrt{4}\rceil=2\)。

（2）完全图 \(K_n\)：
任选一个着火点，一步烧完所有顶点（因为所有顶点相邻）。但注意定义要求每个时刻可以选择一个新的着火点，但 \(k=1\) 时只需在时刻 1 选一个点即可全部传播。所以 \(b(K_n) = 1\)（对 \(n \ge 1\)）。

（3）星图 \(S_n\)（中心 1 度 n-1）：
时刻 1 点燃中心，立刻烧到所有叶子（因为中心与叶子距离 1），因此 \(b(S_n) = 1\)（与 \(K_n\) 类似）。

（4）树的特殊性：
树上，燃烧数可以看作是用若干个半径递减的圆盘覆盖所有顶点，选择这些圆盘的中心（着火点）和半径（传播时间）。

3. 一般界的估计

对任意 n 阶连通图 \(G\)，有下界：
因为半径 \(r\) 的闭球最多包含 \(1 + \Delta + \Delta(\Delta-1) + \dots\)（增长至多 \(\Delta^r\) 级别，但精确来说用 Moore 界）。最差情况是路径，因此

\[b(G) \ge \lceil \sqrt{n} \,\rceil \]

不一定成立（比如完全图很小），但对路径确实达到这个下界，且对所有图有以下著名猜想：

燃烧数猜想（Burning Number Conjecture, BNC）：
对任意连通图 \(G\) 有 \(b(G) \le \lceil \sqrt{n} \,\rceil\)。
即路径是最难烧的图（需要最多步骤）。

目前已知结果：对一般连通图 \(G\)，有 \(b(G) \le \lceil\, \sqrt{4n/3} \,\rceil + 1\) 等上界，BNC 在树、一些稀疏类图中已被证明。

4. 与其它图参数的关系

  • 直径 \(\text{diam}(G)\)：显然 \(b(G) \ge \lceil (\text{diam}(G)+1)/2 \rceil\) 之类（因为最远点需要覆盖）。
  • 树宽：燃烧数与树宽无直接单调关系，但小树宽图可通过树分解设计燃烧策略。
  • 距离支配：燃烧过程类似顺序选择中心点，半径递减的多重支配集。

5. 计算复杂性

计算给定图的燃烧数是 NP 困难 的（即使在树上也是 NP 困难，不过树有多项式时间近似算法）。对于某些特殊图类（如笛卡尔积图、区间图、弦图）有精确算法或更好的上界公式。

6. 应用与扩展

  • 社交网络信息传播：选择初始传播者顺序，使信息最快覆盖整个网络。
  • 消防控制模型：安排多个起火点模拟火灾蔓延的最优控制。
  • 图搜索：与“逐层探索未知图”的机器人问题相关。

如果你已经理解这个模型的建立和基本性质，我可以进一步展开 燃烧数在树上的精确算法思路 或 燃烧数猜想的进展与证明技巧，你想先听哪部分？

图的燃烧数 我们先从直观背景开始。想象你在森林中点火，火会从着火点向相邻区域蔓延。在图论中，“燃烧数”（burning number）描述的是用最少的“着火步骤”将整个图的所有顶点“烧完”所需的最小步骤数（或等价地，最小着火点数）。 1. 定义与基本模型 设 \( G = (V, E) \) 是一个有限简单图。 一个 燃烧过程 （burning process）按离散时间步 \( t = 0, 1, 2, \dots \) 进行： 在 \( t = 0 \) 时，所有顶点未燃烧。 在每个时刻 \( t \)，你可以选择一个顶点点燃（称为“着火点”，fire source），这个顶点在时刻 \( t \) 立即燃烧。 同时，所有在 \( t-1 \) 时刻已燃烧的顶点，会点燃它们的每个邻居顶点（如果邻居未燃烧，则在 \( t \) 时刻燃烧）。 假设我们在时刻 \( 1, 2, \dots, k \) 各选一个着火点（着火点本身立即燃烧），火焰传播规则始终有效。如果在时刻 \( k \) 结束时所有顶点都燃烧了，则称这是一个长度为 \( k \) 的燃烧过程。 图的燃烧数 \( b(G) \) 定义为使得存在一个燃烧过程能在 \( k \) 步内烧完整张图的最小整数 \( k \)。 等价地，如果我们记着火点选择序列为 \( (x_ 1, x_ 2, \dots, x_ k) \)（其中 \( x_ t \) 是在时刻 \( t \) 点燃的新着火点），那么燃烧过程满足： 每个顶点 \( v \) 到某个着火点 \( x_ t \) 的距离 \( d(v, x_ t) \le k - t \)， 因为 \( x_ t \) 在时刻 \( t \) 点燃，火焰传播速度每步走一条边，在时刻 \( k \) 前传播距离最多 \( k-t \)。 所以等价条件： 存在正整数 \( k \) 和顶点序列 \( x_ 1, \dots, x_ k \) 使得 \[ V \subseteq \bigcup_ {t=1}^k B_ {k-t}(x_ t), \] 其中 \( B_ r(x) \) 表示以 \( x \) 为中心、半径 \( r \) 的闭球（包含距离 ≤ \( r \) 的所有顶点）。 最小的这样的 \( k \) 就是 \( b(G) \)。 2. 简单例子 （1） 路径图 \( P_ n \) （n 个顶点依次连接）： 可以证明 \( b(P_ n) = \lceil \sqrt{n} \,\rceil \)。 例如 \( P_ 4 \)：顶点标为 1-2-3-4，取 \( k=2 \)，选着火点：时刻 1 点 2，时刻 2 点 4。 时刻 1：2 燃烧（传播距离 0，仅自燃）。 时刻 2：4 立即燃烧，同时上一轮燃烧的顶点 2 点燃邻居 1 和 3（距离 1）。至此全部燃烧，\( b(P_ 4)=2 \)，而 \( \lceil\sqrt{4}\rceil=2 \)。 （2） 完全图 \( K_ n \) ： 任选一个着火点，一步烧完所有顶点（因为所有顶点相邻）。但注意定义要求每个时刻可以选择一个新的着火点，但 \( k=1 \) 时只需在时刻 1 选一个点即可全部传播。所以 \( b(K_ n) = 1 \)（对 \( n \ge 1 \)）。 （3） 星图 \( S_ n \)（中心 1 度 n-1） ： 时刻 1 点燃中心，立刻烧到所有叶子（因为中心与叶子距离 1），因此 \( b(S_ n) = 1 \)（与 \( K_ n \) 类似）。 （4） 树 的特殊性： 树上，燃烧数可以看作是用若干个半径递减的圆盘覆盖所有顶点，选择这些圆盘的中心（着火点）和半径（传播时间）。 3. 一般界的估计 对任意 n 阶连通图 \( G \)，有下界： 因为半径 \( r \) 的闭球最多包含 \( 1 + \Delta + \Delta(\Delta-1) + \dots \)（增长至多 \( \Delta^r \) 级别，但精确来说用 Moore 界）。最差情况是路径，因此 \[ b(G) \ge \lceil \sqrt{n} \,\rceil \] 不一定成立（比如完全图很小），但对路径确实达到这个下界，且对所有图有以下著名猜想： 燃烧数猜想 （Burning Number Conjecture, BNC）： 对任意连通图 \( G \) 有 \( b(G) \le \lceil \sqrt{n} \,\rceil \)。 即路径是最难烧的图（需要最多步骤）。 目前已知结果：对一般连通图 \( G \)，有 \( b(G) \le \lceil\, \sqrt{4n/3} \,\rceil + 1 \) 等上界，BNC 在树、一些稀疏类图中已被证明。 4. 与其它图参数的关系 直径 \( \text{diam}(G) \)：显然 \( b(G) \ge \lceil (\text{diam}(G)+1)/2 \rceil \) 之类（因为最远点需要覆盖）。 树宽 ：燃烧数与树宽无直接单调关系，但小树宽图可通过树分解设计燃烧策略。 距离支配 ：燃烧过程类似顺序选择中心点，半径递减的多重支配集。 5. 计算复杂性 计算给定图的燃烧数是 NP 困难 的（即使在树上也是 NP 困难，不过树有多项式时间近似算法）。对于某些特殊图类（如笛卡尔积图、区间图、弦图）有精确算法或更好的上界公式。 6. 应用与扩展 社交网络信息传播：选择初始传播者顺序，使信息最快覆盖整个网络。 消防控制模型：安排多个起火点模拟火灾蔓延的最优控制。 图搜索：与“逐层探索未知图”的机器人问题相关。 如果你已经理解这个模型的建立和基本性质，我可以进一步展开 燃烧数在树上的精确算法思路 或 燃烧数猜想的进展与证明技巧 ，你想先听哪部分？