Què és un camí d'Euler?

És una trajectòria o camí que conté totes les arestes d'un graf o xarxa, però només passa una vegada per cadascuna d'elles.

Podries trobar un camí d'Euler en aquests grafs?

Nodes amb grau parell 3
Nodes amb grau imparell 2
Camí d'Euler
Nodes amb grau parell 3
Nodes amb grau imparell 2
Camí d'Euler
Nodes amb grau parell 4
Nodes amb grau imparell 2
Camí d'Euler
Nodes amb grau parell 8
Nodes amb grau imparell 0
Camí d'Euler
Nodes amb grau parell 1
Nodes amb grau imparell 4
Camí d'Euler No
Nodes amb grau parell 4
Nodes amb grau imparell 4
Camí d'Euler No

Prémer la tecla SHIFT i seleccionar un node per moure'l.

Prémer en un punt de la pantalla per afegir un nou node.

Per eliminar un node o una aresta, seleccionar i prémer la tecla DEL

Per unir dos nodes per una nova aresta, seleccionar el node, i sense deixar-lo, al seu nou veí

L'any 1254 l'Orde dels Cavallers Teutons va fundar la ciutat de Königsberg, que literalment es tradueix com "La muntanya del rei". Degut a la seva bona posició estratègica sobre el riu Pregel, va esdevenir un punt d'intercanvi i important ciutat medieval. El riu dividia la ciutat en 4 regions connectades per 7 ponts: el Pont de Blacksmith, el Pont Enllaç, el Pont Alt, el Pont Verd, el Pont de Mel, el Pont del Comerciant i el Pont de Llana.

Königsberg
Mapa de Königsberg al segle XVII

Es diu que els habitants de Königsberg passaven les tardes de Diumenge passejant per la ciutat. El problema que els mateixos ciutadants es van plantejar és si era possible creuar exactament una vegada per tots i cada un dels ponts.

El 1727 Leonhard Euler treballava per l'Acadèmia de Ciències de Sant Petersburg. El 1736 Euler va escriure la solució en un article amb el títol 'Solutio problematis ad geometriam situs pertinentis'

Tot i que no està clar com Euler va arribar a conéixer aquest problema, s'han trobat un seguit de cartes que s'escrivia amb Carl Leonhard Gottlieb Ehler, alcalde de Danzig, a 80 milles de Königsberg, on es parlava d'aquest problema.

El mateix Euler, en una carta a un matemàtic italià, el 13 de Març de 1736, escriu:

M'han proposat un problema sobre l'illa de la ciutat de Königsberg, envoltada per un riu travessat per 7 ponts, i se m'ha plantejat si algú podia travessar els ponts en un camí que els enllaci de tal manera que cada pont només sigui creuat una vegada.

Königsberg
Diagrama del problema dels ponts de Königsberg de l'article de Euler de 1736

Euler, en la mateixa carta, considera que la qüestió és "banal", però la considera d'interés pel fet que no es pot resoldre ni amb geometria, ni algebra ni amb l'art de comptar. Associa el problema a la geometria de posició, introduïda per Leibniz recentment.

En l'article de 1736 Euler descriu el problema, resol el cas particular de Königsberg i finalment, generalitza el problema. Euler es pregunta:

Sigui quina sigui la distribució i divisió del riu en branques i el número de ponts que el trevessen, es pot saber si és possible creuar tots els ponts exactament una vegada?

Tot i que es pot anar provant totes les possibilitats, Euler ho descarta, ja que seria pesat de fer i impossible si hi hagués més ponts i illes.

Euler usa les lletres en majúscula A, B, C i D per referir-se a les illes i les lletres en minúscula a, b, c, d, e, f i g per referir-se als ponts. Si un caminant va des de A a B pel pont a o b, ho escriu AB - on la primera lletra representa la regió d'on surt el caminant i la segona lletra, la regió cap a on es dirigeix.

D'aquesta manera, si un camí consta de n lletres, per tal que tingui solució, cal que estigui unit per n-1 ponts. En el cas dels ponts de Königsberg, el problema té 7 ponts i, per tant, requereix d'un camí de 8 lletres (que es poden repetir).

Quina és la relació entre el número de ponts que uneixen dues regions amb el número de lletres corresponents a aquest camí? Mirem l'exemple senzill proposat per Euler:

Königsberg
Cas senzill unint 2 zones per 6 ponts (número parell)

En el cas anterior la seqüència començant per A és:

AaBbAcBdAeBfA

o bé, ometent els ponts:

AB-BA-AB-BA-AB-BA

Euler dedueix que si el nombre de ponts és imparell, aleshores el nombre de lletres A que hi ha d’haver a la seqüència seria la meitat d’aquest nombre de ponts més un i si el nombre de ponts és parell és directament la meitat.

Amb això és suficient per determinar la impossibilitat del camí buscat. Una de les illes, A, està connectada per 5 ponts; per tant, el camí ha de contenir 3 lletres A. De manera similar, ha d'haver 2 lletres B, 2 lletres C i 2 lletres C.

Königsberg
Diagrama del problema dels ponts de Königsberg de l'article de Euler de 1736
Regió A B C D
Ponts 5 3 3 3
Freqüència 3 2 2 2

Sumant la fila de freqüències de totes les lletres, que representen les repeticions de cada lletra en el camí, veiem que faria falta 9 lletres, però el camí usant 7 ponts només en necessita 8. Per tant, no existeix el camí que busquem.

Generalitzant, la freqüència de cada lletra depenent del nombre de ponts, si aquest és imparell és . Si és parell és o si comença per aquesta regió.

Podem escriure la taula de freqüències en aquest cas, marcant amb un asterisc les illes amb un nombre senar de ponts

Königsberg
Un exemple més complicat: 2 illes, 4 rius i 15 ponts


Regió A B C D* E* F
Ponts 8 4 4 3 5 6
Freqüència 4 2 2 2 3 3

Si la suma de freqüències és el nombre de lletres necessaries menys u, donat el nombre de ponts, el camí que busquem existirà. En aquest cas, la fila de freqüències suma 16, que és exactament el nombre de lletres necessaries per un camí amb 15 ponts, tal com és. Euler va mostrar un possible camí:

EaFbBcFdAeFfCgAhCiDkAmEnApBoElD

Aquest tipus de problemes es poden resoldre molt més fàcilment si ho representem en forma de graf, tal com es va començar a fer a partir del segle XIX. L'objectiu és determinar si una figura es pot dibuixar sense aixecar el llapis i sense repetir cap aresta (Camí Eulerià). Podem transformar els dibuixos que hem vist en grafs:

Königsberg
Graf del problema dels ponts de Königsberg
Königsberg
Graf del problema ampliat proposat i solucionat per Euler


  • Si hi ha més de dos nodes amb grau senar, aleshores el camí Eulerià no és possible

  • Si hi ha exactament dos nodes amb grau senar, aleshores el camí Eulerià existeix si comença en un dels dos nodes

  • Si no hi ha cap node amb grau senar, el camí Eulerià existeix començant per qualsevol node.

Camins d'un pas

Königsberg

Quants ponts estan connectats a cada illa?
Quines illes estan connectades?

Camins de dos passos

Camins que passen per dues arestes

Quants camins de dos passos hi ha de ...

\[n_{34}=2\]
C d e D
C c e D

\[n_{14}=4\]
A c g D
A a f D
A b f D
A d g D

\[n_{23}=5\]
B f g C
B a c C
B a d C
B b d C
B b c C

\[n_{13}=1\]
A e g C

\[n_{11}=9\]
A c c A
A d d A
A a a A
A b b A
A e e A
A c d A
A d c A
A a b A
A b a A

\[n_{44}=3\]
D g g D
D e e D
D f f D

Com trobem el número de camins?

Per trobar el número de camins que surten de C i arriben a D buscarem quants ponts surten de C i arriben a una altra illa que està també connectada al punt final, D. Veurem com multipliquem totes les possibilitats.

\[n_{34}=\color{orange}{2} \cdot \color{purple}{1} + \color{orange}{0} \cdot \color{purple}{1} + \color{orange}{0} \cdot \color{purple}{1} + \color{orange}{1} \cdot \color{purple}{0} \]
\[M^2=\begin{pmatrix} 0 & 2 & 2 & 1\\ 2 & 0 & 0 & 1\\ \color{orange}{2} & \color{orange}{0} & \color{orange}{0} & \color{orange}{1}\\ 1 & 1 & 1 & 0\\ \end{pmatrix} \cdot \begin{pmatrix} 0 & 2 & 2 & \color{purple}{1}\\ 2 & 0 & 0 & \color{purple}{1}\\ 2 & 0 & 0 & \color{purple}{1}\\ 1 & 1 & 1 & \color{purple}{0}\\ \end{pmatrix}\]

Camins de tres passos

Camins que passen per 3 arestes

Si elevem al cub la matriu d'adjacència obtindrem els camins de longitud 3 entre dos nodes. Els termes de la diagonal representen quants triangles es poden recórrer començant i acabant per un dels nodes.

Si sumem els elements de la diagonal obtindrem 6 vegades el nombre de triangles totals. Hem comptat dues vegades els triangles degut als dos possibles sentits (horari i anti-horari) i 3 vegades més ja que hem comptat un triangle per cada node (3 nodes en un triangle)

triangle1
triangle2
triangle3
triangle4

Camins de + passos

Podem seguir el mateix procediment per calcular el nombre de camins de longituds diferents d'una illa a una altra. L'element \[A^l_{ij}\] ens diu quants camins de longitud l entre els nodes i i j hi ha. Cal tenir en compte que s'inclouen els camins que repeteixen arestes i camins en les dues direccions.

Com podríem modificar el mapa de Königsberg per poder recórrer un camí Eulerià? I un cicle Eulerià?

Königsberg
graf

ACTIVITATS

Fulla d'activitats

Explicació de l'activitat