Đúng như cái tên của mình, bài toán Königsberg lấy bối cảnh tại thành phố cổ Königsberg (hiện có tên là Kaliningrad). Ban đầu, Königsberg là một thành phố thuộc Vương quốc Phổ được thành lập năm 1255. Sau đó trở thành thủ phủ của Đức, tiếp đến thuộc quản lý bởi quân đội Liên Xô vào năm 1945.
Câu chuyện bắt đầu vào thế kỷ 18, tại thị trấn Königsberg nằm bên bờ sông Pregel có 7 chiếc cầu, chia thành phố thành 4 vùng. Chúng có thể nối hai bên bờ sông, hay bờ sông với cù lao hoặc là nối 2 cù lao. Vào lúc bấy giờ, người dân Kaliningrad cảm thấy quá mất thời gian khi phải đi qua sự sắp xếp cực kỳ phức tạp của những cây cầu tại đây. Vì thế họ đưa ra một câu đố mà chưa từng có người giải ra, đó chính là liệu rằng có cách nào để đi qua hết 7 cây cầu mà không phải lặp lại cây cầu nào hay không (mỗi cây cầu chỉ được qua một lần), bất kể điểm xuất phát hay điểm tới. Câu đố đó đã thu hút nhiều người thử sức, thậm chí là đến tận Kaliningrad để thử đi dạo để tìm cảm hứng cho lời giải, thế nhưng đến nay vẫn chưa có ai thành công tìm được đáp án.
Thật ra, Königsberg không cách qua xa St.Petersburg nơi nhà toán học nổi tiếng Leonhard Euler sinh sống. Thế nhưng tại sao Euler lại quan tâm và dành thời gian cho câu đố đơn giản tưởng chừng như chẳng hề liên quan đến lĩnh vực toán học như vậy? Vào giai đoạn ấy, rõ ràng Euler đang bận rộn với nhiều dự án của mình, ước tính cả cuộc đời Euler đã xuất bản hơn 500 cuốn sách và bản thảo. Chỉ tính riêng năm 1775, trung bình ông đã hoàn tất một bài báo khoa học mỗi tuần và trong suốt cuộc đời mình, ông đã nghiên cứu về nhiều chủ đề khác nhau ngoài toán học như cơ học, quang học, thiên văn học, thuỷ động lực học,… Vì thế chẳng có gì là ngạc nhiên khi lần đầu nghe qua câu đố này, Euler đã cảm thấy tầm thường.
Câu chuyện bắt đầu vào thế kỷ 18, tại thị trấn Königsberg nằm bên bờ sông Pregel có 7 chiếc cầu, chia thành phố thành 4 vùng. Chúng có thể nối hai bên bờ sông, hay bờ sông với cù lao hoặc là nối 2 cù lao. Vào lúc bấy giờ, người dân Kaliningrad cảm thấy quá mất thời gian khi phải đi qua sự sắp xếp cực kỳ phức tạp của những cây cầu tại đây. Vì thế họ đưa ra một câu đố mà chưa từng có người giải ra, đó chính là liệu rằng có cách nào để đi qua hết 7 cây cầu mà không phải lặp lại cây cầu nào hay không (mỗi cây cầu chỉ được qua một lần), bất kể điểm xuất phát hay điểm tới. Câu đố đó đã thu hút nhiều người thử sức, thậm chí là đến tận Kaliningrad để thử đi dạo để tìm cảm hứng cho lời giải, thế nhưng đến nay vẫn chưa có ai thành công tìm được đáp án.
Euler và bài toán
Thật ra, Königsberg không cách qua xa St.Petersburg nơi nhà toán học nổi tiếng Leonhard Euler sinh sống. Thế nhưng tại sao Euler lại quan tâm và dành thời gian cho câu đố đơn giản tưởng chừng như chẳng hề liên quan đến lĩnh vực toán học như vậy? Vào giai đoạn ấy, rõ ràng Euler đang bận rộn với nhiều dự án của mình, ước tính cả cuộc đời Euler đã xuất bản hơn 500 cuốn sách và bản thảo. Chỉ tính riêng năm 1775, trung bình ông đã hoàn tất một bài báo khoa học mỗi tuần và trong suốt cuộc đời mình, ông đã nghiên cứu về nhiều chủ đề khác nhau ngoài toán học như cơ học, quang học, thiên văn học, thuỷ động lực học,… Vì thế chẳng có gì là ngạc nhiên khi lần đầu nghe qua câu đố này, Euler đã cảm thấy tầm thường.
Điều này được chứng minh thông qua bức thư phản hồi từ chối giải gửi đến Carl Leonhard Gottlieb Ehler năm 1736. Trong thư ông đã viết: "Ngài thấy đấy, lời giải này chẳng liên quan gì đến toán học và tôi cũng tự hỏi không hiểu tại sao ngài lại mong đợi một nhà toán học giải quyết nó, khi mà đáp án dựa vào lý luận mà chẳng phụ thuộc gì đến bất kỳ nguyên tắc toán học nào."
Mặc dù vậy, Euler vẫn cảm thấy hứng thú bài toán này. Trong một lá thư viết cùng năm cho nhà toán học và kỹ sư người Ý Giovanni Marioni, Euler đã viết: "Câu đố này thật tầm thường, nhưng tôi nghĩ rằng nó đáng để được chú ý khi mà cả hình học, đại số lẫn phương pháp đếm cũng không thể giải quyết được đó."
Euler tin rằng câu đố này có liên quan đến một chủ đề mà Gottfried Wilhelm Leibniz từng thảo luận và đã bày tỏ mong muốn được nghiên cứu cùng, được gọi là geometria situs (hình học của vị trí), sau này được biết đến là toán học Topo. Tiền thân của lý thuyết đồ thị, một mảng toán học quan trọng sau này. Chính nhờ vào bài toán này, Euler đã mở ra một nhánh mới cho toán học tổ hợp và lời giải của ông được xem là định lý đầu tiên của lý thuyết đồ thị được gọi là đường đi Euler.
Chứng minh của Euler
Trong một bài báo được xuất bản vào năm 1741, Euler đã trình bày lời giải cho câu đố 7 cây cầu Königsberg và đưa ra lời giải tổng quát cho dạng bài toán này, bất kể số lượng vùng đất cũng như số lượng cây cầu. Bài báo này được gọi là Solution problematis ad geometriam situs pertinentis gồm 21 đoạn, diễn giải cũng như đưa ra những phân tích của ông cho dạng bài toán như thế này.
Trong bài báo này, Euler cũng thừa nhận rằng bài toán này liên quan đến hình học, nhưng không phải là loại hình học thời bấy giờ mà là một loại hoàn toàn mới, hình học vị trí. Bên cạnh đó, ông cũng cho rằng mình có thể liệt kê ra tất cả con đường có thể có trong bài toàn, nhưng điều đó rất mất thời gian và không hợp lí khi áp dụng với những bài toán lớn hơn cùng dạng. Vì thế, Euler đã quyết định chọn một phương pháp khác.
Euler đã giản lược và thay tất cả các chi tiết đất, cù lao bằng điểm và thay cầu bằng đoạn nối, sau đó ông thu về một đồ thị vô hướng như bên dưới. Cách biểu diễn bằng điểm và đoạn thẳng hay cung chính là bước đầu cho sự ra đời của lý thuyết đồ thị sau này.
Quay trở lại bài toán, rõ ràng khi đi qua một vùng, người đi buộc phải băng qua một cây cầu và rời đi với cây cầu khác. Do đó, luôn tồn tại một cặp cạnh đến và đi. Cũng chính vì thế bậc của đồ thị phải là số chẵn (bậc của nút bằng số cạnh nối với nó), ví dụ A có bậc là 5, B là 3,… Sau đó, ông nhận thấy và đưa ra định lý rằng một đồ thị có đường đi qua tất cả các cạnh và mỗi cạnh chỉ đi qua một lần gọi là đường đi Euler, khi và chỉ khi:
- Chỉ có thể tồn tại 2 đỉnh bắt đầu và kết thúc là bậc lẻ, còn các đỉnh trong đồ thị G phải là bậc chẵn.
- Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn.
Còn ở bài toán 7 cây cầu này có đến 4 nút bậc lẻ, vì vậy điều này không thể tồn tại. Euler cũng đã chỉ ra rằng có thể sửa đổi câu đố này bằng cách xây thêm hoặc bỏ bớt 1 cây cầu phù hợp. Trên thực tế, điều này cũng đã từng xảy ra vào năm 1875, khi người dân thành phố Königsberg quyết định sẽ xây dựng thêm một cây cầu mới ở giữa 2 đỉnh và C, nâng số bậc của 2 nút này lên là 4, như vậy sẽ thoả điều kiện của đường đi Euler, và thế là bài toán sẽ có lời giải.
Thế nhưng số phận của thành phố sau đó cũng không mấy tốt đẹp khi vào năm 1944, chỉ 4 ngày trong tháng 8, quân đội Anh đã thả bom xuống thành phố này và phá huỷ hầu hết công trình tại đây. Đến đầu năm 1945, Königsberg bị bao vây bởi quân lính Nga. Người Đức trong thành phố bắt đầu di tản nhưng không kịp, hàng ngàn người đã bị giết khi cố gắng băng qua con sông băng. Tháng 4 năm 1945, hồng quân chiếm được thành phố khi nó chỉ còn đống tro tàn.
Thành phố giờ đây đã có nhiều thay đổi, nhiều cây cầu đã bị phá huỷ trong trận đánh bom, tên gọi thành phố cũng được thay đổi và bài toán nổi tiếng ấy đã không còn tồn tại. Dù vậy, Königsberg sẽ luôn được ghi nhận là nơi đã tạo nên câu đố mang đến ý tưởng cho một ngành toán học mới có vai trò rất quan trọng sau này.
Theo maa, (a)
==***==
Khoá học Quản trị Chiến lược Dành cho Lãnh đạo Doanh nghiệp
==***==
Nơi hội tụ Tinh Hoa Tri Thức - Khơi nguồn Sáng tạo
Để tham gia khóa học công nghệ truy cập link: http://thuvien.hocviendaotao.com
Mọi hỗ trợ về công nghệ email: dinhanhtuan68@gmail.com
---
Khóa học Hacker và Marketing từ A-Z trên ZALO!
Khóa học Hacker và Marketing từ A-Z trên Facebook!
Bảo mật và tấn công Website - Hacker mũ trắng
KHÓA HỌC LẬP TRÌNH PYTHON TỪ CƠ BẢN ĐẾN CHUYÊN NGHIỆP 
Khóa học Lập trình Visual Foxpro 9 - Dành cho nhà quản lý và kế toán 
Khóa học hướng dẫn về Moodle chuyên nghiệp và hay Xây dựng hệ thống đào tạo trực tuyến chuyên nghiệp tốt nhất hiện nay. 
Khóa học AutoIt dành cho dân IT và Marketing chuyên nghiệp 
Khoá học Word từ cơ bản tới nâng cao, học nhanh, hiểu sâu 
Khóa học hướng dẫn sử dụng Powerpoint từ đơn giản đến phức tạp HIỆU QUẢ 
Khóa học Thiết kế, quản lý dữ liệu dự án chuyên nghiệp cho doanh nghiệp bằng Bizagi 
Khóa học Phân tích dữ liệu sử dụng Power Query trong Excel 
Khóa học Lập trình WEB bằng PHP từ cơ bản đến nâng cao 
Khóa học Phân tích dữ liệu sử dụng SPSS - Chìa khóa thành công!
Khóa học "Thiết kế bài giảng điện tử", Video, hoạt hình kiếm tiền Youtube bằng phần mềm Camtasia Studio 
Khóa học HƯỚNG DẪN THIẾT KẾ VIDEO CLIP CHO DÂN MARKETING CHUYÊN NGHIỆP 
HƯỚNG DẪN THIẾT KẾ QUẢNG CÁO VÀ ĐỒ HỌA CHUYÊN NGHIỆP VỚI CANVA Hãy tham gia khóa học để trở thành người chuyên nghiệp. Tuyệt HAY!😲👍 
GOOGLE SPREADSHEETS phê không tưởng 
Hãy tham gia khóa học để biết mọi thứ
Khóa học Ba, Mẹ và Bé - Cùng bé lập trình TUYỆT VỜI
Khóa học sử dụng Adobe Presenter-Tạo bài giảng điện tử 
Để thành thạo Wordpress bạn hãy tham gia khóa học 
Khóa học sử dụng Edmodo để dạy và học hiện đại để thành công 
==***== Bảo hiểm nhân thọ - Bảo vệ người trụ cột 
Cập nhật công nghệ từ Youtube tại link: congnghe.hocviendaotao.com
Tham gia nhóm Facebook
Để tham gia khóa học công nghệ truy cập link: http://thuvien.hocviendaotao.com
Mọi hỗ trợ về công nghệ email: dinhanhtuan68@gmail.com
Bảo mật và tấn công Website - Hacker mũ trắng
KHÓA HỌC LẬP TRÌNH PYTHON TỪ CƠ BẢN ĐẾN CHUYÊN NGHIỆP
Khóa học AutoIt dành cho dân IT và Marketing chuyên nghiệp
Khoá học Word từ cơ bản tới nâng cao, học nhanh, hiểu sâu
Khóa học hướng dẫn sử dụng Powerpoint từ đơn giản đến phức tạp HIỆU QUẢ
Khóa học Thiết kế, quản lý dữ liệu dự án chuyên nghiệp cho doanh nghiệp bằng Bizagi
Khóa học Phân tích dữ liệu sử dụng Power Query trong Excel
Khóa học Lập trình WEB bằng PHP từ cơ bản đến nâng cao
Khóa học Phân tích dữ liệu sử dụng SPSS - Chìa khóa thành công!
kiếm tiền Youtube bằng phần mềm Camtasia Studio
Khóa học HƯỚNG DẪN THIẾT KẾ VIDEO CLIP CHO DÂN MARKETING CHUYÊN NGHIỆP
HƯỚNG DẪN THIẾT KẾ QUẢNG CÁO VÀ ĐỒ HỌA CHUYÊN NGHIỆP VỚI CANVA
Hãy tham gia khóa học để trở thành người chuyên nghiệp. Tuyệt HAY!😲👍
GOOGLE SPREADSHEETS phê không tưởng
Hãy tham gia khóa học để biết mọi thứ
Khóa học Ba, Mẹ và Bé - Cùng bé lập trình TUYỆT VỜI
Khóa học sử dụng Adobe Presenter-Tạo bài giảng điện tử
Để thành thạo Wordpress bạn hãy tham gia khóa học
Khóa học sử dụng Edmodo để dạy và học hiện đại để thành công
==***==
Bảo hiểm nhân thọ - Bảo vệ người trụ cột
Tham gia nhóm Facebook
Để tham gia khóa học công nghệ truy cập link: http://thuvien.hocviendaotao.com
Mọi hỗ trợ về công nghệ email: dinhanhtuan68@gmail.com
Nguồn: Tinh Tế