Haskell 中的集合构建器符号中是否有二十面体图? (我找到了其他柏拉图图')

问题描述 投票:0回答:1

这可能是一个奇怪的练习,因为我正在谈论要指定的有限数量的边,这就引出了一个问题:为什么不把它们写下来呢?然而,我被要求使用集合构建器符号来描述柏拉图固体 - 在我的例子中,我使用顶点或节点作为它们的面,并按原样使用边 - 我只得到了其中的四个:

tetrahedron = [(j,i) | i <- [1..4], j <- [1..i], i/=j]
cube = [(j,i) | i <- [1..6], j <- [1..i], i/=j, i+j/=7]
octahedron = [(j,i) | i <- [1..8], j <- [1..i], k <- [3,7,9,11,15], i/=j, i+j==k]
dodecahedron = [(j,i) | i <- [1..12], j <- [1..i], k <- [3,4,5,8,12,13,15,16,17,20], i/=j, i+j==k, i-j/=6]

四面体与具有 4 个顶点的完整图相同,立方体结构会生成超出必要数量的边,那些顶点加起来为 7 的边,以便我可以排除它们,而八面体是它们必须加起来等于指定奇数。十二面体很难,但我想我必须创建一个例外,即顶点数之间相差 6。

是否可以用同样的方式创建二十面体图?有没有数学表明否则不可能?

haskell graph set polyhedra
1个回答
2
投票

哈密尔顿图可以用广义 LCF 表示法指定。您绕着哈密顿循环走一圈,并从 0 开始按顺序对顶点进行编号。每个节点显然都与一个较高和一个较低的节点相邻; GLCF 表示法将“缺失”的边缘作为偏移量,以及您应该复制这些偏移量的次数。 GLCF 的一个示例是 [(-4,-3,4),(-2,2,3)]6。这意味着第一个顶点在循环中附加到其后面 4 个、后面 3 个和前面 4 个顶点;第二个顶点在循环中附加到其后面 2 个、前面 2 个和前面 3 个顶点;然后我们总共重复六次,因此第三个顶点再次连接到后面 4、后面 3、前面 4;第四个是后面2个,前面2个,前面3个;等等,直到第十二个也是最后一个节点。

我们可以使用列表理解语法将 GLCF 表示法转换为邻接列表:

glcf :: [[Int]] -> Int -> [(Int, Int)]
glcf offsets repetitions =
    [ (k, k')
    | i <- [0..repetitions-1]
    , (j, os) <- zip [0..] offsets
    , let k = i*n+j
    , o <- -1:1:os
    , let k' = (k+o)`mod`(n*repetitions)
    , k<k'
    ]
    where
    n = length offsets

在许多情况下,每个节点恰好有一条缺失边。然后习惯上去掉 GLCF 元组中的括号,这种缩写形式称为 LCF 表示法。我们可以在 Haskell 中做出类似的区分:

lcf :: [Int] -> Int -> [(Int, Int)]
lcf = glcf . map return

MathWorld 为大多数柏拉图图提供了 GLCF 表示法;查看此页面以获取每个内容的描述链接。奇怪的是,它没有列出八面体图的版本。我不知道为什么,因为通过观察图表的各种渲染很容易看出它应该是什么。我们可以直接导入其他的:

tetrahedron = lcf [-2] 4
cube = lcf [3,-3] 4
octahedron = glcf [[2,-2]] 8
icosahedron = glcf [[-4,-3,4],[-2,2,3]] 6
dodecahedron = lcf [-10,-4,7,-7,4,-10,7,4,-4,-7] 2
© www.soinside.com 2019 - 2024. All rights reserved.