python - 生成所有可能的三连通图

Question

有一个 Tutte 和 Thomassen 的猜想(Planarity and duality of finite and infinite graphs, 1979)这样说

A 3-connected graph can be obtained from a wheel by succestively adding an edge and splitting a vertex into two adjacent vertices of degree at least three such that the edge joining them is not contained in a 3-cycle. If we apply a more general splitting operation (i.e., we allow the edge joining the two new vertices to be contained in a 3-cycle) then we can start out with K_4, and we need only the splitting operation in order to generate all 3-connected graphs.

我正在尝试使用 iGraph 和 Python 来实现最后声明的操作。

我想定义一个函数 splitVertex(g,v)，获取一个图 g 和一个顶点 v，然后让它按照操作定义的所有可能方式拆分 v。然后我想要所有这些新图表的列表，我将对它们做一些进一步的工作。

此时，我有以下函数创建两个新顶点 x 和 y，这将是拆分后新创建的顶点。

def splitVertex(g,v):
    numver = g.vcount()

    g.add_vertices(2)

   x = numver
    y = numver+1

    g.add_edges([(x,y)])

有人可以帮我想出一个很好的方法来实现这个吗？我知道这会产生大量数据，但没关系，我有足够的时间 ;)

编辑:当然这必须以某种方式控制，因为 3-连通图的数量是无限的，但这不是这个问题所关注的。

Answer 1

您的拆分操作应该更复杂一些。您需要修改所有用于连接到 v 的边以连接到 x 或 y。

def splitVertex(g,v):
  numver = g.vcount()
  g.add_vertices(2)
  x = numver
  y = numver+1
  g.add_edges([(x,y)])

  neighbors = g.neighbors(v)
  g.delete_vertices([v])

  new_graphs = []
  for (neighbors_of_x, neighbors_of_y) in set_split(neighbors):
    if len(neighbors_of_x) < 2: continue
    if len(neighbors_of_y) < 2: continue
    g2 = g.copy()
    g2.add_edges(map(lambda neighbor_of_x: [neighbor_of_x, x], neighbors_of_x))
    g2.add_edges(map(lambda neighbor_of_y: [neighbor_of_y, y], neighbors_of_y))
    new_graphs.add(g2)
  return new_graphs

set_split 应该生成将 neighbors 分成两组的所有可能方法。

然后您需要为 v 生成所有可能的选择并将它们应用于每个图形。

您可能会得到很多同构图。我想有更好的方法来完成所有这些，我想不出。