Перечисление графов с помощью самоконтроля

Question

Брендан Маккей уже проделал работу по поиску всех неизоморфных графов n переменных, которые можно найти здесь (в разделе Простые графы): http://cs.anu.edu.au/~bdm/data/graphs.html

Я полагаю, что это было сделано с помощью перечисления полиа, котороеЯ понимаю основы.Я хотел бы остановиться на этом, и разрешить самостоятельные циклы на этих графиках.Итак, я хотел бы найти все неизоморфные графы n переменных, включая собственные циклы.Это будет напрямую использовано для другой части моего кода и обеспечит массовую оптимизацию.Я просто не совсем уверен, как это сделать.

Для ясности, файлы Брендана Маккея дают все неизоморфные графы, то есть в граничной нотации,

1-2 1-3

- это график с ребром между вершинами 1 и 2 и 1 и 3. Я хочу, чтобы этот список также включал в себя собственные циклы, то есть:

1-2 1-3 1-1

или

1-2 1-3 1-1 2-2

Я хочу минимальное количество графиков, поэтому все неизоморфные.Как я могу найти их, надеюсь, используя данные, доступные Брендану Маккею для простых графиков?

Answer 1

Прежде всего, вы должны заметить, что если два графа не изоморфны, то эти графы с некоторыми дополнительными автопетлями не изоморфны.

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

Проще всего добавить дополнительный узел, и каждый узел с циклом self будет связан с данным узлом. (вместо цикла) Используя nauty, вы можете проверить, являются ли любые два изоморфными. Вы также можете ускорить процесс, если заметите, что если две версии с кодировкой контура имеют iso, то они должны иметь одинаковое количество соединений с «особым» узлом.