Является ли граф (полным) инвариантом другого графа

[sqribner48]

Вот оно что!
Xaositect. Большое спасибо. Теперь мне понятно.

(Оффтоп)

А то меня тут уже сравнили с плохими студентами

А все-же главный вопрос остается: есть ли другие нетривиальные случаи, когда граф может быть полным инвариантом другого графа?

[Xaositect]

Смотря что считать нетривиальным. Например, связные графы на $\geqslant 4$ вершинах изоморфны тогда и только тогда, когда изоморфны их реберные графы, это достаточно нетривиально?

[sqribner48]

Спасибо. Это очень интересный и конечно нетривиальный пример.
Но несколько неожиданный. Потому, что я ожидал такого примера, в котором бы некоторый подграф был полным инвариантом другого графа.

[Toucan]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

[arseniiv]

sqribner48 в сообщении #939827 писал(а):

Но несколько неожиданный. Потому, что я ожидал такого примера, в котором бы некоторый подграф был полным инвариантом другого графа.

Тогда класс исследуемых графов надо будет как-то сильно урезать. Например, можно брать только простые циклы. Неориентированный простой цикл [из более чем трёх вершин] изоморфен другому iff изоморфны их подграфы, полученные удалением одной из вершин.

-- Чт дек 04, 2014 01:05:46 --

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

[provincialka]

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

Немного более перспективной представляется идея брать не подграф, а какой-то другой граф, построенный по определенному алгоритму из данного. Что-то в этом роде предложил Xaositect

[Xaositect]

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

[sqribner48]

arseniiv
Колеса, циклы, звезды рассматривались мной на первой странице темы. Но они мне не нравились из-за своей чрезмерной простоты. Кроме того, для таких графов полным инвариантом будет их количество вершин. Вдобавок при этом подразумевается какая-то предопределенность , потому что известна структура графов (цикл, колесо, звезда). Поэтому я и дал запрос на форум о каких-то других примерах, когда граф может быть инвариантом другого графа.
Спасибо Xaositect -- он дал первый нетривиальный пример.
Вообще использование реберных графов в качестве полного инварианта также имеет ограничения, хотя бы потому что графы $K_3$ и $K_{1,3}$ имеют одинаковые реберные графы, именно из-за этого было предложено использовать графы с числом вершин 4 и более.
Ясно, что использование реберных графов в качестве полного инварианта имеет только "теоретическое" значение. Поскольку задача определения изоморфизма графов сводится к не менее сложной задаче определения изоморфизма соответствующих реберных графов.

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

[provincialka]

sqribner48 в сообщении #940189 писал(а):

представляет интерес также только с точки зрения теории.

Скорее всего, так.

sqribner48 в сообщении #940189 писал(а):

более целесообразно использовать подграфы, имеющие меньшее число вершин и ребер, чем исходный граф.

Маловероятно:

Xaositect в сообщении #939903 писал(а):

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

[sqribner48]

И все-же, в качестве полного инварианта более целесообразно использовать подграфы, имеющие меньшее число вершин и ребер, чем исходный граф.
А что значит "маловероятно"? Мало классов графов. Мало, но они есть.
Что вы скажете, например, о классе максимальных плоских графов, у которых все грани
(в том числе и внешняя) - треугольники, а количество ребер $m$ определяется количеством вершин $n$ по выражению
$m=3n-6.$
Ясно, что подграф $G^\prime$ любого максимального плоского графа $G$, полученный из него удалением всех трех ребер внешней грани, является полным инвариантом графа $G$.

[provincialka]

sqribner48 в сообщении #940233 писал(а):

А что значит "маловероятно"? Мало классов графов. Мало, но они есть.

Вот это и значит "маловероятно"
Ну, ищите, если хотите. Комбинаторное ограничение остается. И проблема изоморфизма полученных подграфов - тоже.
Задача ставится очень искусственно: подобрать графы под метод. А ведь надо наоборот!

[sqribner48]

Да я ничего не ищу. И не собираюсь. И задачи никакой не ставлю.
А комбинаторное ограничение, о котором вы говорите, "действует" не на всех классах графов.
Не действует оно и в, приведенном мной, случае максимальных плоских графов (потому, что у них всех внешние грани одинаковые и сами графы определяются своими "внутренними" подграфами).

[sqribner48]

(Оффтоп)

«Теперь об этом можно рассказать»

Существует еще один класс графов у которых их некоторые подграфы являются полным инвариантом.
Это максимальные внешнеплоские графы (МВП графы) с двумя симплициальными вершинами.
Связный подграф МВП графа, полученный удалением всех его внешних ребер, называется внутренним графом МВП графа.
Внутренние графы МВП графов были впервые введены в работе
Hedetniemi S. M., Proskurowski A.J., Syslo M. M. Interior Graphs of Maximal Outerplane Graphs. Journale of Combinatorial Theory, Series B.1985. P.156--167.

Нетрудно показать, что внутренний граф любого МВП графа с двумя симплициальными вершинами является его полным инвариантом.