Алгоритмический возврат.Подсчитать идеальное соответствие в графе

Question

Итак, я студент CS, и нас попросили построить программу обратного отслеживания в c (без рекурсии без циклов), которая получает матрицу смежности неориентированного невзвешенного (без лифта) графа и возвращает число идеальных соответствий. на этом графике или ноль в противном случае. Я думал об использовании алгоритма fkt, который использует ориентацию pfaffian, но до сих пор я не понял, как это сделать. Если бы вы могли быть очень добрыми и, возможно, направить меня к правильной книге или правильному взгляду на этот вопрос, я был бы очень благодарен. Это первый раз, когда я пытался вернуться назад, и мне кажется, что мне не хватает некоторых базовых представлений о том, как реализовать такую ​​вещь.

Answer 1

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