Hola25
Hola25 Logo
Hola25
Utilizatori disponibili

Înapoi la blog

Un fir continuu așezat între repere pe un suport de lemn.
Ilustrație generată.
Matematică

Desen dintr-o singură linie: trasee euleriene

Hola25
Hola25
Autor

18 noiembrie 2026

6 min citire

În acest articol

Un desen poate fi parcurs fără ridicarea creionului și fără repetarea unei linii dacă toate liniile sale sunt conectate și există zero sau două noduri de grad impar. Gradul unui nod este numărul capetelor de linii care se întâlnesc acolo. Cu două noduri impare, traseul începe într-unul și se termină în celălalt.

Considerăm linii care pot fi parcurse în ambele sensuri. Este permis să treci de mai multe ori prin același nod, dar fiecare linie trebuie folosită exact o dată. Aceste reguli descriu un traseu eulerian și sunt diferite de cerința de a vizita fiecare punct o singură dată.

Cum transformi desenul într-un graf?

Marchezi capetele și punctele de întâlnire drept noduri. Porțiunile de linie dintre două noduri sunt muchii. Lungimea, forma curbată sau înclinarea unei muchii nu schimbă problema: contează ce noduri leagă.

O intersecție vizuală nu este automat un nod. Dacă desenul reprezintă două drumuri care se suprapun fără legătură, nu poți schimba drumul acolo. Dacă enunțul permite trecerea de pe una dintre linii pe cealaltă, intersecția trebuie marcată ca nod și fiecare linie se împarte în porțiunile corespunzătoare.

De asemenea, două muchii distincte pot lega aceeași pereche de noduri. Ele se numără separat și fiecare trebuie parcursă. Nu le reduce la una numai pentru că au aceleași capete.

Ce înseamnă gradul și cum îl numeri?

Într-un capăt liber se întâlnește o singură muchie, deci gradul este unu. La un colț simplu se întâlnesc două, deci gradul este doi. Un nod cu trei ramuri are gradul trei.

Dacă o muchie pleacă dintr-un nod și revine în același nod, ea formează o buclă. Contribuie cu doi la grad, deoarece are ambele capete în acel punct. Această convenție păstrează regula că suma gradelor este de două ori numărul muchiilor.

Din această sumă rezultă că numărul nodurilor impare trebuie să fie par. O listă cu exact trei noduri impare indică o eroare de numărare sau de identificare a nodurilor. Recontrolează desenul înainte să cauți traseul.

De ce apar perechi de intrări și ieșiri?

Într-un nod intermediar, fiecare sosire trebuie urmată de o plecare pe o muchie încă nefolosită. Muchiile utilizate acolo se grupează în perechi. Dacă toate sunt parcurse, gradul nodului este par.

Doar începutul și sfârșitul pot avea o muchie fără pereche: pleci din primul fără să fi sosit înainte și ajungi în ultimul fără să mai pleci. De aceea, un traseu cu capete diferite cere exact două noduri impare.

Dacă revii la punctul de pornire, și la el intrările și ieșirile se împerechează. Toate gradele trebuie să fie pare. Pentru un graf conectat, aceste condiții sunt și suficiente, nu doar necesare. Distincția dintre traseul deschis și circuit este prezentată în lecția OpenStax despre trasee euleriene.

Cum desenezi o căsuță dintr-o singură linie?

Etichetează baza din stânga cu A și baza din dreapta cu B. Colțul superior din dreapta este C, cel din stânga D, iar vârful acoperișului E. Desenul are muchiile AB, BC, CD, DA, DE și EC.

A și B au gradul doi. E are tot gradul doi. C și D au gradul trei: fiecare aparține conturului dreptunghiului și unei laturi a acoperișului. Există exact două noduri impare, C și D.

Un traseu valid este D, A, B, C, D, E, C. Perechile consecutive folosesc, în ordine, DA, AB, BC, CD, DE și EC. Lista conține toate cele șase muchii, fiecare o singură dată.

Observă că D și C apar de două ori în lista nodurilor. Acest lucru este permis. Restricția privește repetarea unei muchii, nu repetarea unui punct. Dacă ai interzice revenirea în noduri, ai schimba problema.

De ce nu poți porni de oriunde?

În căsuța descrisă, traseul trebuie să înceapă în C sau D. Dacă pornești din A, consumi o plecare fără sosire într-un nod de grad par, iar împerecherea necesară nu mai poate fi păstrată până la final.

Poți întoarce traseul valid și porni din C, terminând în D. Aceasta oferă două sensuri pentru aceeași succesiune de muchii. Existența a două capete posibile nu înseamnă că fiecare alegere intermediară conduce automat la o soluție.

Pentru a lucra sistematic, folosește metoda de rezolvare la matematică: scrie regulile, calculează gradele, identifică începutul și verifică lista muchiilor după construcție.

Ce se întâmplă dacă toate gradele sunt pare?

Consideră două triunghiuri care au numai nodul A în comun. Primul are muchiile AB, BC, CA, iar al doilea AD, DE, EA. Nodul A are gradul patru, iar celelalte au gradul doi.

Circuitul A, B, C, A, D, E, A parcurge toate cele șase muchii și revine la început. Ai parcurs întâi un circuit mic, apoi pe celălalt, lipindu-le în nodul comun.

Această idee ajută și la justificarea existenței circuitului în cazul general: într-un graf conectat cu grade pare, poți integra circuite rămase prin noduri comune până folosești toate muchiile. OpenStax explică criteriul circuitelor euleriene, împreună cu rolul conectării.

De ce trebuie verificată conectarea?

Două triunghiuri complet separate au numai grade pare. Totuși, nu le poți desena pe amândouă fără ridicarea creionului și fără adăugarea unei linii între ele. Condiția de paritate nu creează o legătură care lipsește.

În criteriu ne referim la partea desenului formată din muchii. Un punct izolat, care nu are nicio linie de parcurs, nu împiedică traseul pentru liniile existente. Dacă problema cere și marcarea acelui punct separat, este o cerință suplimentară.

Pentru a testa conectarea, pornește dintr-un nod cu muchii și urmărește dacă poți ajunge la toate celelalte muchii prin legăturile desenate. Nu confunda apropierea pe pagină cu existența unei conexiuni.

Cum eviți închiderea prematură a drumului?

Imaginează-ți un triunghi BCD și încă o muchie BA, cu A în exterior. B are gradul trei, iar A gradul unu. Dacă pornești din B și mergi imediat la A, te oprești înainte să fi parcurs triunghiul.

Un traseu bun este B, C, D, B, A. Mai întâi consumi circuitul, apoi folosești legătura spre capătul final. Exemplul arată de ce „există un traseu” nu înseamnă „orice alegere funcționează”.

Poți evita, când există alternative, o muchie a cărei eliminare separă muchii încă nefolosite de poziția ta. Nu te baza doar pe încercări rapide: notează ce a rămas conectat. Alegerea motivată a următoarei muchii clarifică de ce înțelegerea depășește memorarea.

Exerciții cu răspunsuri

  1. Un pătrat are numai cele patru laturi, fără diagonale. Poate fi trasat dintr-o singură linie, revenind la început?
  2. Același pătrat primește o singură diagonală. Unde trebuie să înceapă și să se termine traseul?
  3. Sunt desenate ambele diagonale. Se poate parcurge fiecare segment o singură dată într-o singură trasare?
  4. Două triunghiuri sunt separate, fără muchie comună și fără nod comun. Ajută faptul că toate gradele sunt pare?

Răspunsuri: da, conturul este un circuit; la capetele diagonalei, singurele noduri impare; nu, cele patru colțuri au grad impar, indiferent dacă intersecția diagonalelor este un nod de grad patru; nu, lipsește conectarea.

Cu un profesor de matematică poți verifica separat criteriul și traseul propus. Primul demonstrează dacă o soluție există; al doilea trebuie să arate efectiv că fiecare muchie a fost folosită exact o dată.