Calea euleriană
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
În teoria graficelor, noțiunea de cale euleriană poate fi definită pentru diferite structuri relaționale .
O cale euleriană peste un multigraf este o cale care atinge toate marginile sale o singură dată. Această definiție se aplică și graficelor nedirecționate , structuri care pot fi considerate cazuri speciale de multigrame.
În mod similar, calea euleriană pe un multidigraf înseamnă o cale care atinge toate arcele sale o singură dată. Această definiție se aplică și digrafelor , structuri care pot fi considerate cazuri speciale ale multidigrafelor.
Aceste definiții se extind apoi la tot felul de îmbogățiri ale multigrafelor (de exemplu la rețelele de transport) și ale multidigrafelor (de exemplu la diferite tipuri de automate și mașini formale ). Cu toate acestea, mediul natural pentru studierea acestor noțiuni rămâne cel al multigrafelor și multidigrafelor. Mai exact, sunt neglijate și posibilitățile de a avea bucle.
Nu toate multi-grafice și nu toate multi-grafice au căi euleriană. Prin urmare, distingem multidigrafele euleriene și multidigrafele euleriene, structuri cu căi euleriene.
De asemenea, se observă că prezența buclelor nu afectează posibilitatea identificării căilor eulerian; la fel se întâmplă și pentru îmbogățirea multigrafelor și a multidigrafelor.
Apoi se pune întrebarea dacă un multigraf sau un multigraf fără bucle este eulerian sau nu. Această problemă a fost rezolvată complet complet de Euler în 1736 cu o lucrare care a marcat nașterea teoriei și topologiei graficelor . Din această lucrare de pionierat derivă calificarea eulerienilor la aceste grafice și la căile care le caracterizează.
Trebuie remarcat faptul că, ca sinonim pentru calea euleriană pe un multigraf, se folosește și termenul cale bijectivă pe margini, în timp ce ca sinonim pentru calea euleriană pe un multidigraf se folosește și termenul cale bijectivă pe arce. De fapt, aceste căi pot fi considerate funcții injective și surjective pe setul de margini sau pe setul de arce.
Cazurile particulare ale căilor euleriene sunt căi închise, adică căile euleriană având vârful coincident inițial și final. Acestea se numesc circuite eulerian.
Elemente conexe
- Calea Hamiltoniană
- Lemă de strângere de mână , demonstrată de Euler în lucrarea sa originală, care arată că orice grafic conectat neorientat are un număr par de vârfuri de grad impar.
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe calea euleriană
