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

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

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

Может ли кто-нибудь помочь мне с хорошим способом реализовать это? Я знаю, что это сгенерирует огромное количество данных, но это нормально, у меня много времени;)

Изменить: Конечно, это нужно каким-то образом контролировать, поскольку количество трехсвязных графов бесконечно, но это не то, что касается этого вопроса.


python graph algorithm igraph graph-theory
person utdiscant    schedule 26.12.2010    source источник
comment
Похоже, вы думаете, что количество трехсвязных графов конечно, но это не так, поэтому вы не можете сгенерировать все. Доказательство: возьмите два 3-связных графа, добавьте 3 подходящих ребра между ними, и вы получите новый 3-связный граф. Повторять до бесконечности.   -  person Jochen Ritzel    schedule 26.12.2010
comment
@ THC4k: ну да; но для данного 3-связного графа с n узлами, как сгенерировать всех 3-связанных потомков с n + 1 узлами? Набросал это на бумаге и тоже немного чесал в затылке!   -  person Hugh Bothwell    schedule 26.12.2010
comment
Я не думаю, что количество 3-связных графов конечно, но количество 3-связных графов на n вершинах определенно конечно.   -  person utdiscant    schedule 26.12.2010

Ответы (2)


arrow_upward
0
arrow_downward

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

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
person Tamás    schedule 27.12.2010
comment
Может ли это сгенерировать колесный граф на 5 вершинах из K_4? K_4 - кубический граф, количество соседей всегда равно 3, разбиение в этом случае всегда будет приводить к тому, что некоторый набор будет меньше 2, что приведет к тому, что функция ничего не вернет. - person Jakub Jabłoński; 19.07.2020

arrow_upward
1
arrow_downward

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

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

person Keith Randall    schedule 26.12.2010