Định lý 4 mau & ứng dụng

Chia sẻ bởi Phạm Huy Hoạt | Ngày 14/10/2018 | 164

Chia sẻ tài liệu: Định lý 4 mau & ứng dụng thuộc Các công cụ toán học

Nội dung tài liệu:

Định lý bốn màu
(về Bản đồ bốn màu và Bài toán xếp lịch)

I.- Khái quát & định lý
Định lý bốn màu (còn gọi là định lý bản đồ bốn màu) phát biểu như sau:
Với bất kỳ mặt phẳng nào được chia thành các vùng phân biệt, chẳng hạn như bản đồ hành chính của một quốc gia, vùng lãnh thổ..., chỉ cần dùng tối đa bốn màu để phân biệt các vùng lân cận với nhau.
Hai vùng được coi là lân cận nếu như chúng có chung nhau một đoạn đường biên (Biên giới, địa giới, danh giới...), không tính chung nhau một điểm. (Điểm mút)
“Định lý bốn màu” là định lý lớn đầu tiên được chứng minh bằng máy vi tính ; Tuy nhiên một số nhà toán học không đồng tình với cách chứng minh này, bởi vì con người không thể kiểm chứng trực tiếp được cách chứng minh. Do vậy, muốn tin vào chứng minh này thì người ta phải công nhận sự chính xác của Trình biên dịch và phần cứng máy tính được sử dụng để chạy chương trình chứng minh.
II.-Lịch sử và ý nghĩa của “Định lý bốn màu”
1/- Vấn đề đạt ra:
Vào năm 1852 lần đầu tiên Francis Guthrie - khi ông thử tô màu bản đồ nước Anh - ông nhận ra rằng chỉ cần bốn màu khác nhau là đủ. Ông đã đem vấn đề này hỏi người anh trai là Fredrick, lúc đó đang là sinh viên của trường Đại học Học viện London (UCL). Fredrick đã đưa vấn đề này hỏi thầy của mình là nhà toán học Augustus De Morgan nhưng người thầy cũng chưa biết rõ và chưa nghiên cứu đến.
Người đầu tiên giới thiệu vấn đề ra trước công chúng là nhà toán học Arthur Cayley vào năm 1878 tại Hội Toán học London, ông đã chỉ ra người đề cập vấn đề là De Morgan.
Người đầu tiên chứng minh định lý này là Alfred Kempe vào năm 1879. Năm 1880, có thêm một cách chứng minh khác của Peter Guthrie Tait. Nhưng đến năm 1890 Percy Heawood đã chỉ ra sai lầm trong cách chứng minh của Kempe, và đến năm 1891 Julius Petersen chỉ ra sai lầm trong cách chứng minh của Tait.
Trong việc chỉ ra sai lầm của Kempe, Heawood còn chứng minh rằng tất cả các Đồ thị phẳng phải sử dụng năm màu khác nhau,( xem Định lý năm màu).
Trong những năm 1960 và 1970, nhà toán học người Đức là Heinrich Heesch đã phát triển phương pháp sử dụng máy vi tính cho việc chứng minh vấn đề.
Năm 1976, cuối cùng thì định lý cũng được chứng minh bởi Kenneth Appel và Wolfgang Haken tại trường Đại học Illinois với sự trợ giúp của máy vi tính.
2- Vấn đề áp dụng vào thực tế
Mặc dù định lý được phát hiện ra trong quá trình tô màu bản đồ, nhưng trên thực tế rất ít khi được áp dụng vào khoa học vẽ bản đồ. Nhiều bản đồ phải sử dụng nhiều hơn bốn màu để thể hiện các khu vực, ngoài ra có những bản đồ sử dụng ít hơn bốn màu.
Hầu hết các bản đồ thực tế đều có vẽ hồ ao, mà tất cả hồ ao này phải vẽ cùng màu. Do vậy làm tăng số lượng màu cần thiết để vẽ các vùng đất. Nếu bỏ qua không vẽ hồ ao, thì trên thực tế vẫn có những vùng đất của cùng một quốc gia nhưng bị tách rời nhau, do đó phải vẽ cùng màu và định lý không áp dụng được.
Các sách vở về môn Bản đồ học cũng không nhắc đến định lý này. Những người vẽ bản đồ cho rằng họ quan tâm hơn đến việc phối màu bản đồ sao cho đẹp mắt; do vậy việc sử dụng bốn, năm hay nhiều màu hơn không phải là vấn đề đáng bận tâm.
3/-Những vùng đất không liên tục
Trên thực tế có nhiều quốc gia mà các phần lãnh thổ không liền kề nhau. Ví dụ như phần lãnh thổ Alaska của nước Mỹ, Nakhchivan của Azerbaijan, hay Kaliningrad của Nga. Nếu việc vẽ bản đồ đòi hỏi các phần lãnh thổ này phải cùng màu thì việc sử dụng bốn màu là không đủ.
Trong toán học, những vùng đất tách rời này được gọi là điểm cô lập của tập hợp miền quốc gia.

Thử xét một hình vẽ đơn giản sau
Trong hình, hai khu vực được đánh dấu "A" cùng thuộc về một quốc gia, và phải được vẽ cùng màu. Bản đồ này phải sử dụng năm màu.




III.- Bài toán xếp lịch

1/Giới thiệu bài toán Bài toán xếp lịch có một lịch sử phát triển dài, trải qua nhiều sự thay đổi lớn. Kể từ những thế hệ đầu tiên của máy tính,người ta đã nghĩ đến việc sử dụng máy tính để trợ giúp người xếp lịch. Ban đầu đó chỉ là những công cụ trợ giúp cho việc phân công những công việc điều hành phối hợp. Sau này mới
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...

Người chia sẻ: Phạm Huy Hoạt
Dung lượng: 35,65KB| Lượt tài: 3
Loại file: rar
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)