Всем добрый день.
Мне нужно сгенерировать все графы следующего типа:
1. Направление ребер не имеет значения;
2. Количество ребер не больше 20;
3. Граф должен быть связным;
4. Граф не должен содержать петель и кратных ребер;
5. Граф должен состоять только из циклов (не должно быть вершин степени 1).
Затем нужно среди изоморфных графов оставить только один.
Время работы программы в принципе не важно (но должно быть в разумных пределах, не больше 15 мин.). Есть идеи?

Brute-force, I suppose.
Your description is not quite clear: "only from cycles" and "no vertices of degree one" is different things.
If only from cycles - then a good way to generate such graphs is firstly to take "ring" (brute-force different ones), then take different pairs of vertices in it and connect them with "threads" (also trying different lengths), one the next step again take all pairs of vertices and connect them, and so on. Normalization is as usual. I suppose, number of such graphs should not be too large.

Спасибо! Есть идеи как удалить изоморфные графы?

Edited by author 17.12.2010 09:19

up

As usual: introduce some normalization procedure, then if the result of normalization coincides with the initial graph - then it is the representative of isomorphic group, otherwise it is not.
But the first thing to do is to try to generate as few isomorphic graphs as possible in your brute-force procedure.

Я этого никогда раньше не делал, поэтому довольно плохо себе все представляю. Что за процедура нормализации? Можно поподробнее? И я плохо понимаю по-английски, пиши мне в следующий раз на почту, r1d1-911@mail.ru

Edited by author 17.12.2010 21:55