2

我正在开发一个 c++ 程序，它计算和绘制所有可能的具有给定 E 数边的连接平面图。像这样 ：

我的第一个想法是通过在通过递归找到 (n-1) 的答案后添加一条边来找到 N 边的所有可能解决方案。

如图所示，n = 4 问题的解决方案基本上是解决方案 n = 3 的改进版本，多了一条边​​。

但这并不是一个非常有效的解决方案。我在特定算法中找不到这个问题。

有没有其他方法可以找到和绘制所有可能的带有 E 边缘的连接平面图？

4

1 回答 1

2

有没有其他方法可以找到和绘制所有可能的带有 E 边缘的连接平面图？

从完整的图 K (E+1)开始- 这将有(E+1)顶点和E(E+1)/2边。枚举边缘1 .. E(E+1)/2。

  • E对于集合中值的每个排列<1 .. E(E+1)/2>
    • 保留这些E边缘并删除其余部分
    • 删除任何未连接的顶点
    • 如果图是连接的、平面的并且与前一个图不同构，那么
      • 它是一个新的具有 E 边的唯一图。

您可能可以通过考虑完整图形的对称性并消除具有旋转和/或反射对称性与先前排列组合的排列来执行重大优化。

于 2017-10-19T10:30:54.960 回答