证明如果 G 的深度优先搜索树等于 G 的广度优先搜索树则 G 是树
Show that if the depth first search tree of G equals breadth first search tree of G then G is Tree
请告诉我我的证明是否正确
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 中。
因此在 G.
中至少有一个 Cycle C= p1, p2, p3, p_{k} with p_{k} = p1，由不同的节点 k>= 3 组成
假设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.
一定是这种情况
该定理仅适用于无向图（以任意强连通圆有向图为例）
回到无向图，对于直观的方法，请注意 dfs 最大化树的高度，而 bfs 最小化它。这意味着在第一个 C 命中时，覆盖 C 的子树将不同。
你的证明使这个想法形式化，所以总的来说我认为没问题。
你没有指定dfs选择策略，所以有2个小错误：
而不是 (p1,p2)，则 dfs 可能包含 (p1,p_{k}) 或 none 的所有边 ( )。当然，dfs 永远不会包括两条边，而 bfs 总是会。
Dfs 不一定将 k-1 圆边添加到 T。但是，在退回到p1之前，它已经访问了所有的圆顶点，所以此时所有的圆顶点都已经被添加到T。因此 (p1,p_{k}) （dfs 选择 (p1,p2) 第一次点击 p1 ）或 (p1,p2) （ else ），分别不会被添加。
你可以通过证明一个小引理来形式化后者：
设 (v, w) 为 dfs 在步骤 n 中添加的边（wlog 假设 dfs 从 v 移动到 w），T(n) 是步骤 (n) 的部分 dfs 树。然后，由 V(G) \ V(T(n)) 诱导的子图 G' 中的连通分量 [w] 中的所有节点将被添加到 dfs 树中，然后来自 E(G) 的另一条边 (w, x) 将被添加到 dfs 树中。已添加。
请告诉我我的证明是否正确
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 中。
因此在 G.
中至少有一个 Cycle C= p1, p2, p3, p_{k} with p_{k} = p1，由不同的节点 k>= 3 组成
假设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.
该定理仅适用于无向图（以任意强连通圆有向图为例）
回到无向图，对于直观的方法，请注意 dfs 最大化树的高度，而 bfs 最小化它。这意味着在第一个 C 命中时，覆盖 C 的子树将不同。
你的证明使这个想法形式化，所以总的来说我认为没问题。
你没有指定dfs选择策略，所以有2个小错误：
而不是
(p1,p2)，则 dfs 可能包含(p1,p_{k})或 none 的所有边 ( )。当然，dfs 永远不会包括两条边，而 bfs 总是会。Dfs 不一定将
k-1圆边添加到T。但是，在退回到p1之前，它已经访问了所有的圆顶点，所以此时所有的圆顶点都已经被添加到T。因此(p1,p_{k})（dfs 选择(p1,p2)第一次点击p1）或(p1,p2)（ else ），分别不会被添加。
你可以通过证明一个小引理来形式化后者：
设 (v, w) 为 dfs 在步骤 n 中添加的边（wlog 假设 dfs 从 v 移动到 w），T(n) 是步骤 (n) 的部分 dfs 树。然后，由 V(G) \ V(T(n)) 诱导的子图 G' 中的连通分量 [w] 中的所有节点将被添加到 dfs 树中，然后来自 E(G) 的另一条边 (w, x) 将被添加到 dfs 树中。已添加。