生成所有可能的3连通图

Question

图论中有一个Tutte和Thomassen的猜想（《有限和无限图的平面性和对偶性》，1979年）如下：

一个3连通图可以通过以下操作得到：从一个轮子（wheel）开始，依次添加边并将一个度数至少为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连通图的数量是无限的，但这不是该问题所关注的。

- utdiscant

---

你的发言听起来好像你认为三连通图的数量是有限的，但实际上并不是这样，所以你无法生成“全部”。证明方法是：取两个三连通图，加入适当的三条边，就可以得到一个新的三连通图。如此循环下去，数量是无穷的。 - Jochen Ritzel

@THC4k：嗯，是的；但对于一个具有n个节点的给定3连通图，如何生成所有3连通的n+1节点后代？我一直在纸上草绘，现在也有些不知所措了！ - Hugh Bothwell

我认为3连通图的数量是无限的，但是n个顶点上的3连通图的数量肯定是有限的。 - utdiscant

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 生成所有可能的选择，并将它们应用于每个图形。

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

- Keith Randall

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

- Tamás

---

这能否从K_4生成一个5个顶点的轮图？K_4是一个三次图，邻居数量始终为3，在这种情况下，分区将始终导致某个集合小于2，这将导致函数不返回任何内容。 - Jakub Jabłoński