подсчёт кол-ва неизоморфных графов , все варианты попарно неизоморфных графов

Во первых приветсвую всех юзеров,профи программеров и админов сего ресура, ну и поздравляю с праздниками.
А вопрос в следующем: дали мне курсовик, давно, ясно дело, тока я как самый настоящий студень, протянул срок до сессии:)
а задание такое:

Написать программу на любом языке программирования (желательно на С, подсчитывающюю количество попарно НЕ изоморфных графов с n вершинами и 4мярёбрами.

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

Сообщение отредактировано: VzLOM - 06.01.05, 13:51

В каких конкретно местах встал? Давай свою эту пару мест. Если успею и смогу, помогу. Хотя скорее всего, кто-нибудь более умный и быстрый раньше поможет.

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

А не проще ли просто строить неизморофные - их всего-то ничего.

Добавлено 06.01.05, 18:03
Во-первых, если n>=8, то, по-моему, ответ будет такой же, как и при n=8.
Если n=1, то ответ = 0. (т.к. нету петель).
Если n=2, то ответ = 1. (Все 4 ребра между 2 вершинами).
Дальше надо рассматривать варианты.

да, но варианты должен разбирать комп, и ещё я не очень понял почему при n>8 такойже ответ что и при 8

Цитата mo3r,6.01.05, 20:57 @ 07.01.70, 13:33

А не проще ли просто строить неизморофные - их всего-то ничего.

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

А как найти количество всех неизоморфных? Неужели только перебором? Ну, в конце концов, можно и перебором. Это же курсовой, а не оптимизационная задача.
А можно и не перебором, можно начать с варианта "все 4 ребра между двумя вершинами", а потом перебрасывать по одному ребру в другую ячейку матрицы. С возвратом.

Цитата mo3r,6.01.05, 20:57 @ 07.01.70, 13:33

Во-первых, если n>=8, то, по-моему, ответ будет такой же, как и при n=8.

Да, мне тоже так показалось. Ведь ребер всего четыре, так? Значит, на 8 вершинах мы получаем последний раз увеличение числа неизоморфных - вариант, когда ни одно ребро не смежно другому. Для n>8 новых вариантов не появится.

Цитата VzLOM,6.01.05, 21:52 @ 07.01.70, 13:34

да, но варианты должен разбирать комп

Оно конечно, но никто тебе не мешает решение первых двух (а то и трех) вариантов (0 и 1 вершина) задать жестко. Чтобы зря алгоритм не гонять.

Сообщение отредактировано: vk - 06.01.05, 19:36

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

Суть алгоритма:
1. Если n = 1, выдать 0, если n = 2, выдать 1.
2. Если n > 8, то n = 8.
3. Делаем массив A из 8 элементов (A[1], A[2] - концы 1-го ребра, A[3],A[4] - 2-го ребра и т.д.), перебираем всевозможные варианты расположения в каждом элементе чисел от 1 до n (т.е., всего вариантов = n^8). Для каждого расположения выполнить следующие шаги:
а. Проверить, что A[1]<A[2], A[3]<A[4], A[5]<A[6], A[7]<A[8].
б. Проверить, что A[1]<=A[3]<=A[5]<=A[7]. (Два этих шага нужны, чтобы сократить перебор, т.к. такие графы точно изоморфны).
в. Построить по этой таблице граф и проверить его на изоморфность с уже построенными. Если среди построенных графов нет изморфных ему, то где-то записать и увеличить счетчик.

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

По A граф строится так: есть матрица смежности C[1..n,1..n]. Она строится так (нас интересует только часть выше главной диагонали): для каждого i = 1..4: увеличиваем на единицу C[A[2*i-1],A[2*i]].