DFS和深度树

Question

我需要确定以下陈述是对还是错。如果为true，请说明为什么，如果false给出反例。

令T为图G和源顶点s上的DFS算法产生的深度树。 G是一个无向图，其周期为3个顶点。 因此，不包含从G中的S到其他顶点的所有最短途径。

我认为这是真的，但我不知道如何证明它或解释为什么

Answer 1

这有点棘手，因为图G可能包含其他周期。三个周期可能会嵌入到树上的多种方式，可能是循环中边缘的 nonne 完全在树上，因此很难通过将所有可能的嵌入分为几种情况。

我认为最简单的证明方法是：

• 如果t是植根于s的g的dfs树，则g中的每个边缘都在t中，或者它将节点连接到t中的祖先
• 。边缘处于不同的高度。对于树中的边缘，它们会差异1。对于其他边缘，它们至少差异为1。
• 周期周围的高度变化之和必须为0，因为它以同一顶点启动和结束。
• 不可能是3周期中的所有高度差异为1，因为这样它们的总数将是一个奇数 - 而不是0。
• 因此，3个周期中的至少一个边缘必须具有高度差＆gt； 1。此边缘将是其下顶点的缩写，因为树上的所有路径都可以每步最多改变高度。