Î: Problema lui Euler. Trei vecini s-au certat. Toți trei au fântână. Este posibil să faceți o cale din casa fiecărui vecin în fiecare fântână, astfel încât aceste căi să nu se intersecteze?
R: În spațiul bidimensional este imposibil să conectați trei puțuri prin căi, astfel încât să nu se intersecteze.
Teorema are o relație directă cu teoria graficelor. Deciziile de 300 de ani care au trecut de la formularea problemei fântânilor nu au găsit nici un lucru - iată un cuplu:
1. este de a lua în considerare cele trei opțiuni rămase după cea de-a opta piesă.
Soluție: Fie nodurile A, B, C, 1, 2, 3 corespunzând formulării problemei trei case și fântâni, și demonstrează că drumul nouă - o margine, nu traversează fiecare nervură să nu fie posibilă.
Pe grafic se află muchiile A-1, A-2, A-3 și B-1, B-2, B-3 (care corespund căilor din casele A și B la cele trei godeuri). Graficul astfel construit a împărțit planul de lucru în 3 regiuni: X, Y, Z. Vertexul B, în funcție de locația sa în plan, intră într-una din aceste 3 regiuni. Dacă ne uităm la fiecare dintre cele 3 cazuri, „infiltrării“ nod B într-una dintre regiunile X, Y, Z - puteți vedea că de fiecare dată când oricare dintre nodurile 1, 2 sau 3 (sau una din cavitățile „vecinii“) nu vor mai fi disponibile pentru a construi un drum de la vârful B (adică va fi imposibil să construiți unul dintre marginile B1, B2 sau B3 care nu intersectează muchiile deja prezente în grafic). În consecință - răspunsul - nu puteți.
2. Bazat pe raportul dintre același Euler pentru poligoane
Soluție: Să presupunem că aceste 9 căi pot fi așezate. Să desemneze casele după punctele H1, H2, H3, fântâni - punctele C1, C2, C3. Fiecare punct-casa este conectat cu fiecare punct bine. Coaste obținute (grafic) în număr de nouă bucăți, care nu se intersectează în perechi. Astfel de margini formează pe planul considerat al problemei un poligon împărțit în poligoane mai mici. Pentru o astfel de partiție trebuie să fie satisfăcută relația binecunoscută Euler B = P + G = 1. Mai adăugăm încă o dată - la fețele luate în considerare - partea exterioară a planului în raport cu poligonul considerat. Apoi, raportul Euler devine B - P + G = 2, și B = 6 și P = 9. transformă, G = 5. Fiecare dintre cele cinci fețe are cel puțin patru coaste, deoarece, prin ipoteză problema Euler, nici unul dintre pistele nu ar trebui să conecteze direct două puțuri sau două case. Deoarece orice margine se află exact în două fețe, numărul de margini ale graficului trebuie să fie cel puțin 5 * 4/2 = 10. Aceasta contrazice condiția problemei originale, conform căreia numărul lor este de nouă. Această contradicție dovedește că răspunsul la problema celor trei puțuri ale lui Euler este negativ.
Soluție „posibilă“ se obține în tranziția la spațiul tridimensional, sau când amintindu faptul că Pământul - rundă, sau „Freeze“ nivel ridicat de apă într-una din fântâni și presupunerea că este posibil să se meargă pe gheață sau în „construcția“ de poduri, tuneluri și etc.
Articole similare
Trimiteți-le prietenilor: