Cu numele Eile-ra, este problema a trei case și a trei puțuri.
Sarcina. Trei vecini au trei puțuri comune. Este posibil să se efectueze trasee care nu intersectează de la fiecare casă la fiecare godeu (Figura 1)?
Pentru a rezolva această problemă, vom folosi teorema dovedită de Euler în 1752.
Teorema. Dacă un poligon este împărțit într-un număr finit de poligoane, astfel încât oricare doi poligoane ale partiției să nu aibă puncte comune sau să aibă vârfuri comune sau să aibă margini comune, atunci egalitatea
unde B este numărul total de vârfuri, P este numărul total de muchii și T este numărul de poligoane (fețe).
Dovada. Să demonstrăm că egalitatea (*) nu se schimbă dacă tragem o diagonală într-un poligon al partiției date (Fig.2, a).
Într-adevăr, după realizarea unei astfel de diagonale în noua partiție, vor exista vârfuri B, muchii P + 1, iar numărul de poligoane va crește cu unul. În consecință, avem
B - (P + 1) + (T + 1) = B - P + G.
Folosind această proprietate, tragem diagonalele care împart triunghiurile de intrare în poligoane, iar pentru partiția obținută, vom arăta satisfacerea relației (*) (figura 2, b). Pentru aceasta, vom elimina consecvent margini externe, reducând numărul de triunghiuri. În acest caz, sunt posibile două cazuri:
a) pentru a elimina triunghiul ABC, este necesară îndepărtarea a două margini, în cazul nostru AB și BC;
b) pentru a șterge triunghiul MKN este necesar să eliminați o muchie, în cazul nostru MN.
În ambele cazuri, egalitatea (*) nu se schimbă. De exemplu, în primul caz, după eliminarea triunghiului, graficul va consta din vârfuri B-1, muchii P-2 și poligoane G-1:
(B-1) - (P + 2) + (T-1) = B - P + G.
Luați cel de-al doilea caz singur.
Astfel, ștergerea unui triunghi nu schimbă egalitatea (*). Continuând acest proces de înlăturare a triunghiurilor, ajungem în cele din urmă la o partiție formată dintr-un triunghi. Pentru o astfel de partiție B = 3, P = 3, T = 1 și, prin urmare, B - P + T = 1. Prin urmare, egalitatea (*) este valabilă pentru partiția inițială. a partiției poligonului, relația (*) este validă.
Observăm că relația Euler nu depinde de forma poligoanelor. Poligoanele pot fi deformate, mărite, reduse sau chiar distorsionate de laturile lor, cu condiția să nu existe discontinuități ale laturilor. Raportul lui Euler nu se va schimba în acest caz.
Să trecem acum la soluționarea problemei a trei case și a trei puțuri.
Soluția. Să presupunem că acest lucru se poate face. Observați casele cu punctele D1. D2. D3. și fântâni - punctele K1. K2. K3 (figura 1). Fiecare punct-casa este conectat cu fiecare punct bine. Obținem nouă margini care nu se intersectează în perechi.
Aceste muchii formează un poligon în plan, împărțit în poligoane mai mici. Prin urmare, pentru această partiție trebuie îndeplinită relația Euler B = P + T = 1. Mai adăugăm încă o parte - partea exterioară a planului în raport cu poligonul față de fețele în cauză. Apoi, formula lui Euler ia forma B = P + T = 2, cu B = 6 și P = 9. În consecință, T = 5. Fiecare dintre cele cinci fețe are cel puțin patru muchii, deoarece, din cauza problemei, trebuie să conecteze direct două case sau două puțuri. Deoarece fiecare muchie se află exact pe două fețe, numărul de muchii nu trebuie să fie mai mic decât (5 # 8729; 4) / 2 = 10, ceea ce contrazice condiția că numărul lor este 9. Această contradicție arată că răspunsul în problema este negativă - este imposibil să se traseze trasee disjuncte din fiecare casă în fiecare puț.
1. Se spune că un grafic este conectat. dacă vreunul dintre vârfurile sale poate fi îmbinat printr-o linie poligonală formată din marginile graficului. Desenați grafice conectate și incoerente.
2. Un grafic conectat care nu conține nici o linie poligonală închisă se numește arbore. Desenați graficele care sunt copaci.
3. Dovedeste ca intr-un graf care este un arbore, oricare doua varfuri pot fi unite de o singura linie poligonala.
4. Dovedeste ca pentru orice copac cu varfuri B si P edge, relatia lui Euler detine: B - P = 1.
5. Dați exemple de grafice pentru care B-P 1.
6. Un grafic care nu conține nici o polilinie închisă se numește o pădure. Lăsați pădurea să fie alcătuită din n copaci și are vârfurile B și P. Ce este B - P?
7. Desenați grafice pentru care B-P este egal cu: a) 0; b) 1; c) 2; d) -1; e) -2.
8. Indicați orice partiție a unui patrulater convex în quadrangles convexe.
9. Dovediți că pentru o partiție arbitrară a unui patrulater în patrulaterale, egalitatea B - T = 3 este valabilă.
10. Indicați orice partiție a unui pentagon convex în pentagoane convexe.
11. Specificați orice diviziune a triunghiului în heptagoni.
12. În interiorul n-gon, sunt luate puncte m. Aceste puncte și vârfuri ale poligonului sunt conectate prin segmente astfel încât poligonul original este împărțit în triunghiuri. Dovada că numărul de triunghiuri este n + 2 m-2.
13. Poligonul este împărțit într-un număr finit de poligoane, astfel încât trei muchii converg la fiecare vârf. Câte vârfuri și fețe există atunci când numărul de margini este egal cu: a) 6; b) 12; c) 15? Desenați astfel de partiții.
14. Dovediți că pentru orice împărțire a n -gon în m-goni, egalitatea 2B + (2 - m) Γ = n + 2 este valabilă.
15. În poligon a fost tăiat un orificiu de poligon. Restul a fost spart în poligoane. Ce este B - P + T pentru această partiție?
16. Doi vecini au: a) trei puțuri comune; b) patru puțuri comune. Este posibil să se efectueze trasee care nu intersectează de la fiecare casă la fiecare puț?
17. Trei vecini au: (a) două puțuri comune; b) patru puțuri comune. Este posibil să se efectueze trasee care nu intersectează de la fiecare casă la fiecare fantă?
18. Patru vecini au patru puțuri comune. Este posibil să se efectueze trasee care nu intersectează de la case la fântâni, astfel încât fiecare casă să fie conectată la trei puțuri și fiecare puț cu trei case?
Articole similare
Trimiteți-le prietenilor: