[Szael]

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

@темы: Теория графов, Дискретная математика

Comments

[Гость]

как решить предел при х стремящмся к 0 от (цох + син^2 3х) в степени х^-2

[remonortsa2]

Насколько я себе это представляю. (Дискретную математику изучал давно и это было неправдой) Так что исправления welcome.
Пусть графы у нас будут неориентированые и без петель. (Cамый простой случай.)
Порядок=кол-во вершин=`n`

Попарно неизоморфные значит любые 2 графа из ответа к задаче не изоморфны друг другу.

1. Графы будем задавать матрицей смежности. На ее диагонали д.б. только нули, т.к. условились считать, что графы без петель, и матрица будет симметрична (относительно главной диагонали), т.к. это не орграф.

2. Постараемся для начала ответить на вопрос задачи для меньших порядков n=1,2,3

3. Рассмотрим матрицу смежности для n=1.
`А=(0)`
Понятно, что граф будет состоять из одной вершины. Значит множество всех попарно неизоморфных графов 1-го порядка будет состоять из одного этого графа. Для n=1 ответ на вопрос задачи мы получили.

4. Рассмотрим матрицы смежности для n=2.
`А_1=((0 \ \ 0),(0 \ \ 0))`
`А_2=((0 \ \ 1),(1 \ \ 0))`

Вот эти два графа и будут составлять множество всех попарно неизоморфных графов 2-го порядка.

5. Рассмотрим матрицу смежности для n=3.
`А_1=((0 \ \ 0 \ \ 0),(0 \ \ 0 \ \ 0),(0 \ \ 0 \ \ 0))`
`А_2=((0 \ \ 0 \ \ 1),(0 \ \ 0 \ \ 0),(1 \ \ 0 \ \ 0))`
+ к `A_2` будут еще два изоморфных графа (получаются перенумерацией вершин).

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

`А_3=((0 \ \ 1 \ \ 1),(1 \ \ 0 \ \ 0),(1 \ \ 0 \ \ 0))`
`А_4=((0 \ \ 1 \ \ 1),(1 \ \ 0 \ \ 1),(1 \ \ 1 \ \ 0))`

Таким образом, графы, задаваемые матрицами смежности `A_1, A_2, A_3, A_4` и будут множеством всех попарно неизоморфных графов 3-го порядка.

[Гость]

В трехреберных графах вы забыли случай, когда ребра образуют треугольник.
В четырехреберных случаях упущен случай, когда граф имеет более одной компоненты связности.
Не рассмотрены 5-, 6-, 7-, 8-, 9-, 10-реберных графов.
Скорее всего, задание на придумывание алгоритма перебора всех попарно неизоморфных графов (необязательно прям все рисовать, главное, придумать действенный алгоритм построения каждого из них).