{"id":345,"date":"2011-01-07T19:19:21","date_gmt":"2011-01-07T17:19:21","guid":{"rendered":"https:\/\/blogs.ua.es\/jabibics\/?p=345"},"modified":"2012-01-08T21:19:18","modified_gmt":"2012-01-08T19:19:18","slug":"capitulo-15-william-hamilton","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/jabibics\/2011\/01\/07\/capitulo-15-william-hamilton\/","title":{"rendered":"Cap\u00edtulo 15 \u201cWilliam Hamilton\u201d"},"content":{"rendered":"<p>Un <span style=\"text-decoration: underline\">camino Hamiltoniano<\/span> en un grafo G es un camino que atraviesa cada v\u00e9rtice del grafo exactamente una vez.<\/p>\n<p>Un <span style=\"text-decoration: underline\">ciclo Hamiltoniano<\/span> en un grafo G es un ciclo que atraviesa cada v\u00e9rtice del grafo exactamente una vez.<\/p>\n<p>Un <span style=\"text-decoration: underline\">grafo Hamiltoniano<\/span> es aquiel grafo G que contiene un ciclo Hamiltoniano.<br \/>\n<!--more--><\/p>\n<h3 style=\"text-align: center\"><strong>REGLAS PARA CONSTRUIR<\/strong><\/h3>\n<h3 style=\"text-align: center\"><strong>CAMINOS Y CICLOS HAMILTONIANOS<\/strong><\/h3>\n<p><span style=\"text-decoration: underline\">Regla 1<\/span>. Si G no es conexo, no posee ciclos Hamiltonianos<\/p>\n<p><span style=\"text-decoration: underline\">Regla 2<\/span>. Si G es un grafo con n v\u00e9rtices<\/p>\n<p style=\"padding-left: 30px\">&#8211; Un camino debe tener n-1 aristas<br \/>\n&#8211; Un ciclo debe tener n aristas<\/p>\n<p><span style=\"text-decoration: underline\">Regla 3<\/span>. Si v es un v\u00e9rtice del grafo, entonces un camino Hamiltoniano debe tener al menos una arista incidente con v como mucho dos.<\/p>\n<p><span style=\"text-decoration: underline\">Regla 4<\/span>. Si G es Hamiltoniano, entoncees dG(v) \u2265 2.<\/p>\n<p><span style=\"text-decoration: underline\">Regla 5<\/span>. Si v tiene grado 2, las dos aristas incidentes a v aparecer\u00e1n en culquier ciclo Hamiltoniano.<\/p>\n<p><span style=\"text-decoration: underline\">Regla 6<\/span>. Si v tiene grado &gt; 2 cuando se intenta construir un ciclo Hamiltoniano, una vez que pase por v, las aristas no utilizadas incidentes, no se tienen en cuenta.<\/p>\n<p><span style=\"text-decoration: underline\">Regla 7<\/span>. Al construir un ciclo o camino hamiltoniano para G no se puede obtener un subgrafo sin que contenga todos los v\u00e9rtices.<\/p>\n<h3 style=\"text-align: center\"><strong>TEOREMA<\/strong>S<\/h3>\n<p>Sea G un grafo bipartido con partici\u00f3n {X,Y}.<\/p>\n<p style=\"padding-left: 30px\"><span style=\"text-decoration: underline\">Teorema 1<\/span>. Si G tiene un ciclo Hamiltoniano, entonces card(X) = card(Y).<\/p>\n<p style=\"padding-left: 30px\"><span style=\"text-decoration: underline\">Teorena 2<\/span>. Si G tiene un camino Hamiltoniano entonces card(X) y card(Y) difieren a lo sumo en 1.<\/p>\n<p style=\"padding-left: 30px\"><span style=\"text-decoration: underline\">Teorena de Dirac<\/span>. Todo grafo simple con n v\u00e9rtices, n \u2265 3, en el que todo v\u00e9rtice tiene grado por lo menos n\/2, tiene un ciclo Hamiltoniano.<\/p>\n<p style=\"padding-left: 30px\"><span style=\"text-decoration: underline\">Colorario<\/span>. Si G es un grafo completo simple con n v\u00e9rtices, n \u2265 3, entonces G tiene un ciclo Hamiltoniano.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un camino Hamiltoniano en un grafo G es un camino que atraviesa cada v\u00e9rtice del grafo exactamente una vez. Un ciclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada v\u00e9rtice del grafo exactamente una vez. Un grafo Hamiltoniano es aquiel grafo G que contiene un ciclo Hamiltoniano.<\/p>\n","protected":false},"author":1760,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10961],"tags":[],"class_list":["post-345","post","type-post","status-publish","format-standard","hentry","category-grafos"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/345","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/users\/1760"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/comments?post=345"}],"version-history":[{"count":14,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/345\/revisions"}],"predecessor-version":[{"id":460,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/345\/revisions\/460"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/media?parent=345"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/categories?post=345"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/tags?post=345"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}