Chapitre 6: Graphes eulériens et hamiltoniens 6.1 Introduction et les
Si ce chemin est fermé on parlera de cycle eulérien. • Un chemin hamiltonien est un chemin dans le graphe qui passe par tous les sommets une et une seule
Cours 7 - voyageur de commerce cycle et chemin hamiltonien
Un chemin hamiltonien est un chemin simple qui contient tous les sommets du graphe. • Sortie : OUI si G contient un chemin hamiltonien NON sinon. 13/14
NP complétude du problème de lexistence dun chemin hamiltonien
Un chemin dans G est dit hamiltonien lorsqu'il passe une et une seule fois par chaque sommet du graphe. Définition 2. On note HAM(G s
Chemin et circuit hamiltonien Exercice 3 : Eléments de solutions
Si vous voyez des erreurs prévenez moi. Exercice 3 :Chemin et circuit hamiltonien. En utilisant le fait que le problème du chemin hamiltonnien est NP-.
Cheminement eul´erien et hamiltonien 1 Chemins eulériens
chemin hamiltonien est un circuit ou un chemin passant une et une seule fois par tous les sommets de G. Un graphe est hamiltonien s'il admet un cycle ...
Algorithmes quantiques cycles hamiltoniens et la k-coloration des
4 avr. 2016 ... hamiltonien. Le problème du chemin hamiltonien consiste à : - Trouver une chaîne hamiltonienne ou un cycle hamiltonien dans un graphe non ...
ne Condition SuiTsante dExistence dun dans un Graphe Oriente
11 possedera un circuit hamiltonien passant necessairement par l'arc (zO zt) d'oti dans G urn circuit plus long que X
Calculabilité Combinatoire et Complexité
Chemin Hamiltonien est NP-difficile : Réduction de CNF-SAT à Chemin Hamiltonien. Réductions. 10 / 7. Page 6. Transformer une formule φ en graphe Gφ. Donnée de
Cycles eulériens et hamiltoniens
Un cycle qui passe exactement une fois par chaque sommet d'un graphe est dit. « hamiltonien ». En effet le parcours de la souris depuis sa cage jusqu'à sa ...
Algorithme dEuler pour trouver un circuit hamiltonien dans le cas du
Le jeu (en solitaire) consiste à trouver un parcours pour un cavalier aux échecs qui passe une fois et une seule par chaque case de l'échiquier. L'article d'
Chapitre 6: Graphes eulériens et hamiltoniens 6.1 Introduction et les
Si ce chemin est fermé on parlera de cycle eulérien. • Un chemin hamiltonien est un chemin dans le graphe qui passe par tous les sommets une et une seule
NP complétude du problème de lexistence dun chemin hamiltonien
Un chemin dans G est dit hamiltonien lorsqu'il passe une et une seule fois par chaque sommet du graphe. Définition 2. On note HAM(G s
Chemin et circuit hamiltonien Exercice 3 : Eléments de solutions
En utilisant le fait que le problème du chemin hamiltonnien est NP- ment si L décrit un chemin hamiltonien du graphe G. C'est à dire que L est.
chemins et circuits hamiltoniens
problème posé : Trouver un chemin ou un circuit hamiltonien sur n'importe quelle figure géométrique. définitions : Un chemin hamiltonien passe une
Algorithme dEuler pour trouver un circuit hamiltonien dans le cas du
L'article d'Euler est antérieur de plus d'un siècle à la publication du jeu icosien d'Hamilton. Il s'agit néanmoins d'un cas particulier de chemin hamiltonien.
Chapitre 13 Théorie des graphes
Un chemin dans un graphe orienté est une séquence (suite) de sommets et d'arcs Un chemin Hamiltonien est un chemin qui contient chaque sommet exactement.
Définition : Une matrice A=[aij] est booléenne si tous ses éléments
Chemins Circuits
Le problème du voyageur de commerce
Un problème lié au TSP est le problème du chemin hamiltonien : étant donné un graphe. (donné par matrice ou listes d'adjacence) et deux sommets A et B
Cycles eulériens et hamiltoniens
Un cycle qui passe exactement une fois par chaque sommet d'un graphe est dit. « hamiltonien ». Certains graphes ne possèdent ni cycle hamiltonien ni cycle
Hamiltonicité dans une grille un jeu denfant ?
En coupant le cycle au niveau de A on a un chemin hamiltonien partant de A. Fig. 2 – Circuit hamiltonien dans une grille paire. Pour les grilles impaires (
Searches related to chemin hamiltonien PDF
• Un chemin hamiltonien est un chemin dans le graphe qui passe par tous les sommets une et une seule fois Si ce chemin est fermé (i e il existe une arête reliant le sommet de départ au sommet d'arrivée) on parlera de cycle hamiltonien • Un graphe est dit hamiltonien s'il possède un cycle hamiltonien
What is the problem of Chemin hamiltonien?
Le problème du chemin hamiltonien est le problème de décision qui consiste, étant donné un graphe, à décider s'il admet un chemin hamiltonien. Ce problème est NP-complet, c'est-à-dire qu'on sait vérifier une éventuelle solution dans un temps polynomial en fonction du nombre
Is a Hamiltonian path NP-complete?
A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete .
What is a Hamiltonian cycle?
A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
What is a Hamiltonian graph?
A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph .
Cycles eulériens et hamiltoniens
Complément au chapitre 6 " La souris et la puce »Commençons par rappeler quelques définitions que nous avons déjà données dans le
chapitre traitant des graphes de ligne.Définition
Un cycle qui passe exactement une fois par chaque arête d"un graphe est dit " eulérien ». Un cycle qui passe exactement une fois par chaque sommet d"un graphe est dit " hamiltonien ». Certains graphes ne possèdent ni cycle hamiltonien ni cycle eulérien, par exemple celui- ci-dessous. Notons qu"on définit de la même manière les chaînes hamiltoniennes et eulériennes, en remplaçant cycle par chaîne. Le graphe ci-dessus a une chaîne hamiltonienne, par exemple : d-c-a-b. Le graphe ci-dessus a également une chaîne eulérienne, par exemple : d-c-a-b-c.Applications
Un voyageur de commerce part tous les matins de son domicile représenté en noir ci-dessous et doit rendre visite à un ensemble de clients représentés en blanc, puis
retourner à son domicile. Comment doit-il s"y prendre pour minimiser la distance totale parcourue. (On suppose que les distances entre toutes les paires de clients ainsi qu"entre les clients et le domicile du voyageur de commerce sont connues). On cherche ici un cycle hamiltonien de longueur minimale. Un camion de ramassage des ordures part du dépôt représenté en noir ci-dessous et doit passer sur chaque route du réseau ci-dessous pour effectuer la collecte des déchets. Comment doit-il s"y prendre ? On cherche ici un cycle eulérien.Les cycles (pas nécessairement hamiltoniens ou eulériens) partagent une propriété
importante que Manori fait remarquer à Sébastien lorsqu"il tente de retrouver la souris. Cette propriété énoncée ci-dessous peut facilement être étendue aux chaînes.Propriété
Lorsqu"on dessine un cycle dans un graphe, tous les sommets sont nécessairement de degré pair car à chaque fois qu"en entre en un sommet, on en ressort aussi. Lorsqu"on dessine une chaîne dans un graphe, tous les sommets intermédiaires (c"est- à-dire tous ceux qui ne sont pas les extrémités de la chaîne) sont de degré pair. C"est cette propriété que Manori utilise pour retrouver la souris. En effet, le parcours dela souris depuis sa cage jusqu"à sa cachette est un cycle (si elle se cache dans le
laboratoire d"où elle s"est enfuie) ou une chaîne. Manori dessine le graphe contenanttoutes les arêtes que la souris a parcourues. Il peut le faire grâce aux informations
fournies par les détecteurs. Son raisonnement est le suivant : · si tous les sommets du graphe sont de degré pair, la souris est revenue à son point de départ et il va être difficile de la retrouver; · si le graphe ne comporte que deux sommets de degré impair, l"un de ces sommets est le lieu de sa fuite, et l"autre le lieu de sa cachette; · si le graphe comporte plus de deux sommets de degré impair, l"information récoltée est incohérente. Par chance, on se trouve dans la deuxième situation et l"un des sommets de degré impair (le sommet A) est un laboratoire alors que l"autre (le sommet H) est une zone entre les laboratoires avec une seule bouche d"aération. La souris s"y trouve donc forcément. Au 18 e siècle, le grand mathématicien Euler a résolu le problème suivant. La ville de Koenigsberg (appelée plus tard Kaliningrad) est traversée par la Praegel qui coule de part et d"autre de l"île de Kneiphof et possède sept ponts, comme le montre la figure ci- dessous. Un piéton peut-il, en se promenant, traverser une et une seule fois chaque pont ? Pour résoudre ce problème, Euler a construit un graphe G dont les sommets sont lesdifférentes régions connexes s"il n"y avait pas de pont, et où chaque arête représente une
liaison entre deux régions par un pont. Pour qu"un piéton puisse se promener en traversant chaque pont exactement une fois, il faut que G contienne un cycle eulérien, ce qui n"est pas le cas car G contient 4 sommets de degré impair. Lorsque tous les sommets d"un graphe sont de degré pair, il est assez facile de dessiner un cycle eulérien. On peut s"y prendre par exemple comme suit. Construction d"un cycle eulérien dans un graphe où tous les sommets sont de degré pair.1. Déterminer un cycle C quelconque.
2. Si C couvre toutes les arêtes du graphe alors STOP, sinon aller à 3.
3. Choisir un sommet v dans C qui est l"extrémité d"une arête hors de C.
Construire un deuxième cycle C" contenant v et tel que C et C" n"aient aucune arête en commun.4. Fusionner C et C" pour former un cycle C"". Cette fusion se fait en partant du
sommet v, en parcourant l"ensemble du cycle C puis étant revenu au sommet v en visitant l"ensemble du cycle C" pour finalement terminer en v.5. Poser C égal à C"" et retourner en 2.
Illustration
Définition
Supposons qu"une distance soit associée à chaque arête. Le problème de la détermination d"un cycle hamiltonien de distance totale minimale s"appelle le " problème du voyageur de commerce ». Le problème du voyageur de commerce est très difficile à résoudre. Il existe cependant des logiciels permettant de déterminer de telle solutions optimales tant que le nombre de sommets ne dépasse pas quelques centaines (par exemple CONCORDE qu"on peut télécharger sur le site internet http://www.tsp.gatech.edu/concorde.html). L"obtention d"une solution optimale peut prendre des heures, voire des jours.Lorsqu"on a affaire à des gros graphes ou qu"on désire obtenir des solutions très
rapidement, on utilise ce qu"on appelle des heuristiques qui fournissent des solutions de qualité raisonnable en des temps raisonnables.Heuristique du plus proche voisin
1) Choisir un sommet de départ x
2) Tant que tous les sommets ne sont pas encore visités faire l"opération suivante se rendre au sommet le plus proche pas encore visitéExemple
Cette heuristique a été comparée à ce que donne par exemple le logiciel CONCORDE.L"erreur est en moyenne d"environ 15%.
Toute heuristique, y compris celle du plus proche voisin, peut facilement être amélioréeen rajoutant à la fin une procédure de post-optimisation. Celle-ci consiste à vérifier s"il
existe une paire d"arêtes sur le cycle qui peut être remplacée par une autre paire d"arêtes
(il n"y a qu"un remplacement possible par paire d"arêtes) tout en diminuant la distance totale parcourue. Tant que de telles paires d"arêtes existent, les échanges sont effectués.Illustration
Cette procédure de post-optimisation permet de réduire considérablement l"écart à
l"optimum. Par exemple, en comparant les solutions produites par le logiciel CONCORDE avec la combinaison de l"heuristique du plus proche voisin suivie d"une post-optimisation, on a pu constater que l"erreur est en moyenne d"environ 2 à 3%.Il existe des méthodes qui permettent de réduire cet écart à quelques dixièmes de
pourcent, mais ces méthodes sont beaucoup plus complexes à mettre en place.Mais revenons maintenant aux cycles eulériens. Tel que déjà mentionné, si tous les
sommets d"un graphe G sont de degré pair alors il est facile de déterminer un cycle eulérien alors que s"il existe au moins un sommet de degré impair, le graphe ne contient aucun cycle eulérien. Dans un cycle eulérien, on impose de passer exactement une foispar chaque arête du graphe. Nous nous intéressons ici au problème consistant à
déterminer un cycle passant au moins une fois par chaque arête du graphe.Définition
Supposons qu"une distance soit associée à chaque arête d"un graphe connexe. Le" problème du postier chinois » consiste à déterminer un cycle aussi court que
possible qui passe au moins une fois par chaque arête du graphe. Contrairement au problème du voyageur de commerce, celui du postier chinois est 'facile" à résoudre. S"il n"existe aucun sommet de degré impair, on a déjà vu comment déterminer un cycle eulérien et ce cycle est nécessairement le plus court puisqu"il passe exactement une fois par chaque arête. Sinon, on peut s"y prendre comme suit. Algorithme pour déterminer une solution optimale au problème du postier chinois dans un graphe G contenant des sommets de degré impair1. Créer un graphe complet H dans lequel les sommets sont ceux de degré impair dans
G et relier toute paire de sommets dans H par une arête de coût égal à la longueur de la plus courte chaîne dans G reliant les sommets considérés.2. Déterminer un couplage de coût minimum dans H.
3. Pour chaque arête du couplage optimal déterminé en 2, rajouter la plus courte
chaîne correspondante dans G.4. Le graphe résultant a tous ses sommets de degré pair. On peut donc facilement
construire un cycle eulérien.Illustration
Dans l"exemple ci-dessus, on a supposé que toutes les distances dans G sont unitaires. Remarquons en passant que pour que le point 2 de l"algorithme ait un sens et qu"on puisse ainsi transformer tous les sommets de degré impair dans G en des sommets de degré pair, il faut qu"il y ait un nombre pair de sommets de degré impair dans G. Ceci est toujours le cas tel que démontré ci-après.Propriété
Tout graphe contient un nombre pair de sommets de degré impair.Preuve
On peut définir une partition V=IÈP de l"ensemble V des sommets d"un graphe en définissant I comme l"ensemble des sommets de degré impair et P comme l"ensemble des sommets de degré pair. On a donc Iv )v(degré Pv )v(degré Vv )v(degré Nous avons déjà montré que cette somme est paire car elle est égale au double du nombre d"arêtes dans le graphe. Comme le premier terme de la somme ci-dessus est pair (c"est une somme de nombres pairs), la deuxième somme doit aussi être paire. Pour qu"une somme de nombres impairs soit paire, il faut sommer un nombre pair de nombres et on déduit donc que l"ensemble I contient un nombre pair de sommets. 0 Un problème similaire à celui du postier chinois consiste à déterminer une tournée de coût total minimum qui passe au moins une fois par un sous-ensemble fixé d"arêtes. En pratique, le réseau d"une ville est constitué de nombreuses arêtes et le ramassage des ordures ne doit se faire que sur certaines arêtes du graphe. Le camion chargé d"effectuer le ramassage peut cependant emprunter les autres arêtes du graphe pour se rendre d"un point à un autre.Définition
Supposons qu"une distance soit associée à chaque arête d"un graphe connexe G et soit D un sous-ensemble d"arêtes à desservir dans G. Le " problème du postier rural » est de déterminer un cycle aussi court que possible dans G qui passe au moins une fois par chaque arête de D. Le problème du postier rural est très difficile à résoudre, comme celui du voyageur de commerce. En fait les problèmes réels sont bien plus complexes que ceux mentionnés ci- dessus puisqu"il faut tenir compte de nombreuses contraintes, tel que la capacité des véhicules, les pauses des chauffeurs, etc.Par exemple, lorsque la quantité totale à livrer ou à collecter auprès des clients dépasse la
capacité d"un véhicule, il faut utiliser plusieurs camions. Le problème se complique donc puisqu"en plus de déterminer la route de chaque véhicule, il faut également répartir les clients parmi les véhicules.quotesdbs_dbs13.pdfusesText_19[PDF] graphe d'ordonnancement
[PDF] sujet algorithme bts sio corrigé
[PDF] calcul matrice booléenne
[PDF] calcul matriciel bts
[PDF] prise de note rapide tableau abréviations
[PDF] sauzay programme
[PDF] programme voltaire
[PDF] un petit paragraphe sur l'environnement
[PDF] exemple de texte argumentatif sur l'environnement
[PDF] texte sur l'environnement
[PDF] texte argumentatif sur l'environnement 4am
[PDF] protection de l'environnement définition
[PDF] graphe probabiliste calculatrice
[PDF] graphe étiqueté
