6.5: Eulerización y el problema del cartero chino

Última actualización
Guardar como PDF

Page ID: 110626

$ \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}}$

No todos los gráficos tienen un camino o circuito de Euler, sin embargo, nuestro inspector de césped aún necesita hacer sus inspecciones. Su objetivo es minimizar la cantidad de caminar que tiene que hacer. Para ello, tendrá que duplicar algunos bordes en la gráfica hasta que exista un circuito de Euler.

Eulerización

Eulerización es el proceso de agregar bordes a una gráfica para crear un circuito de Euler en una gráfica. Para eulerizar una gráfica, los bordes se duplican para conectar pares de vértices con grado impar. Conectar dos vértices de grado impares aumenta el grado de cada uno, dándoles a ambos grados pares. Cuando dos vértices de grados impares no están conectados directamente, podemos duplicar todos los bordes en un camino que conecta los dos.

Tenga en cuenta que solo podemos duplicar bordes, no crear bordes donde no había uno antes. Duplicar bordes significaría caminar o conducir por una carretera dos veces, ¡mientras que crear un borde donde no había uno antes es parecido a instalar una nueva carretera!

Ejemplo 11

Para la gráfica rectangular mostrada, se muestran tres posibles eulerizaciones. Observe en cada uno de estos casos los vértices que comenzaron con grados impares tienen grados pares después de la eulerización, permitiendo un circuito de Euler.

$gt32.svg$ $gt33.svg$

$gt34.svg$ $gt35.svg$

En el ejemplo anterior, notarás que la última eulerización requirió duplicar siete aristas, mientras que las dos primeras solo requirieron duplicar cinco aristas. Si estuviéramos eulizando la gráfica para encontrar un sendero para caminar, querríamos la eulerización con duplicaciones mínimas. Si los bordes tuvieran pesos que representaran distancias o costos, entonces querríamos seleccionar la eulerización con el peso agregado total mínimo.

Pruébalo ahora 4

Eulerizar la gráfica mostrada, después encontrar un circuito de Euler en la gráfica eulerizada.

$gt20.svg$

Responder

Esta gráfica puede ser eulerizada duplicando el borde BC, como se muestra. Un posible circuito de Euler en la gráfica eulerized es ACDBCBA

$gt58.svg$

Ejemplo 12

Al mirar nuevamente la gráfica para nuestro inspector de césped de los Ejemplos 1 y 8, se muestran resaltados los vértices con grado impar. Con ocho vértices, siempre tendremos que duplicar al menos cuatro aristas.

$gt26.svg$

Solución

En este caso, necesitamos duplicar cinco aristas ya que dos vértices de grados impares no están conectados directamente. Sin pesos no podemos estar seguros de que esta es la eulerización que minimiza la distancia a pie, pero se ve bastante bien.

$gt36.svg$

El problema de encontrar la eulerización óptima se llama el Problema del Cartero Chino, nombre dado por un estadounidense en honor al matemático chino Mei-Ko Kwan quien primero estudió el problema en 1962 mientras trataba de encontrar rutas de entrega óptimas para los transportistas postales. Este problema es importante para determinar rutas eficientes para camiones de basura, autobuses escolares, verificadores de parquímetros, barredoras de calles y más.

Desafortunadamente, los algoritmos para resolver este problema son bastante complejos. Algunos casos más simples se consideran en los ejercicios.