魔方吧·中文魔方俱乐部

标题: 魔方-图论-群论-中等难度题 [打印本页]

作者: 唯有混沌 时间: 2011-6-6 16:35:41 标题: 魔方-图论-群论-中等难度题

以三阶魔方可转动得的一切状态为图G的顶点，顶点间有边当且仅当对应状态间相差一次转动。
对于G的一颗定支撑树H上的顶点V[sub]i[/sub]和V[sub]j[/sub]，记V[sub]i[/sub]和V[sub]j[/sub]的树上距离为d，记D=max{d}。
对于变H，求D的最小值。

作者: superacid 时间: 2011-6-6 17:19:02

生成树？

作者: 唯有混沌 时间: 2011-6-6 18:11:25 标题: 回复 2# 的帖子

对。支撑树就是生成树

作者: ggglgq 时间: 2011-6-6 20:08:41

　　

不是很明白楼主的D=max{d}，总觉得D的最小值就是顶点V[sub]i[/sub]和V[sub]j[/sub]间的最小距离。

另外鉴于楼主的两个主题与魔方状态分布图之类的相关研究有关，故此转移

它们至 ★计算机最少步理论版★ ，以便大家讨论研究。
　　

　　

作者: 唯有混沌 时间: 2011-6-6 20:47:23 标题: 回复 4# 的帖子

是这个意思：
对于一颗树，书上有一个最大的d，记为D。
求所有的树的D的最小值。

另：这个问题和最少步有联系；但我觉得你移动的另一个证明题没有，那只是个简单的构造就能解决的。

作者: ggglgq 时间: 2011-6-6 20:53:04

　　

请参考本版版规：3、所有涉及优化或算法的理论（包括数学理论及魔方状态分布图等）基础。
　　
　　

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)