2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 удаление неизоморфных ребер в графе (сюрприз!)
Сообщение16.07.2014, 07:51 
Модератор
Аватара пользователя


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

Изображение

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

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

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение16.07.2014, 08:27 


19/05/10

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение16.07.2014, 08:37 
Модератор
Аватара пользователя


11/01/06
5710
mihailm в сообщении #887804 писал(а):
А что такое неизоморфные ребра у графа?

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение16.07.2014, 23:49 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
maxal
а есть перевод на язык матрицы инцидентности понятия
maxal в сообщении #887802 писал(а):
непомеченного простого графа, в котором есть два неизоморфных ребра, причём удаление любого одного из них приводит к одному и тому же графу

?

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение18.07.2014, 13:53 
Заслуженный участник


10/08/09
599
Красиво.

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение18.07.2014, 19:38 


01/07/08
836
Киев
maxal в сообщении #887802 писал(а):
что удалению любого из них приводит к одному и тому же графу?

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение18.07.2014, 20:10 
Модератор
Аватара пользователя


11/01/06
5710
hurtsy в сообщении #888518 писал(а):
maxal в сообщении #887802 писал(а):
что удалению любого из них приводит к одному и тому же графу?

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

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение19.07.2014, 20:46 
Заслуженный участник


14/03/10
867
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$, и т.д.

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение19.07.2014, 22:47 
Модератор
Аватара пользователя


11/01/06
5710
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})$, но никакие другие пары.
Проверьте свои рассуждения на этот счёт.
Если интересно, могу превести тут свою программу.

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение19.07.2014, 23:20 
Заслуженный участник


14/03/10
867

(maxal)

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение19.07.2014, 23:43 
Модератор
Аватара пользователя


11/01/06
5710
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])

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение19.07.2014, 23:55 
Заслуженный участник


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: удаление неизоморфных ребер в графе (сюрприз!)
Сообщение20.07.2014, 00:03 
Модератор
Аватара пользователя


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group