Закономерности тождественных графов

[Dims]

Есть такое понятие "тождественный граф"

Тождественный граф из одной вершины есть просто одна отдельная вершина. Тождественных графов из 2, 3, 4 и 5 вершин не существует. Тождественных графов из шести вершин восемь штук. Тождественных графов из 7, 8, 9,... вершин соответственно 152, 3696, 135004, ...

Вопрос: есть ли тут какая-то закономерность? Или эта задача подобна поиску простых чисел? Как задача классифицируется по шкале сложности?

[Руст]

То, что при n>5 всегда существуют тождественные графы с n вершинами очевидно. Легко доказать, что количество тождественных графов растёт быстрее, чем полиномиально. Для значений такого рода функций (целочисленных, растущих быстро), возникающих из комбинаторики, имеются кажущаяся случайность и не более того. Но вряд ли здесь есть связь с распределением простых чисел.

[Dims]

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

P.S. Аналогия с простыми числами: там, чтобы проверить, что число простое, надо перебрать все делители (или почти все, насколько я знаю, можно перебирать все ранее найденные простые числа, меньшие корня из проверяемого).

[Dims]

Появилось ещё ряд вопросов, в связи с чем переименовал тему.

1)

Из каждого тождественного графа можно получить ещё один тождественный граф, заменив в матрице смежности 0 на 1 и наоборот. Если каждая такая замена будет давать неизоморфный исходному граф, то количество тождественных графов должно быть всегда чётно. Так ли это? Может ли быть, чтобы такой граф (назовём его инвертированным) совпал с исходным (с точностью до изоморфизма)?

2)

Рассмотрев 8 тождественных графов из 6 вершин, я обратил внимание, что один из них (первый) является подграфом всех остальных (и вообще, все можно получить из первого добавлением рёбер).

Вопрос: все ли тождественные графы таковы? Существуют ли тождественные графы с количеством вершин Н, для которых ни один из тождественных графов с количеством вершин М<Н не является подграфом?

[Руст]

Dims писал(а):

Появилось ещё ряд вопросов, в связи с чем переименовал тему.

1)

Из каждого тождественного графа можно получить ещё один тождественный граф, заменив в матрице смежности 0 на 1 и наоборот. Если каждая такая замена будет давать неизоморфный исходному граф, то количество тождественных графов должно быть всегда чётно. Так ли это? Может ли быть, чтобы такой граф (назовём его инвертированным) совпал с исходным (с точностью до изоморфизма)?

2)

Рассмотрев 8 тождественных графов из 6 вершин, я обратил внимание, что один из них (первый) является подграфом всех остальных (и вообще, все можно получить из первого добавлением рёбер).

Вопрос: все ли тождественные графы таковы? Существуют ли тождественные графы с количеством вершин Н, для которых ни один из тождественных графов с количеством вершин М<Н не является подграфом?

Я не очень интересуюсь задачами относительно графов и не специалист. Тем не менее, второй вопрос тривиальный (решается за пару секунд).
В любом тождественном графе имеется некоторый минимальный тождественный подграф похожий на первый. Однако при n>6 минимальные тождественные графы выглядят иначе, точнее имеется один узел имеющий 3 ребра, исходящих из узла и три длины хвостов k<l<m. При этом k+l+m=n-1.

[Dims]

Видимо, я ещё меньший специалист, так как ничего не понял

Нельзя ли объяснить попонятнее?

[Руст]

Во, первых любой граф разлагается на сумму связных компонент. Связные компоненты тождественного графа будут так же тождественными и не изоморфными между собой. Поэтому достаточно классифицировать связные тождественные графы. Так как простейший связный граф цепочка не является тождественным, то любой связный тождественный граф имеет узел, где примыкают по крайней мере 3 ребра.
Назовём связный тождественный граф минимальным, если любой его подграф или не связный или не тождественный. Когда n=6 минимальный тождественный граф содержит цикл. Я считал, что при n>6 всегда можно разрывать циклы и получить минимальные связные тождественные графы. Однако, я неправильно продолжил эту идею при классификации минимальных тождественных графов. В принципе минимальными тождественными графами могут быть не только указанного вида деревья.

[Dims]

Руст писал(а):

Когда n=6 минимальный тождественный граф содержит цикл.

До сюда понятно

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

[Руст]

Dims писал(а):

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

Нет, если тождественный граф не содержит никакой другой тождественный граф, то он минимален.

[Dims]

Ну так что, минимальный тождественный граф один единственный?

[Руст]

Нет. Минимальных тождественных графов может быть много. Например любое разбиение числа n-1 на как минимум 3 различных слагаемых определяет минимальный тождественный граф. К примеру n=16, n-1=15 дает 15= 1+2+3+4+5= 1+2+3+9= 1+2+4+8= 1+2+5+7= 1+3+4+7= 1+3+5+6= 2+3+4+6= 1+2+12= 1+3+11= 1+4+10= 1+5+9= 1+6+8= 2+3+10= 2+4+9= 2+5+8= 2+6+7= 3+4+8= 3+5+7= 4+5+6
уже дает 19 минимальных тождественных графа.

вставил пробелы в текст // нг

[Dims]

Что-то я не врубаюсь. Что дают эти разложения?

Вот, например, для 7 узлов. Есть ли из 152 графов из 7 узлов, по Вашему, граф, который не сводим ни к одному из 8 тождественных графов из 6 узлов?

[Руст]

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

[maxal]

см. также A003400