Перечислите все неизоморфные графы определенного размера.

30

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

Точнее, я хочу алгоритм, который будет генерировать последовательность неориентированных графов со следующим свойством: для каждого неориентированного графа на вершинах существует индекс такой, что изоморфна для . Я хотел бы, чтобы алгоритм был максимально эффективным; другими словами, метрика, которая меня интересует, - это время выполнения для генерации и перебора этого списка графиков. Вторичная цель состоит в том, чтобы было бы неплохо, если бы алгоритм не был слишком сложным для реализации. $G_1,G_2,\dots,G_k$ $G$ $n$ $i$ $G$ $G_i$

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

Моя заявка выглядит следующим образом: у меня есть программа, которую я хочу протестировать на всех графиках размера . Я знаю, что если два графа изоморфны, моя программа будет вести себя одинаково на обоих (она будет либо правильной на обоих, либо неправильной на обоих), поэтому достаточно перечислить хотя бы одного представителя от каждого класса изоморфизма, а затем проверить программа на этих входах. В моем приложении довольно мало. $n$ $n$

Некоторые возможные алгоритмы, которые я рассмотрел:

Я мог бы перечислить все возможные матрицы смежности, т. Е. Все симметричные матрицы 0 или 1, которые имеют все 0 на диагоналях. Однако для этого необходимо перечислить матриц. Многие из этих матриц будут представлять изоморфные графы, так что, похоже, это требует больших усилий. $n\times n$ $2^{n(n-1)/2}$
Я мог бы перечислить все возможные матрицы смежности и для каждой из них проверить, изоморфен ли он любому из графов, которые я ранее выводил; если оно не изоморфно чему-либо, выводимому ранее, выведите его. Это значительно сократило бы выходной список, но все равно потребовало бы как минимум шагов вычисления (даже если мы предположим, что проверка изоморфизма графа является сверхбыстрой), так что по моей метрике это не намного лучше. $2^{n(n-1)/2}$
Можно перечислить подмножество матриц смежности. В частности, если - граф на вершинах , без ограничения общности я могу предположить, что вершины расположены так, что $G$ $n$ $V=\{v_1,\dots,v_n\}$ $\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$ , Другими словами, каждый граф изоморфен таковому, в котором вершины расположены в порядке неубывающей степени. Таким образом, достаточно перечислить только матрицы смежности, обладающие этим свойством. Я не знаю точно, сколько таких матриц смежности, но их гораздо меньше, чем , и их можно перечислить с гораздо меньшим, чем шагов вычисление. Тем не менее, это все еще оставляет много избыточности: многие классы изоморфизма будут по-прежнему покрываться много раз, поэтому я сомневаюсь, что это оптимально. $2^{n(n-1)/2}$ $2^{n(n-1)/2}$

$2^{n(n-1)/2}/n!$ $\sim 2^{n(n-1)/2}/n!$ $n$ $n=5$ $n=8$ $n$

Связанный: Построение неэквивалентных двоичных матриц (хотя, к сожалению, кажется, что никто не получил правильный ответ).

1

n

$n$

O (| output |)

$O(|\text{output}|)$

| output | = Ω (n \cdot | classes |)

$|\text{output}| = \Omega(n \cdot |\text{classes}|)$

n

$n$

n

$n$

n = 6

$n=6$

n

$n$

19

Вероятно, самый простой способ перечислить все неизоморфные графы для малых чисел вершин - это загрузить их из коллекции Брендана Маккея . Алгоритм перечисления описан в статье Маккея [1] и работает, расширяя неизоморфы размера n-1 всеми возможными способами и проверяя, была ли новая вершина канонической. Это реализовано как gengв программе проверки изоморфизма графов Маккея nauty.

[1]: Б.Д. Маккей, Применение метода помеченной нумерации , Congressus Numerantium, 40 (1983) 207-221.

Дэвид Эйзенстат
источник

У меня проблема. Я беру график размера n-1и расширяю его вершинами всеми возможными способами, как вы сказали. Затем я проверяю, есть ли у вершины каноническая метка, скажем 1(каноническая вершина ?!). Однако что, если граф только изоморфен канонической форме, а вершина имеет другую метку? Я попытался проверить автоморфизмы, чтобы увидеть, находится ли вершина с меткой 1на одной и той же орбите, но затем я в итоге дважды попал в мой список. Бумага действительно не помогает мне. Кроме того, исходный код geng не читается из-за всех этих двоичных оптимизаций и практически без комментариев.

Алекс

1

@ Alex Вам определенно нужна версия проверки, которая определяет, находится ли новая вершина на той же орбите, что и 1. Не могли бы вы привести пример, в котором это приводит к двум изоморфным графам? Может быть, это будет лучше, как новый вопрос.

Дэвид Эйзенстат,

Окей, большое спасибо! Я думаю, что в этом случае «расширение всеми возможными способами» необходимо каким-то образом рассмотреть автоморфизмы графа с n-1вершинами? например, n = 3, и мой предыдущий график был P2. Тогда два случая, когда я присоединяю третью вершину к одной из предыдущих вершин, конечно, приведут к одному и тому же графу P3. Не могли бы вы быстро объяснить, как правильно «расширяться всеми возможными способами» или я должен задать это как еще один вопрос? (Кроме того, иногда я путаюсь с тем, что происходит, поскольку моей программе нужно находить неизоморфизмы графа особого типа, что усложняет ситуацию)

Alex

@ Алекс Да, похоже, само расширение должно быть каноническим. Вероятно, стоит новый вопрос, так как я не помню, как это работает на макушке.

Дэвид Эйзенстат,

1

Домашняя страница Nauty

Guy Coder

4

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

$n<6$
$(1,2)$ $(3,4)$ $n=6$

Наивная реализация этого алгоритма заходит в тупик, где оказывается, что матрица смежности не может быть заполнена в соответствии с заданным набором степеней и предыдущими назначениями. Это может стоить некоторых усилий, чтобы обнаружить / отфильтровать это рано. Некоторые идеи:

Если сумма степеней нечетна, они никогда не сформируют график
Заполните записи для вершин, которые должны быть немедленно связаны со всеми / ни одной из оставшихся вершин.

FrankW
источник

3

Эти документы могут представлять интерес.

«О лаконичном представлении графов», Георгий Туран, Дискретная прикладная математика, том 8, выпуск 3, июль 1984 года, стр. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

«Краткое представление общих немаркированных графов», Мони Наор, Дискретная прикладная математика, том 28, выпуск 3, сентябрь 1990 года, с. 303-307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

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

Кроме того, доказано, что функции кодирования и декодирования являются эффективными.

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

РЕДАКТИРОВАТЬ: Этот документ также может иметь отношение к:

Изоморфизм графов в квазиполиномиальное время, Ласло Бабай, Чикагский университет, препринт на arXiv, 9 декабря 2015 г. http://arxiv.org/pdf/1512.03547v1.pdf

Бабай объявил о своем результате в новостях: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

Но, может быть, я ошибаюсь, когда сравниваю вопрос ОП с этими тремя документами? ОП желает перечислить неизоморфные графы, но все же может быть полезно иметь эффективные методы для определения того, являются ли два графа изоморфными?

Саймон
источник

Я ценю эту мысль, но боюсь, я не спрашиваю, как определить, являются ли два графика изоморфными. Я действительно спрашиваю, как перечислить неизоморфные графы. Боюсь, описание алгоритмов для проверки того, являются ли два графа изоморфными, мне не очень помогает - спасибо за попытку!

DW

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

Симон

Бабаи отказался от требования квазиполиномиального времени выполнения . Видимо была ошибка в анализе.

Рафаэль

1

Есть статья начала 90-х, посвященная именно этому вопросу:

Эффективные алгоритмы для перечисления немаркированных графов Лесли Голдберг.

Подход гарантирует, что перечисляется ровно один представитель каждого класса изоморфизма и что между генерацией двух последующих графов существует только полиномиальная задержка.

$n$

Паскаль Велке
источник

Перечислите все неизоморфные графы определенного размера.

Ответы: