Я хотел бы спросить, есть ли уже опубликованный результат по этому вопросу:
Мы берем все возможные разные пути между каждой парой узлов двух соединенных регулярных (со степенью , скажем, числом узлов ) графов и записываем их длины. Конечно, это число различных путей является экспоненциальным. Мой вопрос: если мы отсортируем длины и сравним их (списки, полученные двумя графами), и они абсолютно одинаковы, можем ли мы сказать, что эти два графа изоморфны?н
Конечно, даже если это результат, мы не можем использовать его для ответа за изоморфизм графов, так как число различных путей экспоненциально, как сказано
Под разными путями я имею в виду пути, имеющие, по крайней мере, один другой узел, очевидно.
Спасибо априори за вашу помощь.
Ответы:
Я полагаю, что ответом на ваш вопрос является «нет», потому что эквивалентное условие подразумевало бы решение GI за полиномиальное время.
Для , матрицы смежности графа G , отметим, что число путей от i до j длины k равно ( A k ) i , j (с возможностью повторения вершин и ребер). Для двух графов G 1 и G 2 (с матрицами смежности A 1 и A 2 ) и k ≥ 1 , если вы отсортировали элементы A k 1 и A k 2, то по порядкуA грамм я J К ( АК)я , дж грамм1 грамм2 A1 A2 k ≥ 1 AК1 AК2 Чтобы G 1 была изоморфна G 2 , необходимо, чтобы списки были одинаковыми для всех k .грамм1 грамм2 К
Я считаю, что ваша гипотеза эквивалентна:
Если отсортированные списки элементов из и A d 2 идентичны для k = 1 - n - 1 (верхняя граница на самом длинном пути с неповторяющимися вершинами), то G 1 и G 2 изоморфны.AК1 Ad2 к = 1 n - 1 грамм1 грамм2
Таким образом, чтобы решить GI, нужно только выполнить умножение матриц n × n (и немного дополнительного времени, чтобы отсортировать и сравнить n 2 элементов). Это займет меньше п 4 раз.n - 1 n × n N2 N4
Я допускаю два возможных недостатка в своем аргументе. Во-первых, вполне возможно, что GI имеет алгоритм полиномиального времени и что мы только что обнаружили его вместе, прямо сейчас (ура, мы знамениты!). Я считаю это крайне маловероятным. Во-вторых (и гораздо более вероятно), то, что я предложил, на самом деле не эквивалентно вашей гипотезе.
Последняя мысль. Вы пробовали это для всех, скажем, 3-регулярных графиков для размера 8 или около того? Я думаю, что если ваша гипотеза неверна, то в 3-регулярных графах довольно небольшого размера должен быть встречный пример.
источник
Поскольку вы сравниваете только длины путей (и в то же время забываете, какой паре узлов они соответствуют, если я вас хорошо понимаю), я думаю, что очень похожие графики должны дать контрпример: в конце концов, вы просто считаете количество путей фиксированной длины и независимо от вершин, которые они связывают. Например, я думаю, что эти графики являются контрпримером: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif и http://www.mathe2.uni-bayreuth.de/ Markus / REGGRAPHS / GIF / 06_3_3-1.gif
Если я не ошибаюсь (подсчет путей утомителен), у них обоих 9 путей длиной 1, 18 путей длины 2, 48 путей длины 3, 30 путей длины 4 и 36 путей длины 5
источник
источник