Форум на Исходниках.RU

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

mo3r — Fri, 07 Jan 2005 08:39:44 +0000

mo3r: Суть алгоритма:
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[1]<=A[3]<=A[5]<=A[7]. (Два этих шага нужны, чтобы сократить перебор, т.к. такие графы точно изоморфны).
в. Построить по этой таблице граф и проверить его на изоморфность с уже построенными. Если среди построенных графов нет изморфных ему, то где-то записать и увеличить счетчик.

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

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

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

VzLOM — Thu, 06 Jan 2005 20:36:32 +0000

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

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

vk — Thu, 06 Jan 2005 19:35:40 +0000

vk:

Цитата 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 вершина) задать жестко. Чтобы зря алгоритм не гонять.

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

VzLOM — Thu, 06 Jan 2005 18:52:12 +0000

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

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

mo3r — Thu, 06 Jan 2005 17:57:27 +0000

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

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

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

VzLOM — Thu, 06 Jan 2005 16:20:07 +0000

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

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

vk — Thu, 06 Jan 2005 15:20:45 +0000

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

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

VzLOM — Thu, 06 Jan 2005 13:46:53 +0000

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

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

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