图的燃烧过程与燃烧数
字数 2128 2025-11-08 20:56:29

图的燃烧过程与燃烧数

图的燃烧过程是一种描述信息或影响在图中传播的简单模型，常用于研究社会网络中的信息传播或传染病的扩散。该过程定义了一个离散的时间步序列，并在每个时间步执行两个操作：点燃新的“火源”和火势蔓延。

1. 燃烧过程的基本规则
假设我们有一个无向图 G=(V,E)。一个燃烧序列是一个顶点序列 (b1, b2, ..., bk)。燃烧过程按如下步骤进行：

  • 时间步 t=1： 我们点燃顶点 b1（称其为第一个火源）。此时，b1 被标记为“已燃烧”。
  • 在每一个后续时间步 t（t>=2），依次发生两件事：
    a. 点燃新火源： 我们点燃序列中的下一个顶点 bt。bt 被立即标记为“已燃烧”。
    b. 火势蔓延： 在上一个时间步（即 t-1 步）中所有已燃烧的顶点，会“点燃”它们所有未被燃烧的邻居顶点。这些邻居顶点也在本步中被标记为“已燃烧”。
  • 这个过程持续进行，直到时间步 k 结束。在时间步 k，我们点燃最后一个火源 bk，并且火势会从所有在时间步 k-1 已燃烧的顶点蔓延开。
  • 如果在这个过程中，图 G 中的所有顶点都被燃烧，那么我们称这个燃烧序列 (b1, b2, ..., bk) 是图 G 的一个“燃烧序列”。

3. 燃烧数的定义
对于一个图 G，其燃烧数，记作 b(G)，是能够完全燃烧图 G 的最短燃烧序列的长度。换句话说，b(G) = k，意味着存在一个长度为 k 的燃烧序列可以烧毁整个图，但不存在长度小于 k 的燃烧序列可以做到这一点。

  • 直观理解： 燃烧数衡量的是“同时从多少个战略点放火，才能最快地烧毁整个图”。k 越小，说明图的结构越紧密，信息传播得越快。

4. 一个简单例子：路径图
考虑一个由 5 个顶点依次连接构成的路径图 P5：v1-v2-v3-v4-v5。

  • 如果我们选择燃烧序列 (v3)，即 k=1：
    • t=1：点燃 v3。已燃烧集合为 {v3}。
    • 由于 k=1，过程结束。但 v1, v2, v4, v5 都未被燃烧。所以这个序列无效。
  • 如果我们选择燃烧序列 (v3, v1)，即 k=2：
    • t=1：点燃 v1。已燃烧集合为 {v1}。
    • t=2：首先点燃第二个火源 v3。已燃烧集合更新为 {v1, v3}。然后火势蔓延：在 t=1 燃烧的 v1 会点燃它的邻居 v2。已燃烧集合变为 {v1, v2, v3}。过程结束，但 v4, v5 未被燃烧。无效。
  • 如果我们选择燃烧序列 (v3, v5)，即 k=2：
    • t=1：点燃 v3。已燃烧集合为 {v3}。
    • t=2：点燃 v5。已燃烧集合变为 {v3, v5}。火势蔓延：在 t=1 燃烧的 v3 会点燃它的邻居 v2 和 v4。已燃烧集合变为 {v2, v3, v4, v5}。过程结束，v1 未被燃烧。无效。
  • 寻找一个有效的序列 (v2, v4)：
    • t=1：点燃 v2。已燃烧集合为 {v2}。
    • t=2：点燃 v4。已燃烧集合变为 {v2, v4}。火势蔓延：在 t=1 燃烧的 v2 会点燃它的邻居 v1 和 v3。已燃烧集合变为 {v1, v2, v3, v4}。过程结束，v5 未被燃烧。无效。
  • 寻找一个有效的序列 (v3, v1, v5)：
    • t=1：点燃 v1。已燃烧集合为 {v1}。
    • t=2：点燃 v3。已燃烧集合变为 {v1, v3}。火势蔓延：v1 点燃 v2。已燃烧集合变为 {v1, v2, v3}。
    • t=3：点燃 v5。已燃烧集合变为 {v1, v2, v3, v5}。火势蔓延：在 t=2 燃烧的顶点是 {v1, v2, v3}。v3 点燃它的邻居 v4。已燃烧集合变为 {v1, v2, v3, v4, v5}。所有顶点被燃烧。有效！
      可以证明，对于 P5，不存在长度为 2 的燃烧序列。因此，b(P5) = 3。

5. 燃烧数的性质与计算复杂性

  • 界限： 对于任意 n 个顶点的图 G，其燃烧数满足 2 <= b(G) <= n。一个完全图（所有顶点两两相连）的燃烧数为 2（任意选一个顶点作为第一个火源，下一步火势蔓延就能烧毁全部）。一条 n 个顶点的路径图，其燃烧数大约为 ⌈√n⌉。
  • NP-困难性： 判定一个图 G 的燃烧数是否小于等于一个给定的整数 k，是一个 NP-完全问题。这意味着对于大型图，精确计算其燃烧数是非常困难的。因此，研究多集中于寻找近似算法、计算特殊图类（如树、网格图、区间图）的燃烧数，以及研究燃烧数的上下界。

6. 燃烧过程与其他模型的联系
燃烧过程可以看作其他传播模型的简化或特例。

  • 与火灾模型（Firefighter Problem）的区别： 火灾模型中，在点燃少量火源后，火势会逐轮蔓延，但同时我们可以派遣消防员去保护（免疫）一些未燃烧的顶点。这是一个“火”与“消防员”的博弈过程。而燃烧过程没有“保护”机制，但允许在每个时间步主动点燃新的火源。
  • 与传染模型（SIR）的联系： 燃烧过程类似于一个离散时间的传染病模型，其中每个被感染的个体（已燃烧顶点）会在下一时间步以概率 1 感染其所有邻居（确定性传播），但同时每个时间步会有新的“零号病人”（新的火源）被引入。
图的燃烧过程与燃烧数 图的燃烧过程是一种描述信息或影响在图中传播的简单模型，常用于研究社会网络中的信息传播或传染病的扩散。该过程定义了一个离散的时间步序列，并在每个时间步执行两个操作：点燃新的“火源”和火势蔓延。 1. 燃烧过程的基本规则 假设我们有一个无向图 G=(V,E)。一个燃烧序列是一个顶点序列 (b1, b2, ..., bk)。燃烧过程按如下步骤进行： 时间步 t=1： 我们点燃顶点 b1（称其为第一个火源）。此时，b1 被标记为“已燃烧”。 在每一个后续时间步 t（t>=2），依次发生两件事： a. 点燃新火源： 我们点燃序列中的下一个顶点 bt。bt 被立即标记为“已燃烧”。 b. 火势蔓延： 在上一个时间步（即 t-1 步）中所有已燃烧的顶点，会“点燃”它们所有未被燃烧的邻居顶点。这些邻居顶点也在本步中被标记为“已燃烧”。 这个过程持续进行，直到时间步 k 结束。在时间步 k，我们点燃最后一个火源 bk，并且火势会从所有在时间步 k-1 已燃烧的顶点蔓延开。 如果在这个过程中，图 G 中的所有顶点都被燃烧，那么我们称这个燃烧序列 (b1, b2, ..., bk) 是图 G 的一个“燃烧序列”。 3. 燃烧数的定义 对于一个图 G，其燃烧数，记作 b(G)，是能够完全燃烧图 G 的最短燃烧序列的长度。换句话说，b(G) = k，意味着存在一个长度为 k 的燃烧序列可以烧毁整个图，但不存在长度小于 k 的燃烧序列可以做到这一点。 直观理解： 燃烧数衡量的是“同时从多少个战略点放火，才能最快地烧毁整个图”。k 越小，说明图的结构越紧密，信息传播得越快。 4. 一个简单例子：路径图 考虑一个由 5 个顶点依次连接构成的路径图 P5：v1-v2-v3-v4-v5。 如果我们选择燃烧序列 (v3)，即 k=1： t=1：点燃 v3。已燃烧集合为 {v3}。 由于 k=1，过程结束。但 v1, v2, v4, v5 都未被燃烧。所以这个序列无效。 如果我们选择燃烧序列 (v3, v1)，即 k=2： t=1：点燃 v1。已燃烧集合为 {v1}。 t=2：首先点燃第二个火源 v3。已燃烧集合更新为 {v1, v3}。然后火势蔓延：在 t=1 燃烧的 v1 会点燃它的邻居 v2。已燃烧集合变为 {v1, v2, v3}。过程结束，但 v4, v5 未被燃烧。无效。 如果我们选择燃烧序列 (v3, v5)，即 k=2： t=1：点燃 v3。已燃烧集合为 {v3}。 t=2：点燃 v5。已燃烧集合变为 {v3, v5}。火势蔓延：在 t=1 燃烧的 v3 会点燃它的邻居 v2 和 v4。已燃烧集合变为 {v2, v3, v4, v5}。过程结束，v1 未被燃烧。无效。 寻找一个有效的序列 (v2, v4)： t=1：点燃 v2。已燃烧集合为 {v2}。 t=2：点燃 v4。已燃烧集合变为 {v2, v4}。火势蔓延：在 t=1 燃烧的 v2 会点燃它的邻居 v1 和 v3。已燃烧集合变为 {v1, v2, v3, v4}。过程结束，v5 未被燃烧。无效。 寻找一个有效的序列 (v3, v1, v5)： t=1：点燃 v1。已燃烧集合为 {v1}。 t=2：点燃 v3。已燃烧集合变为 {v1, v3}。火势蔓延：v1 点燃 v2。已燃烧集合变为 {v1, v2, v3}。 t=3：点燃 v5。已燃烧集合变为 {v1, v2, v3, v5}。火势蔓延：在 t=2 燃烧的顶点是 {v1, v2, v3}。v3 点燃它的邻居 v4。已燃烧集合变为 {v1, v2, v3, v4, v5}。所有顶点被燃烧。有效！ 可以证明，对于 P5，不存在长度为 2 的燃烧序列。因此，b(P5) = 3。 5. 燃烧数的性质与计算复杂性 界限： 对于任意 n 个顶点的图 G，其燃烧数满足 2 <= b(G) <= n。一个完全图（所有顶点两两相连）的燃烧数为 2（任意选一个顶点作为第一个火源，下一步火势蔓延就能烧毁全部）。一条 n 个顶点的路径图，其燃烧数大约为 ⌈√n⌉。 NP-困难性： 判定一个图 G 的燃烧数是否小于等于一个给定的整数 k，是一个 NP-完全问题。这意味着对于大型图，精确计算其燃烧数是非常困难的。因此，研究多集中于寻找近似算法、计算特殊图类（如树、网格图、区间图）的燃烧数，以及研究燃烧数的上下界。 6. 燃烧过程与其他模型的联系 燃烧过程可以看作其他传播模型的简化或特例。 与火灾模型（Firefighter Problem）的区别： 火灾模型中，在点燃少量火源后，火势会逐轮蔓延，但同时我们可以派遣消防员去保护（免疫）一些未燃烧的顶点。这是一个“火”与“消防员”的博弈过程。而燃烧过程没有“保护”机制，但允许在每个时间步主动点燃新的火源。 与传染模型（SIR）的联系： 燃烧过程类似于一个离散时间的传染病模型，其中每个被感染的个体（已燃烧顶点）会在下一时间步以概率 1 感染其所有邻居（确定性传播），但同时每个时间步会有新的“零号病人”（新的火源）被引入。