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

[sqribner48]

Здравствуйте. Помогите решить вопрос: <<Является ли граф (полным) инвариантом другого графа?>>.
Мне кажется, что наиболее точным и полным определением инварианта графов является определение, данное в книге Зыкова А.А. Основы теории графов (параграф 1.3, стр. 21):
Пусть f “--- функция, относящая каждому графу $L$ некоторый элемент $f(L)$ из множества $M$ произвольной природы (в действительности элементами чаще всего служат числа и системы чисел, вектор, многочлены, матрицы). Эту функцию будем называть инвариантом, если на изоморфных графах ее значения совпадают, т.е. для любых $L$ и $L’$

$$L \simeq L’ \Rightarrow f(L) = f(L’)$$

В этой же книге на стр. 41—42 дано определение полного инварианта:
<<Инвариант называется полным, если для любых $L$ и $L’$

$$f(L) = f(L’) \Leftrightarrow L \simeq L’$$

Объединяя оба определения, можно назвать полным инвариантом графа такую функцию $f(L)$ (со значениями в произвольном множестве), для которой $f(L)= F(L’)$ тогда и только тогда, когда $L \simeq L’$.>>
Прошу ответить на следующие вопросы:
1. Можно ли использовать граф в качестве полного инварианта некоторого другого графа? Если да, то в каких случаях?
2. Видел ли кто-нибудь такое использование в математической литературе? (если видели, то прошу дать ссылку).
Я пытался решить этот вопрос (просмотрел литературу), но полноценного и красивого ответа так и не получил. Единственное что пришло в голову – это граф колесо $W_n$, определяемый как граф $K_1 + C_{n-1}$.
Любой такой граф содержит цикл и одну вершину, соединенную ребрами со всеми остальными вершинами.
Итак, пусть имеем два изоморфных колеса $W_n$ и $W’_n$, которые представляются в следующем виде $W_n= K_1 + C_{n-1}$ и $W’_n= K’_1 + C’_{n-1}$. Следовательно, после удаления из графов $W_n$ и $W’_n$ вершин $K_1$ и $K’_1$ с инцидентными ребрами, получим два изоморфных цикла $C_{n-1}$ и $C’_{n-1}$. То есть два колеса изоморфны, тогда и только тогда, когда изоморфны их образующие циклы. И, следовательно, образующие циклы колес являются их полными инвариантами.
Тогда условие полной инвариантности можно сформулировать так: графы $L$ и $L’$ изоморфны тогда и только тогда, когда изоморфны их подграфы $H=f(L)$ и $H’=f(L’)$, полученные с помощью одинаковых процедур удаления вершин и инцидентных им ребер.
Так ли это? Если это так, то определение полного инварианта нужно подкорректировать?

[sqribner48]

Ну вот, написал сообщение. А теперь вижу, что не совсем четко дал его заголовок и плохо обозначил цитаты из книги Зыкова.
А кнопки "правка" уже нет и ничего изменить нельзя. Прошу извинить меня - новичка на этом сайте.

Постараюсь здесь хоть частично исправить свои ошибки.
Так как у Зыкова при определении инварианта имеется в виду множество $M$ произвольной природы, а именно:

Цитата:

Пусть f - функция, относящая каждому графу $L$ некоторый элемент $f(L)$ из множества $M$ произвольной природы (в действительности элементами чаще всего служат числа и системы чисел, вектор, многочлены, матрицы). Эту функцию будем называть инвариантом, если на изоморфных графах ее значения совпадают, т.е. для любых $L$ и $L’$

$$L \simeq L’ \Rightarrow f(L) = f(L’)$$

...... Инвариант называется полным, если для любых $L$ и $L’$ выполняется

$$f(L) = f(L’) \Rightarrow L \simeq L’$$

Объединяя оба определения, можно назвать полным инвариантом графа такую функцию $f(L)$ (со значениями в произвольном множестве), для которой $f(L)= f(L’)$ тогда и только тогда, когда $L \simeq L’$.

таким образом, (по Зыкову) граф может быть полным инвариантом другого графа.

Остается вопрос "а при каких условиях это выполняется". Мне кажется, что полным инвариантом графа может быть его подграф, суграф или часть.
А как это доказать? Найденный мной пример - граф колесо $W_n$, не является доказательством. Не ясно также, существуют ли другие графы, имеющие подграф (суграф) в качестве своего полного инварианта?

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

$$f(L) = f(L') \Leftrightarrow L \simeq L'$$

надо писать

$$f(L) \simeq f(L') \Leftrightarrow L \simeq L'$$

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

[sqribner48]

... Нашел другое определение инварианта в книге:
Алгоритмы и программы решения задач на графах и сетях/Нечепуренко М. И., Попков В. К., Майнагашев С. М. и др.— Новосибирск: Наука. Сиб. отд-ние, 1990.— 515 с.
Привожу его полностью в авторском изложении:

Цитата:

Введем более строго понятие «инвариант графа» и рассмотрим метод построения различных классов инвариантов. Для простоты изложения, не теряя общности, все рассмотрения будем проводить в классе обыкновенных графов, множество которых обозначим через М.
Пусть $Q_\tau$ — непустое множество элементов $q \in Q$ с определенной на нем эквивалентностью $\tau$,
a $R$ — отношение «быть изоморфными графами». Тогда функция $IH$, заданная на $M_R$ и принимающая значения в $Q_\tau$ называется инвариантом графа, если из условия
$G_i (R) G_j$ следует

$$ \forall G_i, G_j [ IH(G_i) (\tau) IH(G_j)] $$

Вроде бы строго, но мне не нравится.
Более простое и полное определение можно получить из определения Зыкова. А именно:

Пусть f -- функция, относящая каждому графу $L \in M$ некоторый элемент $f(L)$ (произвольной природы) из множества $Q$ с определенным на нем отношением эквивалентности $R_\tau$.
Эту функцию будем называть инвариантом, если на изоморфных графах ее значения эквивалентны, т.е. для любых $L$ и $L’$

$$ L \simeq L’ \Rightarrow f(L) R_\tau f(L’)$$

(В действительности элементами $f(L)$ чаще всего служат числа и системы чисел, вектор, многочлены, матрицы).
Это определение является наиболее универсальным и позволяет использовать в качестве инварианта элементы разного вида.

P.S. Это определение будет еще более "красивым", если для эквивалентности использовать символ $\sim$, тогда получим:

$$ L \simeq L’ \Rightarrow f(L) \sim f(L’)$$

PPS. Таким образом вопрос об определении инварианта решен.
Однако остался нерешенным вопрос об использовании графа в качестве полного инварианта для не тривиальных графов (типа колеса). Если кто-то видел такое в литературе прошу дать ссылку.

[sqribner48]

В дополнение к теме. (Прошу не считать это простым "поднятием" темы - появились новые данные , которые я хочу изложить здесь).
Нашел еще один случай, когда граф может быть инвариантом другого графа.
Действительно, пусть $T$ -- некоторое дерево, а $T^\prime$ --подграф, полученный из $T$ удалением всех его висячих вершин. Тогда, если подграф $T^\prime$ имеет такое же количество висячих вершин, как и граф $T$, то он является инвариантом графа $T$.
Таким образом, если два дерева $T_1$ и $T_2$, с одинаковым количеством висячих вершин, имеют изоморфные подграфы $T^\prime_1$ и $T^\prime_2$, у которых такое же количество висячих вершин как и у графов $T_1$ и $T_2$, то графы $T_1$ и $T_2$ также изоморфны.
Мне кажется, есть и другие случаи, когда некоторый граф может быть инвариантом другого графа...
Помнится у bin в его известной статье было (что-то вроде): если два графа $G_1$ и $G_2$ изоморфны, то изоморфны и их подграфы
$G_1 - u, G_2 - v $, полученные после удаления их подобных вершин $u$ и $v$...

[provincialka]

Многое мне непонятно.
Ну, самое первое: вы ищите инвариант, подходящий для всех графов, или только для каких-то классов? Судя по примеру с "колесами" - последнее. Тогда ответ положительный: всегда можно найти достаточно узкий класс графов, которые вполне определяются своей частью. Только непонятно, зачем. Для колес, например, полная система инвариантов состоит всего из одного числа: количества вершин графа (или количества вершин в цикле).

Что касается деревьев, ваш пример показался мне неверным. Вот, "состригли" мы все висячие вершины. А как будем обратно приклеивать? По одной? или кучками? Результат получится разный.

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

Впрочем, исключения, конечно, могут быть.

[sqribner48]

Все очень просто. Я не ищу полный инвариант для всех классов графов. В книге А.А. Зыкова мне понравилось определение инварианта (полного инварианта) графов. Пожалуй это самое широкое и точное определение. При этом, в качестве инварианта может использоваться любой объект:число, система чисел, кортеж, полином, матрица. Вот я и подумал, что в качестве инварианта графа можно использовать и граф (подграф). При этом возникло маленькое противоречие - равенство инвариантов (данное в определении Зыкова) не подходит для случая когда инвариант - граф. В книге Нечепуренко М. И., Попкова В. К. и Майнагашева С. М. нашел другое более громоздкое определение с использованием эквивалентности. Затем из двух этих определений я скомбинировал одно...
Затем я стал искать примеры, когда (под)граф является инвариантом некоторого графа. Колесо это наиболее простой пример, можно использовать звезду или цикл (но это совсем тривиально). Мне самому пример с колесом не очень нравился (потому что инвариантом является количество вершин). Я поэтому и задал вопрос на сайте, думал кто-нибудь поможет найти менее тривиальный пример.
Сейчас я нашел два более сложных примера - один с деревьями, а другой из статьи bin, широко обсуждавшейся на на нашем форуме.
А с деревьями я прав, потому, что подразумевается удаление всех висячих вершин дерева $T$. Следовательно и при восстановлении исходного дерева имеется в виду добавление одной новой вершины к каждой висячей вершине подграфа $T^\prime$.
Граф как полный инвариант другого графа может использоваться не только при решении задачи изоморфизма, но и при доказательстве некоторых утверждений.

[provincialka]

Может, я не так понимаю "висячую вершину"?

По-моему, после вашей операции от обоих деревьев останутся красные части.

[sqribner48]

Вы правильно поняли. Висячая вершина - это вершина степени 1.
Но в вашем примере после удаления всех висячих вершин, количество оставшихся висячих вершин уменьшается с пяти до двух (красное ребро).
А у меня речь шла о таких деревьях, из которых после удаления всех висячих вершин, получается подграф с тем же количеством висячих вершин.
P.S. Операция удаления висячих вершин дерева хорошо известна в литературе. Впервые ее применил Жордан (19-й век) для определения центра деревьев. (В англоязычной литературе для подграфов, полученных удалением висячих вершин деревьев, даже существует свой термин prune graph). Так, что эта операция никаким образом не является "моей".

[provincialka]

Так.
1) Правильно ли я провела удаление висячих вершин в данных графах? Или имеется в виду только сокращение неветвящихся цепочек? Как будут выглядеть prune graph-ы для приведенных мной деревьев?
2) К любому ли графу можно применять эту операцию? Или вы выделяете среди деревьев еще один подкласс?

[sqribner48]

По п.1 удаление висячих вершин проведено правильно. Prune графы для приведенных вами деревьев будут выглядеть как красное ребро.
По п.2, пожалуй вы правы. По-видимому, для изоморфизма исходных деревья одного условия равенства висячих вершин до и после их удаления недостаточно.(кстати приведенный вами пример можно усилить, добавив к каждой висячей вершине по одной новой вершине (и соединив ее ребром со "своей" висячей вершиной).
А если наложить условие сохранения количества вершин разветвления (т.е. вершин со степенью 3 и более), моя гипотеза будет верна. Попробуйте найти контрпример к этой улучшенной гипотезе.

[provincialka]

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

А если наложить условие сохранения количества вершин разветвления (т.е. вершин со степенью 3 и более),

Фраза, не имеющая (для меня) смысла.

[sqribner48]

Любая фраза (кроме тривиально простых) если не вникать, покажется лишенной смысла....
Я имел в виду следующее:
улучшенная гипотеза
Если подграф $T^\prime$, полученный из дерева $T$ удалением всех висячих вершин, имеет одинаковое с $T$ количество разветвительных вершин, то он является полным инвариантом $T$.
Отсюда следует:
Два дерева $T_1$ и $T_2$ изоморфны тогда и только тогда, когда выполняются следующие условия:
а) подграфы $T^\prime_1$ и $T^\prime_2$, полученные удалением всех висячих вершин $T_1$ и $T_2$ изоморфны;
б) количества разветвительных вершин подграфов $T^\prime_1$ и $T^\prime_2$ совпадают с количеством разветвительных вершин исходных графов $T_1$ и $T_2$, то есть $k_r(T^\prime_1)=k_r(T_1)$ и $k_r(T^\prime_2)=k_r(T_2)$.

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

[provincialka]

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

Любая фраза (кроме тривиально простых) если не вникать, покажется лишенной смысла....

Не уподобляйтесь, пожалуйста, моим студентам. Я за много лет наслушалась бессмысленных фраз, будьте покойны.
Я предполагаю, что термин "разветвительные вершины" вы придумали сами?
Но одним их количеством не обойдешься! У них еще и степени есть. И разные вершины "усеченного" графа могут иметь разное количество убранных "листьев".
Если же вы укажете для каждой оставшейся вершины число отрезанных листьев, то вы по сути полностью опишете исходный граф.

Здесь, собственно возникает вопрос: для чего нужен такой сложный инвариант? Он неэффективен.

[sqribner48]

Термин "разветвительные вершины" я взял из статьи
А. А. Добрынин, И. Гутман, Индекс Винера для деревьев и графов гексагональных систем, Дискретн. анализ и исслед. опер., 1998, том 5, номер 2, 34–60. Правда там на странице 40 у них был термин "вершины ветвления"

Цитата:

Естественными характеристиками структуры дерева являются ветвления и линейные сегменты. Ветвления дерева порождаются вершинами со степенью более 2, которые называются вершинами ветвления. Очевидно, число вершин ветвления в р-вершинном дереве не превышает (р — 2)/2. Сегментом дерева Т называется его простая цепь, концевые вершины которой являются либо вершинами ветвления, либо висячими вершинами в Т, а все внутренние вершины цепи имеют в Т степень 2. Например, все гомеоморфно сводимые деревья имеют одинаковое число сегментов.

Ну немного ошибся и назвал их "разветвительными", ведь сути дела это не меняет.
Теперь по существу вашей критики. Вот моя улучшенная гипотеза.
Два дерева $T_1$ и $T_2$ изоморфны тогда и только тогда, когда выполняются следующие условия:
(а) подграфы $T^\prime_1$ и $T^\prime_2$, полученные удалением всех висячих вершин $T_1$ и $T_2$ изоморфны;
(б) количества вершин ветвления подграфов $T^\prime_1$ и $T^\prime_2$ совпадают с количеством вершин ветвления исходных графов $T_1$ и $T_2$, то есть $k_r(T^\prime_1)=k_r(T_1)$ и $k_r(T^\prime_2)=k_r(T_2)$.

Нетрудно заметить, что если выполняется условие (б), то в этом случае каждая новая висячая вершина должна соединяться только одним ребром с удаляемой висячей вершиной. Следовательно вопрос о степенях новых висячих вершин и о количестве соединяемых с ней вершин (при восстановлении исходного графа)не возникает.
Я согласен с вами, что использование графа в качестве полного инварианта другого графа не очень удобно.
P.S. Фактически, моя гипотеза о полном инварианте пригодна только для подкласса деревьев, для которых выполняется условие (б).

[Xaositect]

Тут не получается "тогда и только тогда". Из (а) и (б) следует изоморфизм, а из изоморфизма не следует (б).