生成所有可能的3连通图

Question

有一个猜想是由Tutte和Thomassen提出的（《有限和无限图的平面性与对偶性》，1979年），内容是这样的：

一个3连通的图可以通过从一个轮图开始，逐步添加一条边，并将一个顶点分裂成两个相邻的顶点（这两个新顶点的度数至少为3），而且连接它们的边不能在一个3个顶点的环中。如果我们使用一种更一般的分裂操作（也就是说，允许连接这两个新顶点的边在一个3个顶点的环中），那么我们可以从K_4开始，只需要这个分裂操作，就能生成所有的3连通图。

我正在尝试用Python的iGraph库实现最后提到的操作。

我想定义一个函数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 生成所有可能的选择，并把这些选择应用到每个图上。

你可能会得到很多同构图。我想应该有更好的方法来完成这一切，但我一时想不起来。

Answer 2

根据Keith的解决方案。这个代码还没有经过测试，但我觉得大体思路是没问题的。这个版本是逐步生成分割，而不是一次性返回所有的分割。

from itertools import chain, combinations

def powerset(iterable):
    "Returns all the possible subsets of the elements in a given iterable"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def partition(iterable):
    "Returns all the possible ways to partition a set into two subsets"
    s = set(iterable)
    for s1 in powerset(s):
        yield s1, s-s1

def split_vertex(graph, v1):
    # Note that you only need one extra vertex, you can use v for the other
    v2 = graph.vcount()
    graph.add_vertices(1)

    # Find the neighbors of v1
    neis = set(graph.neighbors(v1))

    # Delete all the edges incident on v1 - some of them will be re-added
    g.delete_edges(g.incident(v1))

    # Iterate over the powerset of neis to find all possible splits
    for set1, set2 in partition(neis):
        if len(set1) < 2 or len(set2) < 2:
            continue

        # Copy the original graph
        g2 = g.copy()

        # Add edges between v1 and members of set1
        g2.add_edges([(v1, v3) for v3 in set1])

        # Add edges between v2 and members of set2
        g2.add_edges([(v2, v3) for v3 in set2])

        # Return the result
        yield g2