gpt4 book ai didi

algorithm - 图论 : Are DFS forests that correspond to a graph isomorphic?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:27:51 27 4
gpt4 key购买 nike

对于图G,如果我们选择不同的起始顶点或选择不同的未探索边,它可能有许多不同的DFS森林。因此我们可以构造 G 的许多辅助图。 G的所有辅助图是否都同构?证明你的答案。

我知道图同构是什么意思,但我不知道如何证明这是正确的,或者我想不出一个反例

请帮忙

最佳答案

不,它们不是同构的:

考虑下图:

enter image description here

以下两个 DFS 森林属于它,但显然它们不是同构的: enter image description here

关于algorithm - 图论 : Are DFS forests that correspond to a graph isomorphic?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22292582/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com