3

TutteとThomassen（有限グラフと無限グラフの平面性と双対性、1979年）による推測があります。

3連結グラフは、エッジを連続して追加し、頂点を2つの隣接する頂点に少なくとも3度分割して、それらを結合するエッジが3サイクルに含まれないようにすることでホイールから取得できます。より一般的な分割操作を適用する場合（つまり、2つの新しい頂点を結合するエッジを3サイクルに含めることができる場合）、K_4から始めることができ、3つすべてを生成するために必要なのは分割操作のみです。 -接続されたグラフ。

PythonでiGraphを使用して、最後に述べた操作を実装しようとしています。

関数splitVertex（g、v）を定義し、グラフgと頂点vを取得してから、操作で定義されているすべての可能な方法でvを分割します。次に、これらすべての新しいグラフのリストが必要です。さらに作業を行います。

この時点で、次の関数を使用して、2つの新しい頂点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、に接続するために使用されたすべてのエッジを変更する必要があります。xy

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_split2つのセットに分割するすべての可能な方法をどこで生成する必要があり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 に答える