Existe-t-il une méthode suffisante pour determiner si un graphe est Hamiltonien?

[oggy27]

Bonjour!
Tout est dans le titre. Si quelqu'un a quelque chose à proposer
Merci
-----

[Seirios]

Bonsoir,

Tu as déjà regardé ce que proposait wikipédia ?

[oggy27]

Oui mais je suis étonné qu'il n'existe aucun outils, aucune méthode pour ça

[JohnArto]

Bonjour
quand vous parlez de "méthode", vous pensez algorithme théorique seulement, ou spécifiquement efficace ?

[A voir en vidéo sur Futura]

[oggy27]

spécifiquement efficace oui, mais la méthode peut être aussi un critère comme celui pour les graphes eulériens.

[minushabens]

Ta question telle qu'elle est formulée n'est pas très intéressante. Par exemple une condition suffisante pour un graphe d'être hamiltonien est qu'il n'ait qu'un unique sommet. On peut trouver beaucoup de conditions suffisantes de ce genre qui n'ont aucun intérêt. Il en existe de plus générales, par exemple un graphe à n sommets dont le degré minimal est n/2 ou plus est hamiltonien.

[oggy27]

Oui je vois, je parlais d'une méthode qui est suffisant dans le sens où elle peut dire si un graphe est hamiltonien ou non, qu'importe le graphe.

[Deedee81]

Salut,

Oui je vois, je parlais d'une méthode qui est suffisant dans le sens où elle peut dire si un graphe est hamiltonien ou non, qu'importe le graphe.

Pour un graphe quelconque et donc nécessaire et suffisant. Il n'existe pas de critère nécessaire et suffisant pour dire si un graphe quelconque est hamiltonien. Ce qui n'est pas très étonnant. La recherche d'un circuit hamiltonien est un problème NP-complet.

[oggy27]

Je ne pense pas que le fait de trouver un circuit soit np-complet rend l'identifcation d'un graphe comme étant np. Mais bon après je ne suis pas un professionnel.

[oggy27]

Je ne pense pas que le fait de trouver un circuit soit np-complet rend l'identifcation d'un graphe comme étant np. Mais bon après je ne suis pas un professionnel.

Correction:
Je ne pense pas que le fait de trouver un circuit soit np-complet entraine que l'identifcation d'un graphe comme étant hamiltonien soit np. Mais bon après je ne suis pas un professionnel.

[Deedee81]

Je ne pense pas que le fait de trouver un circuit soit np-complet entraine que l'identifcation d'un graphe comme étant hamiltonien soit np. Mais bon après je ne suis pas un professionnel.

Bonne remarque. Je ne suis pas mathématicien non plus. Par contre, l'absence de critère, c'est exact. En tout cas c'est indiqué dans wikipedia (qui n'est pas à l'abri d'une erreur ).

[minushabens]

Oui je vois, je parlais d'une méthode qui est suffisant dans le sens où elle peut dire si un graphe est hamiltonien ou non, qu'importe le graphe.

ce que tu cherches est donc une condition nécessaire et suffisante.