Un ciclo que pasa por todos los v\u00e9rtices son llamados ciclos Hamiltonianos. Un grafo que contiene un ciclo de Hamilton se llama grafo Hamiltoniano.<\/p>\n
Una trayectoria que pasa por todos los v\u00e9rtices se denomina trayectoria Hamiltoniana.<\/p>\n
Si el \u00faltimo enlace de un ciclo Hamiltoniano es borrado conseguiremos una trayectoria Hamiltoniana, sin embargo, un grafo no Hamiltoniano puede tener una trayectoria Hamiltoniana.<\/p>\n
Ejemplos:<\/p>\n
El n-ciclo C_n<\/span> con n v\u00e9rtices distintos es Hamiltoniano. Ahora, dado cualquier grafo Hamiltoniano G, el supergrafo G', obtenido por a\u00f1adir nuevos enlaces entre v\u00e9rtices no adyacentes tambi\u00e9n es Hamiltoniano. Por ejemplo K_n <\/span> es un supergrafo de\u00a0C_n<\/span> y por lo tanto\u00a0K_n <\/span>\u00a0 es Hamiltoniano.<\/p>\n El siguiente teorema, debido a Dirac, nos da condiciones suficientes para tener un grafo Hamiltoniano.<\/p>\n <\/p>\n Teorema. (Dirac)<\/strong> Si G es un grafo con n v\u00e9rtices, donde n\\geq 3<\/span> y d(v)\\geq n\/2 <\/span>, para cada v\u00e9rtice v <\/span> de G, entonces G es Hamiltoniano.\u00a0<\/em><\/p>\n <\/p>\n Prueba.<\/p>\n Supongamos que G no es Hamiltoniano. Entonces para alg\u00fan valor n\\geq 3<\/span> hay un grafo no Hamiltoniano H en el cual\u00a0 d(v)\\geq n\/2 <\/span> para cada v\u00e9rtice de H. Entonces en cualquier supergrafo\u00a0 K de H esa desigualdad se mantiene si K tiene el mismo conjunto de v\u00e9rtices que H, pues en ese caso a K se lo obtiene simplemente por a\u00f1adir enlaces a H. Entonces existe un grafo no Hamiltoniano maximal G con n v\u00e9rtices y que satisface la desigualdad\u00a0 d(v)\\geq n\/2 <\/span> para cada v\u00e9rtice de G.<\/p>\n <\/p>\n Obviamente G no es la gr\u00e1fica completa K_n <\/span>, pues dicha gr\u00e1fica es Hamiltoniana. Luego, hay en G v\u00e9rtices que no est\u00e1n conectados u, v. Sea G+uv un nuevo supergrafo de G. Dado que G es no Hamiltoniano maximal, entonces G+uv es Hamiltoniano, y uv pertenece al ciclo Hamiltoniano.<\/p>\n Sea C: u=v_1 v_2 v_3.. v_n=v<\/span>, ahora sea S=\\{v_i \\in C: uv_{i+1}\\in E(G)\\}<\/span> y\u00a0 T=\\{v_j \\in C: vv_{j}\\in E(G)\\}<\/span>. Observemos que v no pertenece al conjunto T ni al conjunto S.<\/p>\n Sea |S| , |T| <\/span> y\u00a0 | S \\cup T | <\/span> las cardinalidades de dichos conjuntos. Entonces |S \\cup T|<n<\/span>, y para cada enlace incidente con u, corresponde un v\u00e9rtice v_i \\in S<\/span>, as\u00ed |S|=d(u)<\/span>. Usando un argumento parecido, |T|=d(v)<\/span>.<\/p>\n La siguiente idea es interesante: Supongamos que alg\u00fan v\u00e9rtice v_k\\in S\\cap T<\/span>, entonces hay dos enlaces, uno que une a u con v_{k+1} <\/span>\u00a0 y otro que une a v con v_k <\/span>. Esto implica que el conjunto C'=v_1, v_{k+1}, v_{k+2}, .., v_n, v_k, v_{k-1}, .., v_1 <\/span> es un ciclo Hamiltoniano en G, lo que contradice que G sea no Hamiltoniano. As\u00ed S\\cap T <\/span> es vac\u00edo.<\/p>\n <\/p>\n Finalmente |S\\cup T|=|S|+|T|-|S\\cap T| <\/span> nos da que |S|+|T|=|S \\cup T|<\/span>, tal que d(u)+d(v)<n <\/span>. Esto es una contradicci\u00f3n porque d(u)\\geq n\/2 <\/span> para todo v\u00e9rtice en G. Y la prueba est\u00e1 terminada.<\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Un ciclo que pasa por todos los v\u00e9rtices son llamados ciclos Hamiltonianos. Un grafo que contiene un ciclo de Hamilton se llama grafo Hamiltoniano. Una trayectoria que pasa por todos los v\u00e9rtices se denomina trayectoria Hamiltoniana. Si el \u00faltimo enlace de un ciclo Hamiltoniano es borrado conseguiremos una trayectoria Hamiltoniana, sin embargo, un grafo no … Sigue leyendo Grafos hamiltonianos y un teorema de Dirac<\/span><\/a><\/p>\n","protected":false},"author":5810,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1419472],"tags":[],"class_list":["post-305","post","type-post","status-publish","format-standard","hentry","category-teoria-de-grafos"],"_links":{"self":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/305","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/users\/5810"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/comments?post=305"}],"version-history":[{"count":11,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/305\/revisions"}],"predecessor-version":[{"id":316,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/305\/revisions\/316"}],"wp:attachment":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/media?parent=305"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/categories?post=305"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/tags?post=305"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}