Генерация всех возможных 3-связных графов - PullRequest
Новая
       16

Генерация всех возможных 3-связных графов

2 голосов
/ 26 декабря 2010

Существует гипотеза Тутте и Томассена (Планарность и двойственность конечных и бесконечных графов, 1979), говорящая это

3-связный граф можно получить из колеса, последовательно добавив реброи разбиение вершины на две смежные вершины степени, по меньшей мере, трех, так что соединяющее их ребро не содержится в 3-цикле.Если мы применим более общую операцию расщепления (т. Е. Мы позволим ребру, соединяющему две новые вершины, содержаться в 3-цикле), то мы можем начать с K_4, и нам понадобится только операция расщепления, чтобы сгенерировать все 3графы.

Я пытаюсь реализовать последнюю заявленную операцию, используя iGraph с Python.

Я хочу определить функцию splitVertex (g, v), принимая граф gи вершина 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-соединенных графовбесконечен, но это не то, к чему относится этот вопрос.

Ответы [ 2 ]

1 голос
/ 27 декабря 2010

Ваша операция расщепления должна быть немного более сложной.Вам нужно изменить все ребра, которые использовались для соединения с 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 и применить их к каждому графу.

Скорее всего, вы получите множество изоморфных графов.Я полагаю, что есть лучший способ сделать все это, не могу думать об этом на макушке.

0 голосов
/ 27 декабря 2010

На основе решения Кейта . Это полностью не проверено, но я думаю, что общая идея в порядке. Эта версия генерирует разбиения вместо того, чтобы возвращать их все сразу. 

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
...