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

[Dimansel]

Только начинаю изучать теорию графов, не пойму как решать такого вида задачи:
Сколько существует попарно неизоморфных простых кубических графов с шестью вершинами?

[provincialka]

А вам как нужно? С помощью элементарных рассуждений или со ссылкой на теорию?

Если элементарными... Ну, разберите случаи,когда в графе есть треугольник (цикл из 3 вершин) и когда нет.

[Dimansel]

provincialka
Разобрал, получается, всякий простой кубический граф с шестью вершинами, имеющий треугольники неизоморфен неимеющему треугольников и изоморфен всякому другому имеющему треугольники, так?

[provincialka]

Хм... какие циклы смотря! Какие-нибудь-то есть.

Dimansel в сообщении #1121496 писал(а):

имеющий циклы неизоморфен неимеющему циклов

Вот с этим не поспоришь! А остальное надо доказывать.

[Dimansel]

provincialka
Исправил на треугольники. То есть изоморфизм каких-либо двух простых кубических графов с шестью вершинами, который имеет треугольники надо доказывать?

[provincialka]

Конечно. Вот, есть у вас треугольник, цикл из трех элементов. От каждого "свисает" по одному ребру, которое надо присоединить к одной из трех оставшихся вершин $A,B,C$. А вдруг два из этих ребер сходятся в одной вершине, например, $A$? Почему этого не может быть?

[Dimansel]

provincialka
В таком случае это не будет циклом из трёх вершин, будут кратные рёбра.

[provincialka]

Хм... непонятно. Вот, у вас 3 вершины, $P,Q,R$ все попарно соединены. Значит, из каждой выходит по 2 ребра "друг в друга". Ещё есть по одному ребру в каждой вершине, которые соединяют ее с одной из вершин $A,B,C$. Каждая из которых также должна иметь степень 3. Как можно организовать это соединение? Почему нельзя по-другому?

[svv]

У меня есть простой кубический граф с шестью вершинами. У моего знакомого тоже есть простой кубический граф с шестью вершинами. Мы хотим проверить, что они изоморфны, а для этого попробовать установить между ними биекцию. Я говорю:
— Я выбираю в моём графе некоторую вершину и обозначаю её $A$.
Знакомый отвечает:
— Я тоже выбираю у себя некоторую вершину и обозначаю её $A$.
— Вершина $A$ смежна трём другим вершинам, обозначим их $B_1, B_2, B_3$. Может быть, для установления биекции эти имена потом придётся «переставить», но пока так.
— Да, у меня тоже так, и я поступаю аналогично.
— В моём графе есть ещё две вершины, которые не были названы. Обозначим их $C_1$ и $C_2$.
— Хорошо, я делаю то же самое.
— У меня вершины $C_1$ и $C_2$ соединены ребром.
— А у меня нет.

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

[Dimansel]

provincialka
А, понял. Ну тогда, каждая из вершин P, Q, R соединяется с одной из A, B, C, причём никакие две из вершин P, Q, R не могут соединиться с одной и той же вершиной из A, B, C, иначе некоторые вершины не будут иметь степень 3 и вершины A, B, C не будут формировать цикл.

svv
Да, суть я теперь понял.

[provincialka]

Dimansel в сообщении #1121584 писал(а):

иначе некоторые вершины не будут иметь степень 3 и вершины A, B, C не будут формировать цикл.

Ну, это тоже бы надо объяснить. Например, так:

Из каждой вершины $A,B,C$ можно провести не более 2 ребер в эти же вершины, значит, хотя бы одно ребро должно соединять каждую из них с вершинами $P,Q,R$. Но в эти вершины "извне" могут входить только по одному ребру. Значит, каждая из вершин $A,B,C$ соединена ровно с одной вершиной $P,Q$ или $R$. Оставшимися 3 ребрами вершины $A,B,C$ соединены между собой.

И аналогично разберите второй случай, когда циклов длиной 3 нет.