удаление неизоморфных ребер в графе (сюрприз!)

[maxal]

Неожиданно обнаружил пример непомеченного простого графа, в котором есть два неизоморфных ребра, причём удаление любого одного из них приводит к одному и тому же графу:



Причём этот пример является минимальным и, более того, единственным для графов на 6 вершинах.

Интересно, как выглядит граф в котором есть три таких попарно неизоморфных ребра, что удаление любого из них приводит к одному и тому же графу?

P.S. С этими графами связана последовательность A245246, для которой желательно вычислить побольше членов...

[mihailm]

А что такое неизоморфные ребра у графа?

[maxal]

mihailm в сообщении #887804 писал(а):

А что такое неизоморфные ребра у графа?

Два ребра неизоморфны, если не существует автоморфизма графа, переводящего одно ребро в другое.

[alcoholist]

maxal
а есть перевод на язык матрицы инцидентности понятия

maxal в сообщении #887802 писал(а):

непомеченного простого графа, в котором есть два неизоморфных ребра, причём удаление любого одного из них приводит к одному и тому же графу

?

[migmit]

Красиво.

[hurtsy]

maxal в сообщении #887802 писал(а):

что удалению любого из них приводит к одному и тому же графу?

А как определяется, что два графа одинаковы?

[maxal]

hurtsy в сообщении #888518 писал(а):

maxal в сообщении #887802 писал(а):

что удалению любого из них приводит к одному и тому же графу?

А как определяется, что два графа одинаковы?

Непомеченные графы равны, если их помеченые варианты изоморфны. Другими словами, если вы как-то пометите вершины в исходном графе, то после удаления указанных ребер должны получаться изоморфные (помеченные) графы.

[patzer2097]

maxal в сообщении #887802 писал(а):

Интересно, как выглядит граф в котором есть три таких попарно неизоморфных ребра, что удаление любого из них приводит к одному и тому же графу?

Попробую дать ответ на Ваш вопрос; привожу описание подходящей конструкции ниже.

Через $G$ я буду обозначать помеченный граф с множеством вершин $\{1,\ldots,n\}$; я буду считать, что ребра $\pi=(p,q)$ и $\rho=(r,s)$ принадлежат $G$ и неизоморфны

(Оффтоп)

т.е., не существует автоморфизма $G$, переводящего $\pi$ в $\rho$

Также, я буду считать, что граф $G'=G\setminus\pi$, получаемый из $G$ удалением ребра $\pi$, изоморфен графу $G\setminus\rho$. Например, возьмем в качестве $G$ граф из первого сообщения темы.

К множеству вершин $\{1,\ldots,n\}$ графа $G$ я добавлю вершины $v_{ec}$, где $e$ пробегает множество неупорядоченных пар чисел $\{1,\ldots,n\}$, а $c$ пробегает $\{1,\ldots,n\}$. Я буду строить граф $\Gamma=\Gamma(G)$ следующим образом:
(1) если $e=\{i,t\}$, то вершина $i$ будет соединена ребром с вершиной $v_{ec}$ при любом $c$;
(2) если $e\in G$, то вершины $v_{ex}$ и $v_{ey}$ соединены ребром в том и только том случае, если $(x,y)\in G$;
(3) если $e\notin G$, то вершины $v_{ex}$ и $v_{ey}$ соединены ребром в том и только том случае, если $(x,y)\in G'$;
(4) никакие другие пары вершин (кроме упомянутых в пп. 1-3) ребрами соединены не будут.

(Оффтоп)

Говоря неформально, я беру пару вершин $e=(i,j)$ графа $G$ и, если $e\in G$, то "рисую" вместо этого ребра $e$ подграф, изоморфный $G$, а если $e\notin G$, то рисую подграф, изоморфный $G'$. Все добавленные вершины я еще соединяю с $i$ и $j$.

Я утверждаю, что ребра $(v_{\pi p},v_{\pi q})$, $(v_{\pi r},v_{\pi s})$, $(v_{\rho p},v_{\rho q})$, $(v_{\rho r},v_{\rho s})$ попарно неизоморфны, и что графы, полученные удалением любого одного из них, изоморфны. Подробное доказательство, если понадобится, могу привести позже, но вот его набросок.
(1) Вершина $i$ не может переходить в $v_{ec}$ при автоморфизме $\psi$ графа $\Gamma$ из-за того, что у них разные степени;
(2) обозначим $e=(i,j)$ и $e'=(\psi(i),\psi(j))$; тогда вершина $v_{ec}$ переходит в $v_{e'c'}$;
(3) поскольку подграфы, порожденные $v_{ec}$ и $v_{e'c}$ (где $c$ пробегает $\{1,\ldots,n\}$) изоморфны тогда и только тогда, когда $e$ и $e'$ обе либо принадлежат, либо не принадлежат $G$, делаем вывод, что $(\psi(i),\psi(j))\in G$ тогда и только тогда, когда $(i,j)\in G$;
(4) то есть, ограничение $\psi$ на $\{1,\ldots,n\}$ является автоморфизмом $G$, и остаток доказательства довольно прост.

Еще отмечу, что $\Gamma(\Gamma(G))$ будет содержать $8$ ребер с нужным свойством, $\Gamma(\Gamma(\Gamma(G)))$ - $16$, и т.д.

[maxal]

patzer2097 в сообщении #888809 писал(а):

Я утверждаю, что ребра $(v_{\pi p},v_{\pi q})$, $(v_{\pi r},v_{\pi s})$, $(v_{\rho p},v_{\rho q})$, $(v_{\rho r},v_{\rho s})$ попарно неизоморфны, и что графы, полученные удалением любого одного из них, изоморфны.

Я набросал на SAGE реализацию вашей конструкции и проверил "численно" это утверждение. Указанные ребра действительно попарно неизоморфны, но вот среди графов, получаемых удалением этих ребер, есть лишь две непересекающихся изоморфных пары: а именно, изоморфна пара графов, получаемых выкидыванием $(v_{\pi p},v_{\pi q})$ и $(v_{\pi r},v_{\pi s})$, а также пара графов, получаемых выкидыванием $(v_{\rho p},v_{\rho q})$ и $(v_{\rho r},v_{\rho s})$, но никакие другие пары.
Проверьте свои рассуждения на этот счёт. Если интересно, могу превести тут свою программу.

[patzer2097]

(maxal)

К сожалению, пока не вижу, где я неправ. А можете и правда Вашу программу привести?

[maxal]

UPD. Код исправлен. Теперь всё OK.

def EdgesIsomorphic(G,e1,e2):
    G1 = G.copy(immutable=False)
    G1.set_edge_label(e1[0],e1[1],6)
    G2 = G.copy(immutable=False)
    G2.set_edge_label(e2[0],e2[1],6)
    return G1.is_isomorphic(G2, edge_labels=True)

######################### Testing patzer2097's construction

def patzer2097():
  # construct graphs G and G'
  G = Graph([(0,1),(1,2),(2,3),(3,4),(4,5),(5,1),(1,3),(3,5)])
  pq = (1,2)
  rs = (3,4)
  Gp = G.copy()
  Gp.delete_edge(pq)

  # construct graph GG = Gamma(G)
  GG = Graph()

  C = [tuple(c) for c in Combinations(range(6),2)]
  # enumerate vertices v_{ec}
  D = dict( zip( { (e,c) for e in C for c in range(6) }, range(6,6+len(C)*6) ))

  for e in C:
    #case (1)
    for c in range(6):
      GG.add_edge( e[0], D[(e,c)] )
      GG.add_edge( e[1], D[(e,c)] )
        
    #case (2)
    if G.has_edge(e):
      for b in G.edges():
        GG.add_edge( D[(e,b[0])], D[(e,b[1])] )
    #case(3)
    else:
      for b in Gp.edges():
        GG.add_edge( D[(e,b[0])], D[(e,b[1])] )
          
  # testing that four edges are pairwise non-isomorphic
  E = [ [ D[(pq,pq[0])], D[(pq,pq[1])] ], [ D[(pq,rs[0])], D[(pq,rs[1])] ], [ D[(rs,pq[0])], D[(rs,pq[1])] ], [ D[(rs,rs[0])], D[(rs,rs[1])] ] ]
  for i in range(len(E)):
    for j in range(i+1,len(E)):
      print "Edges ",[i,j]," ",EdgesIsomorphic(GG,E[i],E[j])

  # testing if graphs are isomorhic
  GGG = [ GG.copy() for e in E ]
  for i in range(len(E)):
    GGG[i].delete_edge(E[i])
  for i in range(len(E)):
    for j in range(i+1,len(E)):
      print "Graphs ",[i,j]," ",GGG[i].is_isomorphic(GGG[j])

[patzer2097]

Большое спасибо, maxal! Я еще не успел полностью разобраться в Вашем коде, но мне непонятен один момент. Правильно ли я понимаю, что Ваш граф $GG$ отличается от $G$ только лишь добавлением некоторых ребер? Просто в моей конструкции $\{i,j\}$ не принадлежит $\Gamma$ ни при каких $i$ и $j$.

(Оффтоп)

извините, если что-то понял не так

[maxal]

patzer2097 в сообщении #888851 писал(а):

Большое спасибо, maxal! Я еще не успел полностью разобраться в Вашем коде, но мне непонятен один момент. Правильно ли я понимаю, что Ваш граф $GG$ отличается от $G$ только лишь добавлением некоторых ребер? Просто в моей конструкции $\{i,j\}$ не принадлежит $\Gamma$ ни при каких $i$ и $j$.

Ага, это я неправильно понял. Заменил "GG = G.copy()", на "GG = Graph()" и всё стало OK.

Если есть желание добавьте вашу конструкцию на MathOverflow
http://mathoverflow.net/questions/17621 ... same-graph
и я приму её в качестве ответа (хотя граф и не минимальный, она того заслуживает).