Изоморфизм графов

[alexrr]

Недавно начал разбираться с изоморфизмом графов. Появился вопрос. Надо найти, какие графы друг другу изоморфны. Как можно доказать, что графы не изоморфны? Если количество вершин и ребер совпадают, степени тоже. Вот, например, 1 и 2 неизоморфны, я просто пронумеровал граф, а у другого пытался тоже так же пронумеровать, чтоб сохранялись те же соединения. Получилось, что в 1 и 2 так нельзя сделать, но есть ли другие простые способы д-ва?

[arseniiv]

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

[Sender]

Можно заметить, что в первом нет треугольников.

[Andrey_Kireew]

Проверка изоморфизма графов - это проблема, но у Вас всё просто:
графы 2 и 3 изоморфны (и тот и тот состоит из 2-х треугольников с попарно соединёнными вершинами), различия здесь только в способе укладки.

Граф 1 не изоморфен графам 2 и 3, так как он, в отличие от них не планарный.

-- 03.06.2018, 01:44 --

Два последних можно то же "развернуть" в шестигранники, результат будет один и тот же:


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

[arseniiv]

Andrey_Kireew в сообщении #1316946 писал(а):

от первого, как видите, он несколько отличается

Это как раз в общем случае ни о чём не говорит, потому что

Andrey_Kireew в сообщении #1316946 писал(а):

результат будет один и тот же

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

[Евгений Машеров]

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

[Sender]

Евгений Машеров в сообщении #1316991 писал(а):

Хороший инвариант - набор собственных значений матрицы смежности.

Да сам характеристический многочлен вполне сойдёт, нет нужды искать корни.

[Евгений Машеров]

Ну, кому проще вычислить характеристический многочлен, кому с.з. матрицы...

[Andrey_Kireew]

В общем случае arseniiv, это может ни о чём и не говорит, но в данном конкретном случае - говорит, и о многом.
Результаты не могут быть разными, графы 2 и 3 невозможно разложить внутри шестигранника по другому, лишь потому - что грань с 6-ю вершинами у них единственная, и включает в себя сразу все вершины. Поэтому других вариантов просто не остаётся. И одинаковый результат такой раскладки доказывает изоморфность 2 и 3.

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

[arseniiv]

Andrey_Kireew в сообщении #1317008 писал(а):

Результаты не могут быть разными, графы 2 и 3 невозможно разложить внутри шестигранника по другому

А, вы имели в виду, чтобы изображение было выпуклым шестиугольником, дополненным отрезками? Ну тогда да.