Найти путь гамильтониана в турнире со списками смежности в Python

Question

Турнир - это полный, ориентированный граф, такой, что для любых двух вершин u и v существует направленное ребро между ними (если вы выиграли над v, то ребро от u до v).

Гамильтонова дорожка всегда существует в турнире. Таким образом, учитывая списки смежности в форме {u:[v,w],v:[w]}, где есть направленное ребро от u до w, от u до v и от v до w, как мне найти, что такое гамильтонов путь есть и распечатать вершины по порядку?

Даже если вы не знаете Python или что-то еще, только алгоритм будет очень полезным. Я думал об этом, и я полагаю, я должен начать с вершины высшей степени? Затем добавьте вершину со второй наивысшей степенью и т.д. до вершины с наименьшей степенью. Но я не вижу, как это отказоустойчивый метод, вершина с наивысшей степенью могла бы быть побеждена вершиной со вторым наивысшим.

Спасибо за любую помощь заранее!

Answer 1

Вы можете решить эту проблему рекурсивно. Предположим, у вас есть n+1 названные вершины v_0 в v_n, v_1 в v_n и ребра между ними для турнира размером n, поэтому мы можем предположить, что у нас есть гамильтонова дорожка, содержащая v_1 в v_n, Переименуйте их в соответствии с этим путем u_1 в u_n, Теперь найди u_i такой, что u_i победил v_0 а также v_0 победил u_i+1 (Здесь вы должны позаботиться о маргинальных узлах: v_0 победил u_1 или же u_n победил v_0). После нахождения таких iОбщий путь гамильтониана может быть построен как:

u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n

Этот алгоритм имеет время выполнения O(n^2). Для этой задачи существует алгоритм O(nlogn).