#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \use_default_options true \begin_modules algorithm2e \end_modules \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style french \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Section Caminos más cortos \end_layout \begin_layout Standard Dada una red \begin_inset Formula $(V,E,\ell)$ \end_inset y un camino \begin_inset Formula $P:=v_{0}e_{1}v_{1}\cdots e_{k}v_{k}$ \end_inset en \begin_inset Formula $(V,E)$ \end_inset , llamamos \series bold longitud \series default de \begin_inset Formula $P$ \end_inset a \begin_inset Formula \[ \ell(P):=\sum_{i=1}^{k}\ell(e_{i}). \] \end_inset El problema del \series bold camino más corto \series default entre dos vértices \begin_inset Formula $u,v\in V$ \end_inset es el de minimizar \begin_inset Formula $\ell(P)$ \end_inset siendo \begin_inset Formula $P$ \end_inset un camino que une \begin_inset Formula $u$ \end_inset con \begin_inset Formula $v$ \end_inset . \end_layout \begin_layout Standard Si \begin_inset Formula $v_{0}v_{1}\cdots v_{k}$ \end_inset es el camino más corto de \begin_inset Formula $v_{0}$ \end_inset a \begin_inset Formula $v_{k}$ \end_inset , \begin_inset Formula $v_{i}v_{i+1}\cdots v_{j}$ \end_inset es el camino más corto de \begin_inset Formula $v_{i}$ \end_inset a \begin_inset Formula $v_{j}$ \end_inset para \begin_inset Formula $0\leq iD_{ik}+D_{kj}$}{ \end_layout \begin_layout Plain Layout $D_{ij} \backslash gets D_{ik}+D_{kj}$ \backslash ; \end_layout \begin_layout Plain Layout $P_{ij} \backslash gets P_{kj}$ \backslash ; \end_layout \begin_layout Plain Layout } \end_layout \begin_layout Plain Layout } \end_layout \begin_layout Plain Layout } \end_layout \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "alg:dantzig" \end_inset Algoritmo de Dantzig. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Section Tours eulerianos \end_layout \begin_layout Standard Dado un grafo \begin_inset Formula $G=(V,E)$ \end_inset , un \series bold tour \series default o \series bold recorrido euleriano \series default es un paseo cerrado que atraviesa cada eje del grafo exactamente una vez. Un grafo es \series bold euleriano \series default si admite un recorrido euleriano. Como \series bold teorema \series default , un grafo conexo es euleriano si y solo si todos los vértices tiene orden par, en cuyo caso se puede obtener un tour euleriano con el \series bold algoritmo de Hierholzer \series default (algoritmo \begin_inset CommandInset ref LatexCommand ref reference "alg:hierholzer" plural "false" caps "false" noprefix "false" \end_inset ). \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\implies]$ \end_inset \end_layout \end_inset Sean \begin_inset Formula $T$ \end_inset un tour euleriano, \begin_inset Formula $v\in V$ \end_inset y \begin_inset Formula $e_{1},\dots,e_{k}$ \end_inset los ejes adyacentes a \begin_inset Formula $v$ \end_inset , cada eje está en \begin_inset Formula $T$ \end_inset exactamente una vez y puede ser entrante (el siguiente nodo es \begin_inset Formula $v$ \end_inset ) o saliente (lo es el anterior), pero a todo eje entrante le sigue uno saliente y a todo saliente le precede uno entrante (podemos suponer que \begin_inset Formula $T$ \end_inset no empieza por \begin_inset Formula $v$ \end_inset ), luego el número de entrantes y salientes es el mismo y \begin_inset Formula $k$ \end_inset es par. \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\impliedby]$ \end_inset \end_layout \end_inset Claramente el algoritmo de Hierholzer toma cada eje exactamente una vez, crea un paseo cerrado y termina, y queda ver que no da errores. Si queda algún eje por tomar, alguno debe ser adyacente a un nodo en \begin_inset Formula $P$ \end_inset , pues de lo contrario los nodos y ejes de \begin_inset Formula $P$ \end_inset formarían una componente conexa y, al haber más ejes, \begin_inset Formula $G$ \end_inset sería disconexo. \begin_inset Formula $\#$ \end_inset Respecto al paso de tomar un eje, en la primera iteración hemos tomado un nodo de forma que se pueda, y en el resto hemos tomado un número par de ejes adyacentes a \begin_inset Formula $i$ \end_inset como ejes entrantes y salientes más el nodo usado para entrar, y como el orden es par, debe quedar otro eje sin añadir a \begin_inset Formula $P$ \end_inset . \end_layout \begin_layout Standard \begin_inset Float algorithm wide false sideways false status open \begin_layout Plain Layout \begin_inset ERT status open \begin_layout Plain Layout \backslash Entrada{Grafo $G=(V,E)$ conexo en el que todos los vértices tienen orden par.} \end_layout \begin_layout Plain Layout \backslash Salida{Tour euleriano $P$ de $G$.} \end_layout \begin_layout Plain Layout Elegir $s \backslash in V$ \backslash ; \end_layout \begin_layout Plain Layout $P \backslash gets(s)$ \backslash ; \end_layout \begin_layout Plain Layout \backslash Mientras{$E \backslash neq \backslash emptyset$}{ \end_layout \begin_layout Plain Layout Tomar un nodo $i$ en $P$ adyacente a algún eje \backslash ; \end_layout \begin_layout Plain Layout $k \backslash gets i$ \backslash ; \end_layout \begin_layout Plain Layout $P_0 \backslash gets(i)$ \backslash ; \end_layout \begin_layout Plain Layout \backslash Repetir{$i=k$}{ \end_layout \begin_layout Plain Layout Sacar un $(i,j)$ de $E$ \backslash ; \end_layout \begin_layout Plain Layout $P_0 \backslash gets P_0j$ \backslash ; \end_layout \begin_layout Plain Layout $i \backslash gets j$ \backslash ; \end_layout \begin_layout Plain Layout } \end_layout \begin_layout Plain Layout Con $P=:P_1kP_2$, hacer $P \backslash gets P_1P_0P_2$ \backslash ; \end_layout \begin_layout Plain Layout } \end_layout \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "alg:hierholzer" \end_inset Algoritmo de Hierholzer. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Standard También se puede obtener un tour euleriano con el \series bold algoritmo de Fleury \series default (algoritmo \begin_inset CommandInset ref LatexCommand ref reference "alg:fleury" plural "false" caps "false" noprefix "false" \end_inset ). \series bold Demostración: \series default Es claro que si el algoritmo funciona genera un tour euleriano. Sea \begin_inset Formula $s$ \end_inset el nodo inicial, cuando \begin_inset Formula $o(s)>0$ \end_inset , \begin_inset Formula $P$ \end_inset es un paseo que no repite ejes, por lo que todos los nodos salvo el primero y el último tienen orden par (por ser \begin_inset Formula $G$ \end_inset euleriano) y, como estos dos tienen orden impar, se puede salir del último añadiendo otro eje al camino en cada paso hasta llegar a \begin_inset Formula $s$ \end_inset y no poder salir, momento en que queremos ver que \begin_inset Formula $E=\emptyset$ \end_inset . Si no fuera así, al final existiría un \begin_inset Formula $e\in E$ \end_inset en una componente conexa de \begin_inset Formula $G$ \end_inset distinta a la de \begin_inset Formula $s$ \end_inset , pero la conexión con \begin_inset Formula $s$ \end_inset salvo en nodos aislados es un invariante del bucle. En efecto, al principio de una iteración, \begin_inset Formula $i$ \end_inset conecta con \begin_inset Formula $s$ \end_inset porque no es aislado y solo se rompe la conexión si se quita un eje de corte, pero entonces todos los ejes adyacentes a \begin_inset Formula $i$ \end_inset , \begin_inset Formula $(i,j_{1}),\dots,(i,j_{k})$ \end_inset , serían de corte y \begin_inset Formula $G-i$ \end_inset tendría \begin_inset Formula $k$ \end_inset componentes conexas. Sea entonces \begin_inset Formula $V_{p}$ \end_inset la componente conexa con \begin_inset Formula $j_{p}$ \end_inset , si fuera \begin_inset Formula $s\notin V_{p}$ \end_inset , como todos los nodos de \begin_inset Formula $V_{p}$ \end_inset tienen orden par salvo \begin_inset Formula $j_{p}$ \end_inset que tendría orden impar al haber eliminado \begin_inset Formula $(i,j_{p})$ \end_inset , la suma de los órdenes sería impar \begin_inset Formula $\#$ \end_inset , luego \begin_inset Formula $s\in V_{p}$ \end_inset y, como \begin_inset Formula $V_{1},\dots,V_{k}$ \end_inset es una partición, \begin_inset Formula $k=1$ \end_inset . Por tanto \begin_inset Formula $i$ \end_inset es un nodo hoja y eliminar el eje de corte deja a \begin_inset Formula $i$ \end_inset aislado. \end_layout \begin_layout Standard \begin_inset Float algorithm wide false sideways false status open \begin_layout Plain Layout \begin_inset ERT status open \begin_layout Plain Layout \backslash Entrada{Grafo euleriano conexo $G=(V,E)$.} \end_layout \begin_layout Plain Layout \backslash Salida{Tour euleriano $P$ de $G$.} \end_layout \begin_layout Plain Layout Tomar $i \backslash in V$ \backslash ; \end_layout \begin_layout Plain Layout $P \backslash gets(i)$ \backslash ; \end_layout \begin_layout Plain Layout \backslash Mientras{$E \backslash neq \backslash emptyset$}{ \end_layout \begin_layout Plain Layout \backslash lSSi{existe $(i,j) \backslash in E$ que no sea de corte}{sacar $(i,j)$ de $E$} \end_layout \begin_layout Plain Layout \backslash lEnOtroCaso{sacar un $(i,j)$ de $E$} \end_layout \begin_layout Plain Layout $P \backslash gets Pj$ \backslash ; \end_layout \begin_layout Plain Layout $i \backslash gets j$ \backslash ; \end_layout \begin_layout Plain Layout } \end_layout \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "alg:fleury" \end_inset Algoritmo de Fleury. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Section Problema del cartero chino \end_layout \begin_layout Standard Dada una red \begin_inset Formula $(V,E,\ell)$ \end_inset , el \series bold problema del cartero chino \series default consiste en obtener un paseo cerrado de longitud mínima que incluya todos los ejes al menos una vez. Para resolverlo: \end_layout \begin_layout Enumerate Calculamos la longitud de los caminos más cortos entre cada par de nodos, por ejemplo con el algoritmo de Dantzig. \end_layout \begin_layout Enumerate Identificamos los nodos de orden impar, de los que habrá un número par, y los emparejamos minimizando la suma de las longitudes de los caminos más cortos entre cada par. \end_layout \begin_layout Enumerate Duplicamos los ejes de un camino más corto entre cada par, obteniendo un grafo euleriano. \end_layout \begin_layout Enumerate Obtenemos un tour euleriano, que será la solución. \end_layout \begin_layout Section Grafos hamiltonianos \end_layout \begin_layout Standard Dado un grafo \begin_inset Formula $G=(V,E)$ \end_inset , un camino es \series bold hamiltoniano \series default si contiene a todos los vértices. Un grafo es hamiltoniano si admite un ciclo hamiltoniano. \end_layout \begin_layout Standard El \series bold grafo clausura \series default de \begin_inset Formula $G$ \end_inset , \begin_inset Formula $[G]$ \end_inset , es el grafo resultante de añadir a \begin_inset Formula $G$ \end_inset los \begin_inset Formula $(u,v)\in E^{\complement}$ \end_inset con \begin_inset Formula $o(u)+o(v)\geq|V|$ \end_inset hasta que no quede ningún \begin_inset Formula $(u,v)\in E^{\complement}$ \end_inset que cumpla la condición. Como \series bold teorema \series default , \begin_inset Formula $G$ \end_inset es hamiltoniano si y sólo si lo es \begin_inset Formula $[G]$ \end_inset . \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\implies]$ \end_inset \end_layout \end_inset Trivial. \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\impliedby]$ \end_inset \end_layout \end_inset Si \begin_inset Formula $G$ \end_inset no fuera hamiltoniano y, para obtener \begin_inset Formula $[G]$ \end_inset , le hubiéramos añadido los ejes \begin_inset Formula $e_{1},\dots,e_{n}$ \end_inset en ese orden, existiría un \begin_inset Formula $e_{k}=:(u,v)$ \end_inset tal que \begin_inset Formula $G_{i}:=(V,E_{i}):=G+\{e_{1},\dots,e_{i}\}$ \end_inset es hamiltoniano si y sólo si \begin_inset Formula $i>k$ \end_inset , por lo que existe un camino hamiltoniano \begin_inset Formula $(u=:u_{1})u_{2}\cdots(u_{n}:=v)$ \end_inset en \begin_inset Formula $G_{k}$ \end_inset , con \begin_inset Formula $n:=|V|$ \end_inset . Sean ahora \begin_inset Formula $X:=\{i\in\{2,\dots,n-2\}:(u_{i},v)\in E_{k}\}$ \end_inset e \begin_inset Formula $Y:=\{i\in\{2,\dots,n-2\}:(u_{i+1},u)\in E_{k}\}$ \end_inset , se tiene \begin_inset Formula $|X|=o(u)-1$ \end_inset e \begin_inset Formula $|Y|=o(v)-1$ \end_inset , pero como \begin_inset Formula $o(u)+o(v)\geq n$ \end_inset en \begin_inset Formula $G_{k}$ \end_inset , \begin_inset Formula $|X|+|Y|=o(u)+o(v)\geq n-2>n-1=|\{2,\dots,n-2\}|$ \end_inset y existe \begin_inset Formula $j\in X\cap Y$ \end_inset , con lo que \begin_inset Formula $u_{1}u_{k}u_{k+1}\cdots u_{n}u_{k-1}u_{k-2}\cdots u_{1}$ \end_inset es un ciclo hamiltoniano en \begin_inset Formula $G_{j}\#$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{sloppypar} \end_layout \end_inset Una \series bold sucesión hamiltoniana \series default es una tupla \begin_inset Formula $(a_{1},\dots,a_{n})$ \end_inset de naturales tal que todo grafo \begin_inset Formula $(\{1,\dots,n\},E)$ \end_inset con \begin_inset Formula $o(1)\leq\dots\leq o(n)$ \end_inset y \begin_inset Formula $o(i)\geq a_{i}$ \end_inset para cada \begin_inset Formula $i$ \end_inset es hamiltoniano. Como \series bold teorema \series default , para \begin_inset Formula $n\geq3$ \end_inset , \begin_inset Formula $(a_{1},\dots,a_{n})$ \end_inset con \begin_inset Formula $a_{1}\leq\dots\leq a_{n}