Correos tiene oficinas de atención al cliente, que son las que normalmente vemos en las ciudades y pueblos, y otras oficinas llamadas carterías que son aquellas en las que se tienen almacenadas las cartas y paquetes que hay que repartir. Desde estas oficinas salen los carteros y carteras a realizar sus rutas, ya sea andando o en vehículos motorizados, normalmente furgonetas.

Para poder analizar las rutas de nuestra oficina de cartería, tendremos que contactar con dicha oficina para que nos indiquen con cuánto personal cuentan y qué partes del callejero tienen asignadas aquellas personas que realizan su trabajo andando y qué partes del callejero tienen asignadas aquellas que se encargan de la recogida de las cartas de los buzones y de la entrega de paquetes en puntos Citypaq, las cuales realizan su ruta usando vehículos motorizados.

1. Localiza una oficina de Correos situada en la zona de estudio y solicita las zonas de reparto que corresponden a los carteros y carteras asignadas a dicha oficina.
2. Pega en GeoGebra un mapa de la zona.
   1. Marca sobre el mapa los polígonos que cubren las zonas asignadas a cada cartero o cartera. Utiliza un color distinto para cada polígono. El resultado puede ser aproximado.
3. Repartiros por grupos de modo que cada zona esté asignada a un grupo de estudiantes.

El cartero o cartera tiene que recorrer todas las calles (y las dos aceras de cada calle) de la zona o sección que tiene asignada y, al ir andado, no importa el sentido en el que lo haga. Por tanto, el grafo que representa la situación en cada sección es un grafo no dirigido.

Cada grupo tiene que hacer el grafo de su sección. Para ello, hay que tener en cuenta que hay un nodo que marca el inicio de la ruta y que este es el que quede más cerca de la oficina de cartería.

Otro algoritmo que nos ayuda a encontrar caminos eulerianos es el algoritmo de Hierhozel.

Algoritmo de Hierhozel

Caso 1:

1. Verificar que el grafo es conexo y todos los vértices tienen grado par. En este caso el grafo posee un ciclo euleriano
2. Creamos una cadena donde almacenar la sucesión ordenada de vértices que forman el ciclo \(C=\{\}\)
3. Elegimos un vértice cualquiera, V
4. Elegimos un ciclo que comience y acabe en V
5. Eliminamos del grafo inicial todas las aristas que forman el ciclo y añadimos la sucesión ordenada de vértices a la cadena
6. Del grafo que nos queda elegimos un vértice que no haya quedado aislado y que pertenezca a la sucesión de vértices del ciclo que hay almacenado en la cadena, V
7. Elegimos un ciclo que comience y termine en V e insertamos la sucesión ordenada de vértices que lo forman en el lugar que le corresponde dentro de la cadena 
8. Borramos del grafo las aristas del ciclo cuyos vértices hemos insertado en la cadena
9. Repetimos el paso 6 hasta que hayamos eliminado todas las aristas

Caso 2:

1. Verificar que el grafo es conexo y sólo tiene dos vértices tienen grado impar. En este caso el grafo posee un camino euleriano
2. Trazamos una arista que una los dos vértices de grado impar, aunque ya hubiera una. Con esto conseguimos que todos los vértices de nuestro grafo tengan grado par, por lo que podemos encontrar un ciclo euleriano usando el algoritmo escrito en el caso 1
3. Cuando tengamos la sucesión ordenada de vértices del ciclo solución, buscamos el lugar que ocupa la arista que añadimos y cortamos la sucesión ordenada por ese sitio
4. Ponemos detrás del último vértice de la sucesión ordenada de vértices del ciclo la sucesión ordenada de vértices que estaba delante del lugar donde hemos realizado el corte. Lo que nos queda es un camino euleriano que parte de uno de los vértices de grado impar y termina en el otro

Veamos un ejemplo con el siguiente grafo.

Paso 1

Se comprueba que todos los vértices tienen grado par y por tanto existe un camino euleriano.

Paso 2

Creamos una cadena donde almacenar el ciclo \(C=\{\}\)

Paso 3

Se elige un vértice.  \( V_1 \)

Paso 4

Se busca un ciclo que comience y acabe en \( V_1 \).  \( \{V_1, V_2, V_5, V_3, V_1\} \)

Paso 5

Se elimina del grafo inicial el ciclo anterior.

Se añaden a la cadena \(C=\{ V_1, V_2, V_5, V_3, V_1\}\)

Paso 6

Del grafo que nos queda elegimos un vértice que no haya quedado aislado y que pertenezca al ciclo que hay almacenado en la cadena. Por ejemplo, \(V_3 \)

Paso 7

Se elige un ciclo que comience y termine en \( V_3 \) y lo insertamos en el lugar que le corresponde dentro de la cadena. \( \{ V_3, V_4, V_2, V_3 \}\)

Paso 8

Borramos las aristas del ciclo que hemos insertado

Paso 9

Como no hay más aristas el algoritmo ha terminado. 

El algoritmo ha generado dos ciclos \[ C_1 = \{ V_1, V_2, V_5, V_3, V_1 \} \] y  \[ C_2 = \{ V_3, V_4, V_2, V_3\} \] 

Sustituimos en en el ciclo \( C_1 \) el vértice \( V_3 \) por el ciclo \(C_2 \) que comienza y termina en \(V_3\). De esta forma \[ C= \{ V_1, V_2, V_5, V_3, V_2, V_4, V_3, V_1 \} \]

Aplica el algoritmo de Fleury o el algoritmo de Heirholzer al grafo del cartero o cartera y encuentra un camino o ciclo euleriano.