{"id":8590,"date":"2020-08-26T13:01:30","date_gmt":"2020-08-26T12:01:30","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=8590"},"modified":"2022-12-03T22:58:50","modified_gmt":"2022-12-03T21:58:50","slug":"hamiltonien-et-eulerien","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/hamiltonian-and-eulerian\/","title":{"rendered":"Hamiltonian and Eulerian"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"8590\" class=\"elementor elementor-8590\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-deb1199 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"deb1199\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-3592cd4\" data-id=\"3592cd4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cab5c54 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"cab5c54\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Graph theory<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-f38f645\" data-id=\"f38f645\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-06e2384 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"06e2384\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-0549563\" data-id=\"0549563\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-847d1ac elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"847d1ac\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Graphe_hamiltonien\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-657e3325 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"657e3325\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3f640d66\" data-id=\"3f640d66\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-24ec756e elementor-widget elementor-widget-text-editor\" data-id=\"24ec756e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/hamiltonian-and-eulerian\/#Probleme-graphe-eulerien\" >Problem: Eulerian graph<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/hamiltonian-and-eulerian\/#Probleme-graphe-hamiltonien\" >Problem: Hamiltonian graph<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-graphe-eulerien\"><\/span>Problem: Eulerian graph<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"Hamiltonian Eulerian graph\" width=\"97\" height=\"97\" title=\"\"><\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">For a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> oriented, an Eulerian path (or circuit) passes once and only once through all the arcs. Similarly in the undirected case, a chain or Eulerian cycle passes once and only once through all the edges.<\/div>\n\n<p class=\"wp-block-paragraph\">The graph must be strongly connected (or connected). Indeed, if the graph is not, one or more subgraphs containing links cannot be reached. We see that a cycle or Eulerian circuit contains as many links arriving at a vertex as it leaves (we arrive at a vertex to leave)<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Necessary and sufficient conditions of the Eulerian circuit \/ cycle. The graph is connected (or strongly connected). Whatever a vertex of the graph, its degree is even (its outgoing degree is equal to its entering degree).<\/div>\n\n<p class=\"wp-block-paragraph\">Since all vertices have an even degree, we know that there is a circuit. A path is a union of disjoint circuits at the edges. If we remove the edges of a path then the degrees are always even. Suppose there is no path giving an Eulerian cycle. If we remove a path with a maximum of edges on the graph then the degrees remain even. But in this case, there is a circuit disjointed from our maximum route. The route being a union of disjoint circuits, we conclude that the initial route was not maximum. Deduces from this that the maximum path contains all the edges of the graph. The proof is identical for the oriented case.<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Let be a graph admitting an Eulerian chain. Adding an edge between the start and the end of the chain will give us an Eulerian cycle. Likewise, if we remove any edge from an Eulerian cycle, we will have an Eulerian chain.<\/div>\n\n<p class=\"wp-block-paragraph\">With this transformation, we deduce the necessary and sufficient conditions for a graph to have an Eulerian chain (or path).<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Necessary and sufficient conditions of the Eulerian chain \/ path. The graph is connected (or strongly connected). For all vertices of the graph, except possibly two, its degree is even (its outgoing degree is equal to its incoming degree + or - 1 for possibly two vertices.<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-graphe-hamiltonien\"><\/span>Problem: Hamiltonian graph<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">In a directed graph, a circuit or a Hamiltonian path is a circuit or path passing once and only once through all the vertices. Likewise for the non-oriented case.<\/div>\n\n<p class=\"wp-block-paragraph\">To date, there are no necessary and sufficient conditions but only sufficient conditions relating to the degrees of the vertices.<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\"><strong>Dirac 1952.<\/strong> A simple graph with <strong>not<\/strong> vertices (n&gt; 2) each vertex of which has a degree at least equal to n \/ 2 is Hamiltonian.<\/div>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\"><strong>Ore 1960.<\/strong>\u00a0A simple graph with\u00a0<span class=\"mwe-math-element\"><span class=\"mwe-math-mathml-inline mwe-math-mathml-a11y\">not<\/span><\/span>\u00a0vertices (<span class=\"mwe-math-element\"><span class=\"mwe-math-mathml-inline mwe-math-mathml-a11y\">n&gt; 2)<\/span><\/span>\u00a0such that the sum of the degrees of any pair of nonadjacent vertices is at least\u00a0<span class=\"mwe-math-element\"><span class=\"mwe-math-mathml-inline mwe-math-mathml-a11y\">not<\/span><\/span>\u00a0is Hamiltonian.<\/div>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\"><strong>Posa 1962.<\/strong> A simple graph with <strong>not<\/strong> vertices (n&gt; 2) such that for all <strong>k<\/strong>, 0 &lt;k&lt;(n-1)\/2 le nombre de sommets de degr\u00e9 inf\u00e9rieur ou \u00e9gal \u00e0 <strong>k<\/strong> is inferior to <strong>k<\/strong>. The number of vertices of degree less than or equal to (n-1) \/ 2 is less than or equal to (n-1) \/ 2.<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Graph theory Wiki homepage Problem: Eulerian graph For a directed graph, an Eulerian path (or circuit) passes once and only once\u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8590","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/8590","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=8590"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/8590\/revisions"}],"predecessor-version":[{"id":18367,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/8590\/revisions\/18367"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=8590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}