Camí eulerià

Un camí o cicle eulerià és aquell camí que recorre tots els vèrtexs (nodes) d'un graf passant una i només una vegada per cada arc (aresta) del graf, i és condició necessària que torni al vèrtex inicial de sortida, per tant és un camí tancat (camí tancat = camí en un graf on coincideixen vèrtex inicial o de sortida i vèrtex final o meta). Una definició més formal el defineix com: " aquell camí que conté totes les arestes d'un graf només una vegada ".

En relació amb els camins eulerians Carl Hierholzer va publicar la primera caracterització completa dels grafs eulerians el 1873, provant matemàticament que de fet els grafs eulerians són exactament aquells grafs que estan connectats amb tots i on cada un els vèrtexs tenen grau parell.

Camins eulerians

exemple .

A la imatge, $C=\{1,2,3,4,6,3,5,4,1\}\,$ és un camí eulerià, també és un graf eulerià.

Un graf és una representació, un model, compost per un nombre determinat de vèrtexs (nodes) i un nombre d'arcs (arestes) que els relacionen, cada aresta o arc té la capacitat de relacionar dos nodes. La paraula camí s'empra en teoria de grafs per indicar un camí tancat en un graf, és a dir, que el node d'inici i el node final són el mateix, com a contrapartida un camí hamiltonià és un camí que recorre tots els vèrtexs d'un graf sense passar dues vegades pel mateix vèrtex. Si el camí és tancat se li diu camí hamiltonià.

Si un graf admet un camí eulerià, es denomina graf eulerià.

Història

Article principal: Problema dels ponts de Königsberg

L'origen de la teoria dels camins eulerians va ser plantejat i resolt pel mateix Leonhard Euler el 1736 en un problema que té el nom de Set ponts de la ciutat de Königsberg (Prússia oriental en el segle xviii i actualment, Kaliningrad, província russa) donant origen a la teoria dels grafs.

El problema s'enuncia de la manera següent: Dues illes en el riu Pregel, a Königsberg s'uneixen entre elles i amb la terra ferma mitjançant set ponts. És possible fer una passejada començant per una qualsevol de les quatre parts de terra ferma, creuant cada pont una sola vegada i tornant al punt de partida?

Euler va enfocar el problema representant cada part de terra per un punt i cada pont, d'una línia, unint els punts que es corresponen. Llavors, el problema anterior es pot traslladar a la següent pregunta: es pot recórrer el dibuix sense repetir les línies?

Euler va demostrar que no era possible, ja que el nombre de línies que incideixen en cada punt no és parell (condició necessària per entrar i sortir de cada punt, i per tornar al punt de partida, per camins diferents en tot moment).

Teorema

Sigui $G(V,E\,)$un graf no orientat i connex (no hi ha nodes aïllats) valen les següents expressions.

1) $G\,$ és eulerià;

2) $\forall v\in \ V$ amb grau $(v)\geq 2$ i parell.

3) $G=\coprod _{i=1}^{n}C_{i}$ tots disjunts en els arcs, és a dir $C_{i}^{E}\cap \;C_{j}^{E}=\emptyset \;$ amb ${i\not \neq \;j}$ o equivalentment

$C\prod _{v\in V}(\deg ^{-}(v)-1)!$ sent C qualsevol cofactor de la matriu laplaciana de G .

Vegeu també

• Glossari de teoria de grafs

Bibliografia

• Recreations Mathématiques IV, Lucas, I., Paris, 1921.
• "Deux problemes de geometria de situation", Fleury, Journal de mathématiques elementaires (1883), 257-261.
• "Solutio problematis ad geometriam situs pertinentis", Euler, L., Comment. Academiae Sci I. Petropolitanae 8 (1736), 128-140.
• "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Hierholzer, C. Mathematische Annalen 6 (1873), 30-32.