On sait qu'il est NP-complet de tester si un cycle hamiltonien existe dans un graphe à 3 réguliers, même s'il est planaire (Garey, Johnson et Tarjan, SIAM J.Comput.1976) ou bipartite (Akiyama, Nishizeki, et Saito, J. Inform. Proc. 1980) ou pour tester si un cycle hamiltonien existe dans un graphe à...
On sait que le cycle hamiltonien (jambon en abrégé) est NP-complet et que le cycle planaire du jambon est NP-complet. La preuve pour Planar Ham Cycle n'est pas de Ham Cycle. Existe-t-il un joli gadget qui, étant donné un graphe G, remplacera tous les croisements par un gadget plan afin que vous...
Le problème de chemin le plus long est NP-difficile. La preuve (typique?) Repose sur une réduction du problème du chemin hamiltonien (qui est NP-complet). Notez qu'ici, le chemin est considéré comme (nœud-) simple. Autrement dit, aucun sommet ne peut apparaître plus d'une fois dans le chemin....
Le problème du cycle hamiltonien (HC) consiste à trouver un cycle passant par tous les sommets d'un graphe non orienté donné. Le problème des vendeurs ambulants (TSP) consiste à trouver un cycle qui passe par tous les sommets d'un graphique pondéré sur les bords et minimise la distance totale...
Je recherche des problèmes fortement NP-durs pour une réduction. Jusqu'à présent, j'ai trouvé les problèmes suivants: Problème de 3 partitions problème de bin-packing Correspondance numérique tridimensionnelle TSP Tout problème NP-complet sans données numériques, par exemple, SATISFACILITÉ, CYCLE...
Soit un graphe non orienté. Une décomposition de en sous-ensembles disjoints est appelée une décomposition de Hamilton de si le sous-graphe induit par chaque ensemble est soit un graphe de Hamilton, soit un seul bord avec .V V iG = ( V, E)g=(V,E)G=(V,E)VVVVjeVjeV_iV i | V i | = 2ggGVjeVjeV_i| Vje|...
kkk points distincts sont choisis au hasard dans une grille . (Évidemment et est un nombre constant donné.) Un graphique pondéré complet est construit à partir de ces points de telle sorte que le poids de l'arête entre le sommet et le sommet est égal à la distance Manhattan de deux sommets sur la...