{"id":309,"date":"2011-01-07T18:01:13","date_gmt":"2011-01-07T16:01:13","guid":{"rendered":"https:\/\/blogs.ua.es\/jabibics\/?p=309"},"modified":"2012-01-08T21:19:48","modified_gmt":"2012-01-08T19:19:48","slug":"capitulo-14-algoritmo-de-fleury","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/jabibics\/2011\/01\/07\/capitulo-14-algoritmo-de-fleury\/","title":{"rendered":"Cap\u00edtulo 14 \u201cAlgoritmo de Fleury\u201d"},"content":{"rendered":"

El algoritmo de fleury<\/span> encuentra un tour o camino euleriano en un grafo no dirigido, sabiendo si existen por el siguiente teorema:<\/p>\n

Teorema 1<\/h3>\n

Sea G un grafo no dirigido y conexo<\/p>\n

– G es euleriano si y s\u00f3lo si no tiene v\u00e9rtices de grado impar.
\n– G contiene un camino euleriano si y s\u00f3lo si tiene exactamente dos v\u00e9rtices de grado impar.<\/p>\n

<\/p>\n

Ejemplo<\/p><\/blockquote>\n\n\n\n\n
\"\"<\/td>\n\"\"<\/td>\n\"\"<\/td>\n<\/tr>\n
Tiene dos v\u00e9rtices de grado impar por lo tanto no<\/span> es un grafo euleriano pero si tiene un camino<\/span> euleriano:<\/p>\n

v2 e3 v4 e2 v1 e1 v3<\/p>\n<\/td>\n

Tiene dos v\u00e9rtices de grado impar por lo tanto no<\/span> es un grafo euleriano pero tiene un camino<\/span> euleriano:<\/p>\n

v2 e2 v3 e3 v4 e4 v2 e1 v1<\/p>\n<\/td>\n

Si<\/span> es un grafo euleriano<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Ahora que sabemos que el grafo tres es euleriano debemos seguir los siguientes pasos:<\/p>\n

Paso 1:<\/p>\n

– Nos creamos una cadena d\u00f3nde iremos guardando nuestro tour euleriano<\/p>\n

T = {}<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

\n

Paso 2:<\/p>\n

– Seleccionamos un v\u00e9rtice x.<\/p>\n

– Seleccionamos una arista incidente a x, que no desconecte el grafo si la quitamos.<\/p>\n

– A\u00f1adimos la arista a nuestra cadena y la quitamos del grafo<\/p>\n

– Si x no tiene m\u00e1s aristas incidentes lo quitamos.<\/p>\n

T = {e3 }<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

\n

Repetimos el paso 2<\/p>\n

T = {e3 e2}<\/p>\n

Como el v\u00e9rtice 3 se queda sin aristas lo quitamos.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Repetimos el paso 2<\/p>\n

T = {e3 e2 e1}<\/p>\n

Como el v\u00e9rtice 1\u00a0 se queda sin aristas lo quitamos.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

\n

No hay m\u00e1s aristas ya tenemos nuestro tour euleriano.<\/p>\n

NOTA: Deben aparecer todas las aristas en el tour\/camino<\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"

El algoritmo de fleury encuentra un tour o camino euleriano en un grafo no dirigido, sabiendo si existen por el siguiente teorema: Teorema 1 Sea G un grafo no dirigido y conexo – G es euleriano si y s\u00f3lo si no tiene v\u00e9rtices de grado impar. – G contiene un camino euleriano si y s\u00f3lo […]<\/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-309","post","type-post","status-publish","format-standard","hentry","category-grafos"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/309","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=309"}],"version-history":[{"count":33,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/309\/revisions"}],"predecessor-version":[{"id":461,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/309\/revisions\/461"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/media?parent=309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/categories?post=309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/tags?post=309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}