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 .
Le problème du voyageur de commerce
Sujet proposé par David Monniaux et Bruno Salvy (corrigé) On appelleproblème du voyageur de commercele problème informel suivant : étant donnéune carte avec des villes, des chemins et des distances (ou temps de trajet) entre ces villes, fournir
un itinéraire qui passe par toutes les villes, revient à la ville de départ, ne visite chaque ville
qu"une fois, et qui réalise la distance (ou le temps) minimal. On explique ainsi le nom donnéà ce problème : auxixesiècle, les guides à l"usage des voyageurs de commerce proposaient des
itinéraires, sinon minimaux, du moins optimisés. Plus proche de nous, étant donné un ensemble de
positions de trous ou de soudures à réaliser, ainsi que les temps de déplacement de la machine-outil
d"un emplacement à l"autre, donner l"ordre de réalisation optimal est un problème de voyageur
de commerce. Nous nous intéresserons ici au problème formel suivant : on fixe un nombrende sommets d"un graphe orienté, et on se donne une matricennqui à chaque couple(i;j)de sommets associe soit+1, soit un entier naturel, mesurant le coût pour passer sur l"arête(i;j); on sedonne également une borneb, le problème est de décider s"il existe un circuit (un chemin qui
revient à son point de départ) passant exactement une fois par chacun des sommets et dont lasomme des coûts est inférieure ou égale àb. Nous allons montrer que ce problème, noté TSP
(traveling salesman problem), est NP-complet.1 Mise en jambes
Question 1.1.Montrez que TSP est dans NP.
Solution :La donnée des sommetss1;:::;snsuccessifs dans le circuits1!:::sn!s1est un certificat : clairement, on peut vérifier en temps polynomial qu"il ne passe pas deux fois par lemême sommet et qu"il est bien de coût total inférieur àb.Un problème lié au TSP est le problème duchemin hamiltonien: étant donné un graphe
(donné par matrice ou listes d"adjacence), et deux sommetsAetBdistincts dans ce graphe, dire s"il existe un chemin deAàBqui passe par tous les sommets du graphe, et ne visite chacun qu"une fois. Question 1.2.Montrez que le problème du chemin hamiltonien est dans NP.Solution :De même qu"à la question précédente, le chemin est un certificat.Le problème ducircuit hamiltonienest voisin : étant donné un graphe (donné par matrice
ou listes d"adjacence), dire s"il existe un circuit qui passe par tous les sommets du graphe, et ne visite chacun qu"une fois. Question 1.3.Montrez que le problème du circuit hamiltonien est dans NP.Solution :De même qu"à la question précédente, le circuit est un certificat.Question 1.4.Montrez que le problème du circuit hamiltonien est un cas particulier du problème
du voyageur de commerce. 1 Solution :C"est le problème du voyageur de commerce avec un coût de un pour les arêtesprésentes dans le graphe, et+1pour celles qui n"y sont pas.Question 1.5.Montrez que le problème du circuit hamiltonien se réduit au problème du chemin
hamiltonien.Solution :Soits1un sommet arbitraire du graphe. On le dédouble en deux sommetss01ets001(s01ets001remplacents1et sont connectés aux mêmes noeuds ques1) et on recherche un chemin
hamiltonien entres01ets001: tout cycle hamiltoniens1!s2!sn!s1du graphe d"origine donneun chemin hamiltoniens01!:::s2!sn!s001, et réciproquement.Question 1.6.Montrez que le problème du chemin hamiltonien se réduit au problème du circuit
hamiltonien. Solution :SoitGun graphe dans lequel on cherche s"il y a un chemin hamiltonien entre les noeudsaetb. On rajoute un noeudcet deux arêtesb!c!apour obtenir le grapheG0, dans lequel on cherche un circuit hamiltonien. Si l"on trouve un tel circuit, on peut le mettre sous la formec!a!v1! !vn!b!cet alorsa!v1! !vn!best un chemin hamiltonien dansG. Réciproquement, tout chemin hamiltoniena!v1! !vn!bdansGdonne un circuit hamiltonienc!a!v1! !vn!b!cdansG0.En utilisant le fait que 3SAT (dit aussi 3CNFSAT) est NP-complet, on a donc les réductions
suivantes :voyageur de commercecircuit hamiltonienchemin hamiltonien3SAT q1.4q1.5 q1.6q1.1q1.3 q1.2Il reste donc à prouver que l"on peut réduire 3SAT vers le problème du chemin hamiltonien (la
flèche en pointillés).2 Réduction 3SAT vers le problème du chemin hamiltonien
Il s"agit, à partir d"un problème 3SAT, de construire un graphe de taille polynomiale en celle du problème, qui aura un chemin hamiltonien entre deux points distingués si et seulement si ce problème 3SAT a une solution, ce chemin permettant de construire une solution du problème3SAT, et réciproquement une solution du problème 3SAT permettant de construire un chemin
hamiltonien. . On va supposer que l"on dispose d"un graphe TRIPLETTE ayant les propriétés suivantes : 1. TRIPLETTE p ossède,en treautres noeuds, trois noeuds d"en tréee1,e2ete3, et trois noeudss1,s2ets3, tous distincts. On dit que chaque noeudsicorrespond au noeudei. 2. P ourtout ensem bled"un (resp ectivementdeux, trois) noeuds d"en trée,il ex isteun (resp ec- tivement deux, trois) chemins commençant sur ces noeuds, finissant sur les noeuds de sortie correspondant respectifs, et tels qu"à eux tous, ces chemins passent par chaque noeud une et une seule fois. 23.P ourtout ensem bled" un(resp ectivementdeux, trois) noeuds d"en trée,il n"existe qu"un
(respectivement deux, trois) chemins commençant sur ces noeuds, finissant sur des noeuds de sortie, et, dans leur ensemble, passant par chaque noeud une et une seule fois. SoitC1^ ^Cmle problème 3SAT, chaqueCiétant une clause formée sur les variables propositionnellesy1;:::;yn. On construit le graphe formé : Des noeuds v1;:::;vn+1. Les noeudsv1;:::;vnsont respectivement associés aux variables y1;:::;yn.
De mcopies de TRIPLETTE, chacune correspondant à une clauseCi, avec les 3 entrées et sorties respectives étiquetées par les variables de la clause. P ourc haquev ariableyi, on répertorie les clausesCi1;:::;Cipdans laquelle elle intervient positivement, aveci1<< ip; on connectevià l"entrée correspondante àyidansCi1, la sortie correspondante deCi1à l"entrée correspondante deCi2, etc., et la sortie deCipest connectée àvi+1. On appelle ces branchements le "sous-graphe positif associé àyi».
On op èreexactemen tde la même manière p ourles clauses où elle in tervientnégativ ement.
On appelle ces branchements le "sous-graphe négatif associé àyi». Question 2.1.Montrez qu"à tout chemin hamiltonien dev1àvn+1on peut associer une valuation dey1;:::;ynsatisfaisantC1^ ^Cm. Solution :Soit un tel chemin. Pour toute variable propositionnelleyi, le chemin hamiltonienpart devisoit vers le sous-graphe positif associé àyi, auquel cas on associera la valeur "vrai»
àyi, soit vers le sous-graphe négatif associé àyi, auquel cas on associera la valeur "faux» àyi.
Cette valuation est bien définie : on ne peut associer deux valeurs de vérité différentes à une
même variableyi. En effet, le chemin ne peut passer deux fois par un noeudvi. Le chemin doit, par définition d"un chemin hamiltonien, passer dans chaque TRIPLETTEdonc notamment par un noeud d"entrée. Par définition du graphe, cela veut dire que le littéral
associé à la variable qui étiquette le noeud d"entrée est vrai, donc que la clause associée à la
TRIPLETTE est vrai.Question 2.2.Montrez qu"à toute valuation dey1;:::;ynsatisfaisantC1^ ^Cmon peut
associer un chemin hamiltonien. Solution :Pour tout1jn, on choisit comme arête sortante devjcelle vers le sous-graphepositif associé àyjsiyjest vraie, celle vers le sous-graphe négatif associé àyjsiyjest fausse;
on choisit comme arête entrante devj+1celle depuis le sous-graphe positif associé àyjsiyjest
vraie, celle depuis le sous-graphe négatif associé àyjsiyjest fausse. Soit1im, considérons la TRIPLETTE correspondant àCi. La valuation satisfait la clauseCi; elle rend donc vrais un, deux ou trois littéraux dansCi. Ceci correspond à une, deuxou trois arêtes arrivant sur les noeuds d"entrée, et une, deux ou trois arêtes partant des noeuds de
sortie. D"après la 2 epropriété de la TRIPLETTE, on peut trouver trois chemins partant de ces noeuds d"entrée et arrivant aux noeuds de sortie correspondants, qui, pris tous ensemble, passent une fois exactement par chaque noeud de la triplette. D"après la 3 epropriété, cette construction est unique. Comme la TRIPLETTE est un graphe fini, on peut énumérer toutes les configurations de chemin dedans jusqu"à trouver l"unique configuration qui vérifie ces conditions.Le chemin ainsi construit est un chemin hamiltonien dev1àvn+1.Question 2.3.Donnez un graphe TRIPLETTE vérifiant les 3 conditions.
3Solution :Ceci achève la preuve que le problème du chemin hamiltonien, et donc ceux du circuit hamil-
tonien et du voyageur de commerce, sont NP-complets. Le problème du voyageur de commercereste NP-complet si les distances indiquées respectent l"inégalité triangulaire, et le reste encore
si elles sont des distances euclidiennes dans le plan.3 Solutions approchées
Dans le cours, un algorithme en temps polynomial a été présenté pour trouver un cheminpresque optimal (à un facteur 2 de l"optimal) lorsque la matrice des coûts est symétrique et
vérifie l"inégalité triangulaire : siAest la matrice,Aij+AjkAikpour tout(i;j;k). Toujoursavec cette hypothèse d"inégalité triangulaire, mais maintenant sans la symétrie de la matrice,
les meilleurs algorithmes connus s"approchent de l"optimum à un facteurlogn. L"idée du plusclassique d"entre eux remonte à 1982 et mène à un facteurlog2nde l"optimum. Ce résultat n"a
été amélioré que très récemment, en 2008, où une solution à un facteur0;999log2nde l"optimum
a été élaborée. Cette section repose sur le résultat plus simple de 1982.Question 3.1.Montrer que sans l"hypothèse d"inégalité triangulaire, il n"existe pas d"algorithme
pour trouver une solution approchée à un facteur constant en complexité polynomiale sauf si P=NP. [Indication : prendre un problème de circuit Hamiltonien et rendre le graphe complet en y rajoutant toutes les arêtes manquantes avec un coûtc >1.] Solution :Si le graphe possède un circuit hamiltonien, alors un circuit de voyageur de commerceoptimal sur le graphe modifié a un coûtn, alors qu"un circuit qui n"est pas optimal possède au
moins une arête de coûtcet donc un coût total d"au moinsn+(c1). Si on choisitc >(1)n+1alors une solution approchée à un facteurde l"optimum est le circuit hamiltonien s"il en existe 1
et a un coût supérieur ànsinon.À partir de maintenant, nous considérons que la matrice de coût vérifie l"inégalité triangulaire.
Question 3.2.Montrer que tout circuit est au plus à un facteurnde l"optimal.Solution :Toute arête joint deux sommets qui appartiennent au circuit optimal. Par l"inégalité
triangulaire, son coût est donc borné par celui du chemin optimal. Comme il y anarêtes dansun circuit, le coût total est donc à un facteurnde l"optimal.On admettra qu"il est possible de trouver en complexité polynomiale un recouvrement de
tous les sommets du graphe par une union de circuits (chaque sommet du graphe appartient àun et un seul de ces circuits), la somme des coûts de cette union étant optimale. (L"algorithme
correspondant s"appelle "la méthode hongroise"). Question 3.3.Montrer que la somme de ces coûts est au plus celle du circuit optimal, et que le nombre de circuits est au plusn=2. 4 Solution :Puisque la somme des coûts est optimale, et que le circuit optimal est une telle unionde circuits réduite à un seul circuit, le circuit optimal est plus coûteux que la couverture optimale
par des circuits. Chaque circuit a longueur au moins 2, ce qui permet de borner leur nombre.Question 3.4.En choisissant un sommet dans chacun de ces circuits et en considérant récur-
sivement le sous-graphe induit par ces sommets, montrer que l"on aboutit à une solution à un facteurlog2nde l"optimal en complexité polynomiale. Solution :Le sous-grapheG0induit par ces sommets peut à nouveau être couvert de manière optimale par des circuits. Le coût de cette couverture est encore majoré par celui du circuit optimal : du circuit optimal sur le graphe entier on déduit une couverture des sommets deG0par un circuit en remplaçant les suites d"arêtes qui sortent deG0par une seule arête de coût
moindre (par inégalité triangulaire). On obtient alors un nombre de circuits borné parjG0j=2. La
procédure se répète au pluslog2nétapes, et à chaque fois la couverture par des circuits a coût
borné par celui du circuit du voyageur de commerce optimal. À l"inverse, on peut recoller un circuit qui passe par les sommets deG0et les circuits cou- vrantG: il suffit de parcourir chaque circuit couvrantGen partant de l"arête provenant deG0et remplaçant l"arête qui termine le circuit par une arête reliant ce sommet au suivant dans le
cycle couvrantG0. Le coût total est alors borné par la somme des coûts des circuits couvrantG
et du circuit deG0. Procédant ainsi dans la remontée de la récursion, on obtient un coût total
borné parlog2nfois l"optimum.Références [1] Da vidL. Applegate, Rob ertE. Bixb y,V asekCh vátal,and Will iamJ. Co ok.The trave- ling salesman problem : a computational study. Princeton university press, 2007. ISBN9780691129938.
[2] inequality.ACM Trans. Algorithms, 4(4) :Art. 47, 15, 2008. ISSN 1549-6325. doi:10.1145/1383369.1383378. URLhttp://dx.doi.org/10.1145/1383369.1383378.
[3] A. M. F rieze,G. Galbiati, and F. Maffioli. On the w orst-casep erformanceof some algorithms for the asymmetric traveling salesman problem.Networks, 12(1) :23-39, 1982. ISSN 0028-3045. doi: 10.1002/net.3230120103. URLhttp://dx.doi.org/10.1002/net.3230120103.
[4] Mic haelMa chteya ndP aulY oung.An introduction to the general theory of algorithms. Computer science library, Theory of computation series. North-Holland, New York, 1978.ISBN 044400226X.
[5] Sarta jSahni and T eofiloGonzale z.P-complete approximation problems.J. Assoc. Comput.Mach., 23(3) :555-565, 1976. ISSN 0004-5411.
5quotesdbs_dbs44.pdfusesText_44[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é