- 0 vârfuri impare: un circuit, din orice vârf înapoi la el
- 2 vârfuri impare: un drum de la unul la celălalt
- 4 sau mai multe: imposibil dintr-o singură trăsătură
Căutător de drumuri euleriene
Se poate desena casa lui Moș Nicolae fără să ridicați creionul și fără să treceți de două ori peste o linie? Se poate, dar numai începând dintr-unul din cele două colțuri de jos, și din fiecare există 44 de moduri. Motivul este gradul unui vârf, numărul de linii care se întâlnesc acolo: de fiecare dată când creionul trece printr-un vârf, folosește două dintre liniile lui. Leonhard Euler a găsit această regulă în 1736 cu cele șapte poduri din Königsberg. Trasați singur o figură, vedeți unde vă blocați și de ce, cereți un indiciu sau priviți un algoritm desenând-o. Alegeți o figură și trasați-o: atingeți un vârf pentru a începe, apoi muchiile sau vârfurile următoare în ordine, sau trageți din vârf în vârf. Fiecare muchie se folosește o singură dată. Înapoi anulează un pas, Indiciu arată următoarea muchie sigură, iar Rezolvă rulează pas cu pas algoritmul lui Fleury sau al lui Hierholzer. Vârfurile impare sunt pline, iar eticheta de la fiecare vârf este gradul său. În modul Desenează, o atingere pe un loc gol adaugă un vârf, iar o atingere pe două vârfuri le unește, încă o dată pentru o a doua muchie; trageți un vârf pentru a-l muta. Șterge elimină vârfuri și muchii. Când mai mult de două vârfuri sunt impare, Adaugă pune muchiile care fac figura trasabilă.
Cum funcționează
- Alegeți o figură, de pildă cele șapte poduri din Königsberg, casa lui Moș Nicolae sau o stea, sau desenați-o pe a dumneavoastră în modul Desenează, cu oricâte muchii între două vârfuri.
- Atingeți un vârf pentru a începe, apoi muchiile sau vârfurile în ordine, sau trageți din vârf în vârf. Dacă vă blocați, linia de stare spune de ce; Înapoi anulează un pas, iar Indiciu arată o muchie sigură.
- Citiți regula gradelor de sub figură, adăugați unei figuri imposibile muchiile propuse sau apăsați Rezolvă pentru a vedea algoritmul lui Fleury sau al lui Hierholzer desenând-o pas cu pas.
De ce hotărăsc vârfurile impare
O trăsătură care trece printr-un vârf sosește pe o linie și pleacă pe alta, deci folosește liniile acelui vârf două câte două. Numai acolo unde trăsătura începe sau se termină poate rămâne o linie fără pereche. Așadar un vârf cu un număr impar de linii trebuie să fie începutul sau sfârșitul. Fără vârfuri impare, trăsătura se termină unde a început: un circuit eulerian. Cu două, merge de la unul la celălalt: un drum eulerian. Cu patru sau mai multe sunt prea multe capete pentru o singură trăsătură, iar k vârfuri impare cer k/2 trăsături. Königsberg avea patru bucăți de uscat, cu cinci, trei, trei și trei poduri: toate patru impare, deci nicio plimbare nu putea trece peste fiecare pod o dată. Un pod nou între două dintre ele ar fi făcut plimbarea posibilă.
Algoritmii lui Fleury și Hierholzer
A ști că o figură poate fi desenată nu înseamnă a o desena: o trăsătură neatentă se poate tăia de liniile de care mai are nevoie. Algoritmul lui Fleury din 1883 evită asta printr-o singură regulă: nu treceți niciodată peste un pod, adică o linie a cărei îndepărtare ar despărți liniile rămase în două bucăți, decât dacă nu există altă linie. Algoritmul lui Hierholzer, dintr-o lucrare apărută în 1873, este mai rapid: mergeți oriunde până vă blocați, ceea ce se poate întâmpla doar la start, apoi, dintr-un vârf al traseului care mai are linii libere, parcurgeți încă o buclă închisă și inserați-o în traseu. Timpul crește proporțional cu numărul de muchii, și așa găsesc calculatoarele drumuri euleriene.
Întrebări frecvente
Care este diferența dintre un drum eulerian și un circuit eulerian?
Amândouă folosesc fiecare muchie a unui graf exact o dată. Un circuit eulerian se termină unde a început; un drum eulerian se termină în altă parte. Un graf conex are un circuit când fiecare vârf are grad par și un drum când exact două vârfuri au grad impar; drumul merge atunci de la unul la celălalt.
De ce nu pot fi trecute cele șapte poduri din Königsberg câte o dată fiecare?
Desenați fiecare bucată de uscat ca un vârf și fiecare pod ca o muchie. Insula Kneiphof avea cinci poduri, iar celelalte trei bucăți câte trei, deci toate cele patru vârfuri sunt impare. O plimbare poate începe sau se poate termina doar într-un vârf impar, iar patru sunt prea multe. Un pod în plus între două dintre ele lasă două vârfuri impare, iar plimbarea devine posibilă.
În câte moduri se poate desena casa lui Moș Nicolae?
44 din fiecare dintre cele două colțuri de jos, 88 în total, dacă o altă ordine sau un alt sens se socotesc alt mod. Din oricare alt vârf nu se poate, fiindcă acele colțuri sunt singurele două cu un număr impar de linii. Aplicația numără astfel modurile pentru figurile mici.
Ce este un pod într-un graf?
O muchie a cărei îndepărtare desparte un graf conex în două bucăți. Algoritmul lui Fleury nu trece niciodată peste un pod dintre muchiile rămase câtă vreme are altă alegere, fiindcă ar lăsa în urmă o parte din figură. În această aplicație, unei trăsături care se blochează după ce a trecut un pod prea devreme i se spune care pas a fost.
Pot exista mai multe muchii între două vârfuri?
Da. Un graf cu muchii paralele se numește multigraf, iar Königsberg are nevoie de unul: două poduri legau Kneiphoful de fiecare mal. În modul Desenează, atingeți din nou două vârfuri pentru a adăuga încă o muchie între ele, până la patru. Regula gradelor funcționează la fel, numărând fiecare muchie.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor