Camí eulerià

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un camí eulerià 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 (camí = 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[modifica | modifica el codi]

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[modifica | modifica el codi]

L'origen de la teoria dels camins eulerians va ser plantejat i resolt pel propi 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?

Els ponts de Königsberg

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?

Graf dels ponts de Königsberg

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[modifica | modifica el codi]

Atès  G (V, E \,) 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) \ge 2 i parell.
3)  G = \coprod_{i = 1}^n C_i tots disjunts en els arcs, és a dir  C^E_i \cap \; C^E_j = \emptyset \; amb {i \not \ne \; j}

Propietats[modifica | modifica el codi]

  • Un graf connex i no dirigit es diu que és eulerià si cada vèrtex té un grau parell.
  • Un graf no dirigit és eulerià si és connex i si es pot descompondre en un amb els vèrtexs disjunts.
  • Si un graf no dirigit G és eulerià llavors la seva graf-línia L ( G ) es diu que és també eulerià.
  • Un graf dirigit és eulerià si és connex i cada vèrtex té graus interns iguals als externs.
  • Un graf no dirigit es diu que és susceptible de ser recorregut (en anglès: traversa ) si és connex i almenys dos vèrtexs en el graf tenen grau senar.

Comptant circuits eulerians en dígrafs[modifica | modifica el codi]

El nombre de circuits eulerià en els dígrafs pot ser calculat mitjançant el teorema denominat en Anglès: BEST-theorem , procedent dels noms dels seus fundadors: de B ruijn, van Aardenne- I hrenfest, S Mith i T utte.

En aquest teorema s'esmenta que donat un dígraf eulerià G : = ( V , I ), el nombre camins eulerians no-equivalestes en el graf és

 C \prod_{v \in V}(\deg^(v) -1) !

o equivalentment

 C \prod_{v \in V}(\deg^- (v) -1) !

sent C qualsevol cofactor de la matriu laplaciana de G .

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Camí eulerià Modifica l'enllaç a Wikidata
  • "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.
  • Recreations Mathématiques IV , Lucas, I., Paris, 1921.
  • "Deux problemes de geometria de situation", Fleury, Journal de mathématiques elementaires (1883), 257-261.