Comment trouver le nombre de chemins hamiltoniens dans un graphique?

Question

Je suis d'essayer ce problème Google Code Jam qui dit trouver nombre de chemins hamiltoniens si on enlève k arêtes d'un graphe complet

lien à la question

https://code.google.com/codejam/contest/32004/dashboard#s=p2

j'ai compris que nous pouvons utiliser le principe d'exclusion d'inclusion pour trouver le numéro

mais mon problème est de savoir comment déterminer le nombre de chemin lorsque nous considérons que certains «x» nombre d'arêtes ont été retirés du graphe complet (les arêtes enlevées sont données)

Answer 1

L'idée est de compter les permutations au lieu de compter les chemins. De cette façon, chaque chemin serait pris en compte 2 * n fois.

Le nombre total si permutations est n !.

Utilisons le principe de l'incul- sion-exlusion pour compter les mauvais cycles. Si un bord est interdit, il y a 2 * n * (n-2)! chemins qui contiennent ce bord (nous plaçons deux sommets adjacents ensemble et le reste va n'importe où).

S'il existe plusieurs arêtes interdites, tous les vetrices sont divisés en plusieurs groupes indépendants (ils forment des chaînes reliées par ces arêtes). Il y a deux façons de placer chaque groupe (comme il peut être inversé). Tous les groupes peuvent être permutés arbitrairement les uns avec les autres. Le reste des éléments peut être placé n'importe où (il contribuerait en tant que coefficient binomial fois quelque factoriel). Il y a une autre mise en garde: une chaîne peut s'enrouler. Mais il peut y avoir au plus une telle chaîne. Nous pouvons donc parcourir la chaîne qui enveloppe et compter le nombre de façons de placer le reste en utilisant l'algorithme décrit ci-dessus.