Я хотел бы перечислить все неориентированные графы размера , но мне нужен только один экземпляр каждого класса изоморфизма . Другими словами, я хочу перечислить все неизоморфные (неориентированные) графы по n вершинам. Как я могу это сделать?NnnNnn Точнее, я хочу алгоритм, который будет...
Страница проблемы изоморфизма графов Википедии, похоже, указывает на то, что нет, она не была решена. Однако мой друг указал на Алгоритм Полиномиального Времени для Изоморфизма Графов . Я недостаточно опытен, чтобы следовать рассуждениям в газете. У меня есть собственная очень грубая попытка...
Читая некоторые блоги о сложности вычислений (например, здесь ), я усвоил идею, что решить, изоморфны ли две группы, проще, чем тестировать два графа на изоморфизм. Например, на указанной странице говорится, что изоморфизм графов является более общей проблемой, чем изоморфизм групп. Поэтому я...
В случае немаркированных графов проблема изоморфизма графов может быть решена с помощью ряда алгоритмов, которые очень хорошо работают на практике. То есть, хотя наихудшее время выполнения является экспоненциальным, обычно оно имеет полиномиальное время выполнения. Я надеялся, что ситуация...
Я описываю подход к изоморфизму графа, который, вероятно, имеет ложные срабатывания, и мне любопытно, есть ли литература, указывающая, что он не работает. Учитывая две матрицы смежности , по общему признанию наивный метод проверки изоморфизма состоит в проверке, существует ли для каждой строки u...