Теория графов.

[Pulseofmalstrem]

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

[arseniiv]

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

[Pulseofmalstrem]

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

[arseniiv]

Тут я пока пас.

[Pulseofmalstrem]

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

[arseniiv]

Эх, так и знал, что слишком просто вышло.

[Tot]

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

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

[Pulseofmalstrem]

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

[oskar_808]

Pulseofmalstrem

Pulseofmalstrem в сообщении #1112302 писал(а):

Улана

Улама

-- 05.04.2016, 12:23 --

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

[Pulseofmalstrem]

oskar_808

(Оффтоп)

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

-- 05.04.2016, 12:24 --

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

[Pulseofmalstrem]

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

[Tot]

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

[Pulseofmalstrem]

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

[sqribner48]

Pulseofmalstrem
По Вашей задаче возможно Вам будет полезно посмотреть статью (на сайте MathNet.ru бесплатно и без регистрации)

Цитата:

В. Г. Визинг, Некоторые нерешенные задачи в теории графов, УМН, 1968, том 23, выпуск 6(144), 117–134.

Там в параграфе 2 "Вопросы изоморфизма" на стр. 121 рассматривается проблема Келли-Улама и родственные ей другие задачи, есть много ссылок на литературу. Хоть какая-нибудь зацепочка...
Вот цитата оттуда:

Цитата:

П. Келли [11] доказал справедливость этой гипотезы для деревьев,
Ф. Харари [12] — для несвязных графов. Проверена справедливость утверждения для $n \leqslant 7$.

Еще вроде-бы помню, что гипотеза Келли -Улама доказана для максимальных внешнеплоских графов (но это надо уточнить).
Более свежие данные можно найти в статье:

Цитата:

П. В. Скумс, Р. И. Тышкевич, Гипотеза реконструируемости для графов с ограничениями на 4-вершинные простые цепи, Дискретн. анализ и исслед. опер. , 2009, том 16, номер 4, 87–96

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