TAILIEUCHUNG - Toán rời rạc và một số vấn đề liên quan (P9)

Tham khảo tài liệu 'toán rời rạc và một số vấn đề liên quan (p9)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Sau khi bình phương hai vế của 1 và sử dụng các hệ thức ii và ký hiệu rút gọn X2 x ị 4- X2 4- xf 4ữ2j ta được biểu thức rút gọn sau của Pij dưới dạng một tam thức bậc hai đối với biến Xi 4- Xj Pij Xi Xj 2 4- 4aij Xi 4- Xj 4- 4 a2j 62 trong đó giữa Xi và Xj có các hệ thức sau đây X2 X2 4a2-4-4b2 Xi 4-Xj 2 4- Xi Xj 2 8 a2 ò2 . 2 3 4 Vì Xi 0 Xj 0 nên biểu thức 2 của P2- cho biết Pịj và do đó Pij đạt giá trị maxífyM hay giá trị minify khi và chỉ khi Xi Xj đạt max hay min. Do đó từ 4 ta suy ra Xi 4- Xj đạt max min Xi Xj đạt min max . Từ 4 ta được Xi 4- Xj 2 8 ữ2- 4- ò2 và do đó thay vào 2 ta được plj 5Í 4 aijV2 4- ựa2j 4- b2 . Vậy Pij PijM 2 fyV2 4- -ựa2j 4- b2 5 Pij PijM z aijV2 4- ựa2- b2 6 Xi Xj 26 Xi Xj C 2ữjj 2ữ . Mặc khác Xi - Xj đạt max khi và chỉ khi hoặc Xi đạt max 2aijt Xj đạt min Zo 2b hoặc Xj đạt max 2ãij Xi đạt min Xo 2b. Suy ra PỈj plm 2aij 2Ò 2 4ũfy 2cfy 4- 26 4 a2 - 62 4 ữjj 4- 6 2 4- 8aij aij 4- 6 4- 4 aij 4- b aij b 16aij aij 4- 6 . Vậy và Pij Pij Pij 7 8 Và do đó Pijm 4bự2 với aij b 4ựa2 4- ab 4a p. 4- với aij 112 Bây giờ ta trở lại với hàm 2n biến p xi z r . xn x n từ 5 và 7 ta thu được bất đẳng thức kép sau 4 ựaiÁaij b p 22 Pd 2 ự4 ỏ2 l i j n trong đó 0 b dij a. Đến đây ta có thể tìm được các giá trị lớn nhất PM và nhỏ nhất Pm của p. - Trước hết ta tìm giá trị nhỏ nhất pm của p p zi xí . Xi x ị . xn x nỴ Để tính Pm ta hãy để ý rằng n - 1 52 Zi2 22 tâ X x x j 22 44 - í9 i l l i j n l i j n Từ iii và 9 ta được n _ l 4a2 2 n - 2 6 ế 22 aj . Suy ra 22 02j ft - l o2 7j- ft l ft - 2 h2 n l a2 ơ2_xỏ2 const 10 l i j n n limaxa Cn-iTnindii. z vj 11- L b j Hệ thức 10 chứng tỏ rằng - Không thể xảy ra dij b với Ví j Điều này dễ dàng suy ra bằng phương pháp chứng minh phản chứng . Từ đó suy ra rằng phải có một số giá trị dij a. Mặt khác có tất cả C2 n 1 Cn-1 giá trị của dij mà theo 10 thì tối đa có Ơ2_1 giá trị dij 6 và vì thế phải có n 1 giá trị dij nào đó đạt cực đại bằng a chẳng hạn 012 013 Oin o tức là dij a j 7 1 . Cuối cùng suy ra Pm 4 n - 1 ạ o o í - n -

• Toán học
• ứng dụng toán rời rạc
• giáo trình toán rời rạc
• toán đại học
• toán cao cấp
• thi học sinh giỏi toán
• Toán rời rạc
• bài giảng Toán rời rạc
• bài tập Toán rời rạc
• đề cương Toán rời rạc
• Ngôn ngữ lập trình
• Toán rời rạc địa cương
• Đề cương môn học
• Toán rời rạc ứng dụng trong tin học
• Bài toán về đường đi
• Đường đi Euler
• Đường đi Hamilton
• Đại cương về đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Toán học
• Xác suất rời rạc
• Ứng dụng xác suất rời rạc
• Toán xác suất rời rạc
• Phương pháp toán sơ cấp
• Biểu diễn đồ thị
• Đồ thị có hướng
• Khái niệm cơ bản về cây
• Tính chất của cây
• Phép duyệt cây nhị phân
• Toán rời rạc trong tin học
• Ngôn ngữ hình thức
• Phương pháp đệ quy
• Lôgic mệnh đề
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Tìm kiếm trên đồ thị
• Thuật toán tìm kiếm
• Ứng dụng của thuật toán tìm kiếm
• tài liệu toán rời rạc
• học toán rời rạc
• Đề cương bài giảng Toán rời rạc
• Thảo luận Logic
• Logic mệnh đề
• Kỹ thuật đếm cơ bản
• Số nguyên và ứng dụng
• Mô hình toán
• Toán ứng dụng
• Lý thuyết toán học
• Mệnh đề toán học
• Bài toán luồng cực đại
• Ứng dụng bài toán luồng cực đại
• Ứng dụng trong tổ hợp
• Bài toán cặp ghép cực đại
• Đồ thị hai phía
• Đại số Boole
• Toán giải tích
• Hệ mô tả rời rạc
• Ứng dụng hệ mô tả rời rạc
• Hệ phương trình sai phân
• Đại số đại cương
• Toán kinh tế
• Toán thống kê