Cicle euleriano

En la teoria de grafos, un camí euleriano és un camí que passa per cada aresta una i solament una volta. Un cicle o circuit euleriano és un camí tancat que recorre cada aresta exactament una volta. El problema de trobar dits camins va ser discutit per primera volta per Leonhard Euler, en el famós problema dels ponts de Königsberg.

Cicle euleriano

Cicles eulerianos

Dibuixar un sobre obert, com el de l'image, sense alçar el llapis del paper ni passar dos voltes pel mateix lloc, és possible. En canvi, dibuixar el sobre tancat (prescindint del punt 5 i les seues llínees adjacents) és impossible.

En l'image, $C=\{1,2,3,4,6,3,5,4,1\}$ és un cicle euleriano, després és un grafo euleriano.

Un grafo és una representació, un model, compost per un número determinat de vèrtiços (nodos) i un número d'arcs (arestes) que els relacionen, cada aresta o arc té la capacitat de relacionar dos nodos. La paraula cicle s'ampra en teoria de grafos per a indicar un camí tancat en un grafo, és dir, que el nodo d'inici i el nodo final són el mateix, com a contrapartida un camí hamiltoniano és un camí que recorre tots els vèrtiços d'un grafo sense passar dos voltes pel mateix vèrtiç. Si el camí és tancat es diu un cicle hamiltoniano.

Si un grafo admet un cicle euleriano, es denomina grafo euleriano.

Característiques

S'elegix per a iniciar el traç qualsevol punt impar i es terminarà en l'atre punt o vèrtiç impar.

Vore també

• Problema dels ponts de Königsberg
• Cicle hamiltoniano
• Problema del carter chinenc
• Glossari en teoria de grafos

Referències

• "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.
• Récréations Mathématiques IV, Lucas, E., Paris, 1921.
• "Deux problemes de geometrie de situation", Fleury, Journal de mathematiques elementaires (1883), 257-261.
• "Discrete Mathematics with Applications", Susanna Epp, Fourth Edition
• "Discreta Mathematics and its application"", Rosen 7.ª edició
• https://en.wikipedia.org/wiki/Eulerian_path