graph-theory - 证明如果 G 的深度优先搜索树等于 G 的广度优先搜索树则 G 是树

Question

请告诉我我的证明是否正确

We have a connected graph, and specific vertex u in V(G).
Suppose we compute the dfs tree of G rooted at u and obtain tree T.
Now imagine we compute the bfs tree of G rooted at u and we obtain the same tree T.
Prove that the only way this is possible is if G=T

反证法。

假设dfs树和bfs树都等于T，但是G不等于T。
这意味着 G 至少包含一条不在 T 中的边。
我们也知道任何这样的边都是循环的一部分，否则它们就会在 T 中。
所以至少有一个 Cycle C= p1, p2, p3, p_{k} 且 p_{k} = p1，由不同的节点 k> 组成= 3，在 G.
假设dfs和bfs算法会在节点p1处遇到循环。
Dfs 会将以下边添加到它的树 (p1, p2), ...., (p_{k-2},(p_{k- 1}) 而 bfs 首先将边 (p1,p2), (p1,p_{k}) 添加到它的树中。
我们已经看到 dfs 树不等于 bfs 树，因为 bfs 包含 (p1,p_{k}) 而 dfs 不包含这条边。
这与我们假设 dfs 和 bfs 具有相同的树相矛盾，并且表明 G=T 一定是这种情况。

Answer 1

该定理只适用于无向图(以任意强连通圆有向图为例)。

回到无向图，对于直观的方法，请注意 dfs 最大化树的高度，而 bfs 最小化它。这意味着在第一个圆 C 命中时，覆盖 C 的子树将不同。

你的证明形式化了这个想法，所以总的来说我会说没问题。

你没有指定dfs的选择策略，所以有2个小错误:

• 代替 (p1,p2)，dfs 可能包含 (p1,p_{k}) 或根本不包含任何边 ( )。当然，dfs 永远不会包括两条边，而 bfs 总是会。

• Dfs 不一定向T 添加k-1 个圆边。但是，在返回到p1之前，它已经访问了所有的圆顶点，因此此时所有的圆顶点都已经添加到T。因此 (p1,p_{k})(dfs 选择 (p1,p2) 第一次点击 p1)或 (p1,p2) (else), resp., 不会被添加。

您可以通过证明一个小引理将后者形式化:

设 (v, w) 是 dfs 在步骤 n 中添加的边( wlog 假设 dfs 从 v 移动到w ), T(n) 是第(n)步的部分dfs树。然后由 V(G)\V(T(n)) 诱导的子图 G' 中的连通分量 [w] 的所有节点将在 E(G) 的另一条边 (w, x) 被添加之前被添加到 dfs 树中。