Ce este acest lucru și de ce sunt necesare?
După ce marele matematician Euler Leonhard a fost întrebat: Este posibil pentru a ocoli cele șapte poduri în picioare, apoi în Königsberg (azi Kaliningrad, Rusia), care au fost la fiecare dată? Înainte de a planifica Koenigsberg - puteți încerca!
Considerăm că această problemă, în 1736, Euler a demonstrat că acest lucru nu este posibil, și este considerat mai mult problema generală: ce zonă separată de bayous și conectate prin punți, este posibil pentru a obține în jur, vizitând fiecare pod exact o dată, și ceea ce este imposibil.
Modificăm problema într-o oarecare măsură. Fiecare dintre zonele considerate, separate de un râu, indicăm cu un punct, iar punțile care le conectează sunt un segment de linie (nu neapărat o linie dreaptă). Apoi, în loc de plan, vom lucra pur și simplu cu o anumită figură compusă din segmente de curbe și linii. Astfel de figuri din matematica modernă se numesc grafice, segmentele sunt coaste, iar punctele care leagă marginile sunt vârfuri. Apoi, problema inițială este echivalentă cu următoarea: dacă este posibilă trasarea unui grafic dat fără a lua creionul din hârtie, adică în așa fel încât fiecare dintre margini să treacă exact o singură dată. Astfel de grafice, care pot fi desenate fără a lua creionul din hârtie, sunt numite unicursal (din latine unus cursus - o singură cale), sau Euler. Deci, sarcina este pusă astfel: în ce condiții este graficul unicursal? În mod evident, graficul unicursal nu încetează să mai fie unicursal, dacă modificați lungimea sau forma coastele lui, și de a schimba locația nod - dar nu ar schimba blaturi de conectare coaste (în sensul că, dacă sunt conectate două vârfuri, acestea trebuie să fie conectate, iar dacă ar fi întreruptă Apoi deconectat).
Dacă graficul este unicursal, atunci graficul echivalent topologic este, de asemenea, unicursal. Prin urmare, unicurismul este o proprietate topologică a graficului.
În primul rând, este necesar să se facă distincția între graficele conectate și cele deconectate. Sunt conectate astfel de figuri încât orice două puncte pot fi conectate într-un fel care aparține acestei figuri. De exemplu, majoritatea literelor din alfabetul rusesc sunt legate, dar litera Y nu este: este imposibil să mergeți de la jumătatea stângă la dreapta, prin punctele care aparțin acestei scrisori. Conectivitatea este o proprietate topologică: nu se schimbă atunci când se transformă o figură fără spargere și lipire. Este clar că dacă graficul este unicursal, atunci trebuie să fie conectat.
În al doilea rând, ia în considerare vârfurile graficului. Vom numi indexul vârfului numărul de margini întâlnite la acest vârf. Acum, să ne întrebăm: ce poate fi egal cu indicele vârfurilor grafului unicursal.
Poate începe și se termină în același punct (să-l numim „traseu închis“), linia este trasată grafic, și poate fi în diferite (o numim „cale non-închis“): Pot exista două cazuri. Încercați să trageți astfel de linii - cu ceea ce doriți intersecții de sine - dublu, triplu, etc. (pentru claritate, este mai bine ca marginile să nu fie mai mari de 15).
Este ușor de observat că într-o cale închisă toate nodurile au un indice par și, într-o cale neacoperită, exact două sunt ciudate (acesta este începutul și sfârșitul căii). Faptul este că, în cazul în care nodul nu este un început sau sfârșit, a venit la el, noi trebuie să fim apoi din ea - atât cât de multe margini sunt incluse în ea, la fel de mult din ea, ci doar numărul de muchii de intrare și de ieșire este chiar . Dacă vârful inițial coincide cu vârful finit, atunci și indicele său este chiar: de câte marginile ies din el, după cum au intrat mulți. Și dacă punctul inițial nu coincide cu sfârșitul anului, indicii lor ciudat: de la punctul de plecare trebuie să obțină o dată afară, și apoi, dacă se întoarce și apoi pleacă din nou în cazul în care din nou - să plece din nou, etc;.. iar ultimul trebuie să vină, și dacă îl lăsăm mai târziu, atunci din nou trebuie să ne întoarcem și așa mai departe.
Pentru ca graficul să fie unicursal, este necesar ca toate nodurile lui să aibă un indice par, sau că numărul de noduri cu un indice ciudat este egal cu două.
Acum, uita-te din nou la graficul problemei podurilor Koenigsberg.
Contorizați indicii vârfurilor și asigurați-vă că nu poate fi unicursal în nici un fel. De aceea nu ați reușit când ați vrut să ocoliți toate podurile.
Articole similare
Trimiteți-le prietenilor: