{"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\/es\/teoria-de-grafos\/hamiltoniano-y-euleriano\/","title":{"rendered":"Hamiltoniano y euleriano"},"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\/es\/teoria-de-grafos\/\">\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\">Teor\u00eda de grafos<\/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\/es\/\">\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\">Pagina de inicio<\/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_83 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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/es\/teoria-de-grafos\/hamiltoniano-y-euleriano\/#Probleme-graphe-eulerien\" >Problema: grafo euleriano<\/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\/es\/teoria-de-grafos\/hamiltoniano-y-euleriano\/#Probleme-graphe-hamiltonien\" >Problema: gr\u00e1fico hamiltoniano<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-graphe-eulerien\"><\/span>Problema: grafo euleriano<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=\"Gr\u00e1fico euleriano hamiltoniano\" 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;\">Por un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a> orientado, un camino (o circuito) euleriano pasa una y s\u00f3lo una vez por todos los arcos. An\u00e1logamente, en el caso no dirigido, una cadena o ciclo euleriano pasa una y s\u00f3lo una vez por todas las aristas.<\/div>\n\n<p>El gr\u00e1fico debe estar fuertemente conectado (o conectado). De hecho, si el gr\u00e1fico no lo es, no se puede acceder a uno o m\u00e1s subgrafos que contienen enlaces. Vemos que un ciclo o circuito euleriano contiene tantos enlaces que llegan a un v\u00e9rtice como sale (llegamos a un v\u00e9rtice para salir)<\/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;\">Condiciones necesarias y suficientes del circuito \/ ciclo euleriano. El gr\u00e1fico est\u00e1 conectado (o fuertemente conectado). Cualquiera que sea el v\u00e9rtice del gr\u00e1fico, su grado es par (su grado de salida es igual a su grado de entrada).<\/div>\n\n<p>Dado que todos los v\u00e9rtices tienen un grado par, sabemos que hay un circuito. Un camino es una uni\u00f3n de circuitos disjuntos en los bordes. Si eliminamos los bordes de un camino, los grados siempre son pares. Supongamos que no hay un camino que d\u00e9 un ciclo euleriano. Si eliminamos una ruta con un m\u00e1ximo de bordes en el gr\u00e1fico, los grados permanecen uniformes. Pero en este caso, hay un circuito desarticulado de nuestra ruta m\u00e1xima. Siendo el recorrido una uni\u00f3n de circuitos disjuntos, se concluye que el recorrido inicial no era m\u00e1ximo. De esto se deduce que la ruta m\u00e1xima contiene todos los bordes del gr\u00e1fico. La prueba es id\u00e9ntica para el caso orientado.<\/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;\">Sea una gr\u00e1fica que admita una cadena euleriana. Agregar un borde entre el inicio y el final de la cadena nos dar\u00e1 un ciclo euleriano. Asimismo, si eliminamos cualquier borde de un ciclo euleriano, tendremos una cadena euleriana.<\/div>\n\n<p>Con esta transformaci\u00f3n, deducimos las condiciones necesarias y suficientes para que un gr\u00e1fico tenga una cadena (o trayectoria) euleriana.<\/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;\">Condiciones necesarias y suficientes de la cadena \/ camino euleriano. El gr\u00e1fico est\u00e1 conectado (o fuertemente conectado). Para todos los v\u00e9rtices del gr\u00e1fico, excepto posiblemente dos, su grado es par (su grado de salida es igual a su grado de entrada + o - 1 para posiblemente dos v\u00e9rtices.<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-graphe-hamiltonien\"><\/span>Problema: gr\u00e1fico hamiltoniano<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;\">En un gr\u00e1fico dirigido, un circuito o un camino hamiltoniano es un circuito o camino que pasa una vez y solo una vez por todos los v\u00e9rtices. Lo mismo ocurre con el caso no orientado.<\/div>\n\n<p>Hasta la fecha, no existen condiciones necesarias y suficientes, sino solo condiciones suficientes relativas a los grados de los v\u00e9rtices.<\/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> Un gr\u00e1fico simple con <strong>no<\/strong> v\u00e9rtices (n&gt; 2) cada v\u00e9rtice de los cuales tiene un grado al menos igual an \/ 2 es hamiltoniano.<\/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>Mineral de 1960.<\/strong>\u00a0Un gr\u00e1fico simple con\u00a0<span class=\"mwe-math-element\"><span class=\"mwe-math-mathml-inline mwe-math-mathml-a11y\">no<\/span><\/span>\u00a0v\u00e9rtices<span class=\"mwe-math-element\"><span class=\"mwe-math-mathml-inline mwe-math-mathml-a11y\">n&gt; 2)<\/span><\/span>\u00a0tal que la suma de los grados de cualquier par de v\u00e9rtices no adyacentes sea al menos\u00a0<span class=\"mwe-math-element\"><span class=\"mwe-math-mathml-inline mwe-math-mathml-a11y\">no<\/span><\/span>\u00a0es hamiltoniano.<\/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> Un gr\u00e1fico simple con <strong>no<\/strong> v\u00e9rtices (n&gt; 2) tales que para todos <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> es inferior a <strong>k<\/strong>. El n\u00famero de v\u00e9rtices de grado menor o igual que (n-1) \/ 2 es menor o igual que (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>P\u00e1gina de inicio de Wiki de teor\u00eda de grafos Problema: gr\u00e1fico euleriano Para un gr\u00e1fico dirigido, un camino (o circuito) euleriano pasa una y solo una vez... <\/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\/es\/wp-json\/wp\/v2\/pages\/8590","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=8590"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/8590\/revisions"}],"predecessor-version":[{"id":18367,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/8590\/revisions\/18367"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=8590"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}