recursion - 用 "E"边计算所有可能连通的平面图

Question

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

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

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

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

有没有其他方法可以找到并绘制所有可能的具有 E 边的连通平面图？

Answer 1

is there any other way of finding and drawing all possible connected planar graphs with E edge?

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

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

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