эквивалентность графов

[sab123]

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

http://babkin-cep.blogspot.com/2018/06/graph-equivalence-1-overall-algorithm.html

Comments

[spamsink]

Я не совсем понял, как, скажем, для полного графа с 10 вершинами без одного ребра получится один и тот же хэш независимо от порядка назначения идентификаторов вершинам.

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

[sab123]

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

Задача да, эквивалентна задаче с матрицами, но нет, алогоритмов не хватает.

[spamsink]

Задача называется https://en.wikipedia.org/wiki/Graph_isomorphism_problem

Если докажешь, что твой алгоритм работает - публикуйся.

[sab123]

Ну, типа доказал (см. части 3-4). Так сказать, в пределах своих способностей. А где публиковаться (или где искать желающих проверить доказательство) - я без понятия.

[spamsink]

Попробуй написать алгоритм определения изоморфизма непомеченных графов: просто или матриц инциденции, или двух vector<set<int>> Наружный вектор индексируется номером узлов, элемент наружного вектора - множество номеров узлов, соединенных дугами с данным; ненаправленность или обещается, или форсируется предварительным проходом.

Потом можно тестировать: генерировать случайный граф с количеством дуг примерно 50% от полного графа, делать случайную перестановку номеров узлов, сравнивать. Проверять на графах размером 10 узлов, 100 узлов, 1000 узлов.

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

Или проще: публикуешь ссылку http://babkin-cep.blogspot.com/2018/06/graph-equivalence-1-overall-algorithm.html на /r/programming - тут тебе и отрецензируют, и докажут, где ты неправ, и найдут контрпримеры...

[sab123]

Я делал полный набор перестановок для избранных графов из 5-7 элементов. Ну, и эта штука изначальна написана для поиска и классификации подграфов в большом графе. Там я ее прогонял с примерно полумиллионом найденных подграфов из 10 элементов. Вручную, конечно, их все не проверишь, но по общим ощущениям выглядит внятно (находит большое количество повторений вокруг узлов с большим количеством связей). А про реддит - это мысль. Я уже выложил ссылки на стэковерфлове и кворе, где про такое спрашивали.