Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Le probeme de voyageur de commerce et la coloration des sommets d x27 un graphe

Leçon INTRODUCTION AUX PROBLEMES COMBINATOIRES DIFFICILES LE PROBLEME DU VOYAGEUR DE COMMERCE ET LE PROBLEME DE COLORATION D'UN GRAPHE Dans cette leçon nous présentons deux problèmes très célèbres celui du voyageur de commerce et celui de la coloration d'une carte de géographie Nous commençons par le problème du voyageur de commerce Après en avoir donné la dé ?nition et des exemples d'application nous aborderons le problème du temps de calcul de certains algorithmes et proposerons des méthodes de résolution approchées Nous introduirons ensuite le problème de coloration des sommets d'un graphe Après la dé ?nition et des exemples d'application nous décrirons des méthodes de résolution approchées I Le problème du voyageur de commerce exemple d ? introduction En Procter et Gamble lancèrent un concours pour résoudre le problème suivant Trouver un parcours passant par les villes ?gurant sur la carte ci-dessous et le plus court possible C'était une des premières versions de ce qui deviendra le célèbre problème dit du voyageur de commerce problème étudié par Dantzig dès L'origine de ce nom est assez obscure et probablement peu de voyageurs de commerce l'utilisent Cf http www math Princeton edu tsp car html Le graphe ci-dessous correspond à un problème avec villes en supposant que toutes les liaisons sont possibles Les distances sont mises arbitrairement Leçon Introduction aux problèmes combinatoires di ?ciles CIl s ? agit de partir d ? un sommet et d ? y revenir en parcourant une fois et une seule chaque sommet avec l ? itinéraire le plus court Cet itinéraire est indépendant de la ville de départ Par exemple la longueur de l ? itinéraire a b c d e a à est égale à alors que celle de a b e c d a vaut II Le problème du voyageur de commerce Dé ?nition d'un cycle ou d'un circuit hamiltonien Un cycle hamiltonien est un cycle qui passe une fois et une seule par chaque sommet du graphe On dit aussi tournée ou tour Si le graphe est orienté on dé ?nit de la même manière un circuit hamiltonien Dans un graphe de n sommets le nombre de tournées est égal à n- qui correspond aux nombres de permutations de n- éléments n- et non n car on peut partir d'un sommet quelconque A chaque arête ou arc si le graphe est orienté on a ?ecte un nombre cij qui peut par exemple représenter un coût un temps ou ? une longueur On l ? appelle longueur de l ? arête ou de l'arc Dé ?nition du problème du voyageur de commerce Cas non orienté ou symétrique cij cji Il s'agit de déterminer parmi tous les cycles hamiltoniens celui ou ceux de longueur minimale Cas orienté ou non symétrique cij ?? cji Il s'agit de déterminer parmi tous les circuits hamiltoniens celui ou ceux de longueur minimale Le problème du voyageur de commerce est le cas le plus simple du problème d ? organisation de tournées de livraisons Exemple de problème modélisable par un problème