3

Tutte 和 Thomassen 有一个猜想（有限和无限图的平面性和对偶性，1979）说

一个 3 连通图可以通过连续添加一条边并将一个顶点分成两个至少三个度数的相邻顶点，使得连接它们的边不包含在 3 循环中，可以从一个轮子中获得一个 3 连通图。如果我们应用更一般的拆分操作（即，我们允许连接两个新顶点的边包含在 3 个循环中），那么我们可以从 K_4 开始，我们只需要拆分操作即可生成所有 3 -连通图。

我正在尝试使用 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 连通图的数量是无限的，但这不是这个问题所关心的。

4

2 回答 2

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并将它们应用于每个图形。

你可能会得到很多同构图。我想有一个更好的方法来做这一切，我想不出它。

于 2010-12-26T21:28:09.633 回答
0

基于基思的解决方案。这是完全未经测试的，但我想一般的想法是可以的。此版本生成拆分而不是一次返回所有拆分。

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
于 2010-12-27T20:19:47.557 回答