13: Euler y Hamilton
- Page ID
- 114422
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Algunos tipos de recorridos a través de una gráfica son particularmente importantes para los problemas de enrutamiento. Estaremos considerando algunos de estos en este capítulo
- 13.1: Euler Tours y Senderos
- Para introducir estos conceptos, necesitamos conocer algunos tipos especiales de paseos. Recordemos el ejemplo histórico de los puentes de Königsberg. El problema de encontrar una ruta que cruce cada puente exactamente una vez, equivale a encontrar un sendero de Euler en la gráfica correspondiente. Si queremos que la ruta comience y termine en el mismo lugar (por ejemplo, la casa de alguien), entonces el problema equivale a encontrar un recorrido de Euler en la gráfica correspondiente.
- 13.2: Caminos y Ciclos Hamilton
- A veces, en lugar de viajar a lo largo de cada conexión en una red, nuestro objetivo es simplemente visitar cada nodo de la red. Esto se relaciona con una estructura diferente en la gráfica correspondiente. Las definiciones de trayectoria y ciclo aseguran que los vértices no se repitan. Los caminos y los ciclos de Hamilton son herramientas importantes para planificar rutas para tareas como la entrega de paquetes, donde el punto importante no son las rutas tomadas, sino los lugares que se han visitado.
- 13.3: Resumen
- Esta página contiene el resumen de los temas tratados en el Capítulo 13.