魔方吧·中文魔方俱乐部 › 论坛 › 『理论篇』 › ★ 计算机最少步理论版 (Software Solver Theory) › 魔方-图论-群论-中等难度题

查看: 2458|回复: 5

魔方-图论-群论-中等难度题 [复制链接]

唯有混沌

白魔

Rank: 1

积分: 116
帖子: 87
精华: 0
UID: 1244025
性别: 男

电梯直达

1^#

发表于 2011-6-6 16:35:41 |只看该作者 |倒序浏览

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

收藏0

使用道具举报

superacid

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 2520
帖子: 3072
精华: 7
UID: 62890
性别: 男

2^#

发表于 2011-6-6 17:19:02 |只看该作者

生成树？

19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群：RP与公式的绝佳配合QQ群5652935

使用道具举报

唯有混沌

白魔

Rank: 1

积分: 116
帖子: 87
精华: 0
UID: 1244025
性别: 男

3^#

发表于 2011-6-6 18:11:25 |只看该作者

回复 2# 的帖子

对。支撑树就是生成树

使用道具举报

ggglgq

资深版主

Rank: 8 Rank: 8

积分: 4787
帖子: 1876
精华: 12
UID: 93
性别: 男

4^#

发表于 2011-6-6 20:08:41 |只看该作者

　　

不是很明白楼主的D=max{d}，总觉得D的最小值就是顶点V_i和V_j间的最小距离。

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

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

　　

～～宇宙在旋转运动～

～魔方在循环变换～～

使用道具举报

唯有混沌

白魔

Rank: 1

积分: 116
帖子: 87
精华: 0
UID: 1244025
性别: 男

5^#

发表于 2011-6-6 20:47:23 |只看该作者

回复 4# 的帖子

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

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

使用道具举报

ggglgq

资深版主

Rank: 8 Rank: 8

积分: 4787
帖子: 1876
精华: 12
UID: 93
性别: 男

6^#

发表于 2011-6-6 20:53:04 |只看该作者

　　

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

～～宇宙在旋转运动～

～魔方在循环变换～～

使用道具举报

返回列表

		自动登录	找回密码
密码			注册

魔方-图论-群论-中等难度题 [复制链接]

回复 2# 的帖子

回复 4# 的帖子

中国纪录

八年元老

魔方理论探索者

十年元老