如何证明括号定理不适用于广度优先搜索？

Question

我正在尝试思考如何准确地证明括号定理不适用于广度优先搜索。

对于深度优先搜索，它的工作方式与嵌套括号完全相同，因为所有内容都属于这三个属性：

1. 区间 [d[u], f[u]] 和 [d[v], f[v]] 完全不相交，并且 u 和 v 在深度优先森林中都不是对方的后代。

2. 区间 [d[u], f[u]] 包含在区间 [d[v], f[v]] 内，并且 u 是深度优先树中 v 的后代。

3. 区间 [d[v], f[v]] 完全包含在区间 [d[u], f[u]] 内，并且 v 是深度优先树中 u 的后代。

我如何证明它不适用于广度优先搜索？

Answer 1

一般来说，要反驳一个定理，你只需要找到一个反例。在您的情况下，这将是（某些图的）单个广度优先遍历，不满足括号定理。

但是您面临的问题是，括号定理实际上并不是关于图遍历的一般性陈述，它对于给定的遍历可能是正确的或错误的，并且恰好对于所有深度优先遍历都是正确的；相反，括号定理是关于深度优先遍历的特定陈述，对所有这些都成立。像“区间 [d[u], f[u]]”和“深度优先森林”这样的短语明确引用了深度优先遍历；它们没有明显/独特的定义可以应用于广度优先遍历。

所以你需要做的是：

1. 决定括号定理对于广度优先遍历意味着什么。有几种方法可以解决这个问题，例如：
   为定理中使用的所有术语提出适当的“广度优先”定义。
   以更一般的方式重新表述括号定理。
   定义一个“广度优先括号定理”，它类似于现有的“深度优先括号定理”，但所有术语都替换为适当的类似物。
找到不满足这些定义下的定理的广度优先遍历（某些小图）。