2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Теория графов.
Сообщение03.04.2016, 19:19 


16/12/14
472
Вопрос чисто теоретический. Существует ли такая теорема:
Пусть графы $G$ и $H$, таковы что число их собственных подграфов равно, каждый подграф $\Gamma$ графа $G$ изоморфен некоторому подграфу $\Pi$ графа $H$, и обратно каждый подграф $\Pi$ графа $H$ изоморфен некоторому подграфу $\Gamma$ графа $G$, тогда графы $G$ и $H$ изоморфны?

 Профиль  
                  
 
 Re: Теория графов.
Сообщение03.04.2016, 19:29 
Заслуженный участник


27/04/09
28128
Контрпример: полный и несвязный графы с двумя вершинами.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение03.04.2016, 19:33 


16/12/14
472
arseniiv
А если потребовать связности графов $G$ и $H$?

 Профиль  
                  
 
 Re: Теория графов.
Сообщение03.04.2016, 19:49 
Заслуженный участник


27/04/09
28128
Тут я пока пас. :-)

 Профиль  
                  
 
 Re: Теория графов.
Сообщение03.04.2016, 21:04 


16/12/14
472
arseniiv
Ваш контрпример, кстати неверен. Поскольку у привиденных вами графов неодинаковое число подграфов (У полного 3, посльку несвязный тоже собственный подграф полного). Поэтому вопрос открыт и в самом общем виде.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение03.04.2016, 23:18 
Заслуженный участник


27/04/09
28128
Эх, так и знал, что слишком просто вышло. :-)

 Профиль  
                  
 
 Re: Теория графов.
Сообщение04.04.2016, 18:24 


08/12/13
252
Пусть у исходных графов не менее трёх вершин.
1) Можно ли среди подграфов выбрать три, которые получены из исходного отсечением только одной из вершин?
2) Можно ли из матриц смежности трёх полученных в первом пункте подграфов составить матрицу смежности всего графа?

Не специалист, но попадись подобная тема на практике решал бы путём сравнения предложенной теоремы с обратной к ней и ответом на представленные вопросы.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение05.04.2016, 11:55 


16/12/14
472
Tot
Это что-то ужасно похожее на гипотезу Кэли-Улана про то что каждый граф полностью определен набором своих подграфов, получаемых отсчечением одной из вершин. Она до сих пор не доказана в общем случае. Предложенная теорема, на первый взгляд, чуть слабее потому что в сравнении с гипотезой Улана мы имеем больше данных (еще и все подграфы образованные отсечением нескольких ребер из исходного в добавок к тем,что есть в условии Улана). Но вроде бы удалось показать, эквивалетность этой теоремы гипотезе Улана (активно проверяется док-во), собственно я за тем и обратился на форум, вдруг такое уже доказано и тогда на него можно было бы сослатся в работе. Но, увы, по-всей видимости сслыться особо не на что.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение05.04.2016, 12:20 
Аватара пользователя


08/03/16
45
Москва
Pulseofmalstrem
Pulseofmalstrem в сообщении #1112302 писал(а):
Улана
Улама

-- 05.04.2016, 12:23 --

Было бы неплохо, если бы Вы уточнили, о каких графах идёт речь -- ориентированных/неориентированных, допускающих/не допускающих петли и т.д. Гипотеза Келли-Улама, насколько я знаю, говорит о так называемых простых графах.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение05.04.2016, 12:23 


16/12/14
472
oskar_808

(Оффтоп)

Ох, все никак не могу запомнить эту фамилию.


-- 05.04.2016, 12:24 --

oskar_808
О простых, неориентированных графах, без петель и кратных ребер.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение06.04.2016, 10:09 


16/12/14
472
Можете подсказать источник, откуда можно почерпнуть представление о теории графов на данный момент. Интересуют нерешенные задачи и возможные пути для проведения исследований. Очень хотелось бы связать свои математические интересы и исследования с графами на данный момент.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение07.04.2016, 20:12 


08/12/13
252
Что-то спецы не заглянули.
Мне нравится second edition "Handbook of graph theory" 2014 года.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение07.04.2016, 20:47 


16/12/14
472
Tot
Благодарю за ответ.
По теме, к сожелению, обнаружил ошибку в док-ве эквивалетности, о котором говорил выше. Так что пока у меня на руках гораздо боллее слабая эквивалетность.
Вообще, я был бы рад найти человека, с которым можно было бы вместе поработать над этой проблемой, потому что возможно лично я не вижу некоторых деталей, в силу замыленности личного взгляда. На данный момент мне удалось свести изучение гипотезы Улана к изучением остовных деревьев, данных двух графов, то есть нет нужны рассматривать наборы подграфов с разлиными множествами вершин, можно удобно смотреть на деревья, у которых вершины совпадают, но, увы, множества ребер уже весьма различаются, поэтому в целом задача не становится проще.

 Профиль  
                  
 
 Re: Теория графов.
Сообщение12.04.2016, 22:39 


13/05/14
476
Pulseofmalstrem
По Вашей задаче возможно Вам будет полезно посмотреть статью (на сайте MathNet.ru бесплатно и без регистрации)
Цитата:
В. Г. Визинг, Некоторые нерешенные задачи в теории графов, УМН, 1968, том 23, выпуск 6(144), 117–134.

Там в параграфе 2 "Вопросы изоморфизма" на стр. 121 рассматривается проблема Келли-Улама и родственные ей другие задачи, есть много ссылок на литературу. Хоть какая-нибудь зацепочка... :-)
Вот цитата оттуда:
Цитата:
П. Келли [11] доказал справедливость этой гипотезы для деревьев,
Ф. Харари [12] — для несвязных графов. Проверена справедливость утверждения для $n \leqslant 7$.

Еще вроде-бы помню, что гипотеза Келли -Улама доказана для максимальных внешнеплоских графов (но это надо уточнить).
Более свежие данные можно найти в статье:
Цитата:
П. В. Скумс, Р. И. Тышкевич, Гипотеза реконструируемости для графов с ограничениями на 4-вершинные простые цепи, Дискретн. анализ и исслед. опер. , 2009, том 16, номер 4, 87–96

Тоже на сайте MathNet.ru...

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

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



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

Сейчас этот форум просматривают: Cynic


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

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